Fastest way to recreate the ArrayList in a for loop

by

What would be much more efficient would be to use a Set instead of a list, for example the HashSet implementation. The contains method will run in O(1) instead of O(n) with a list. And you could save one call by only calling the add method.

As for your specific question, I would just create a new Set at each loop – object creation is not that expensive, probably less than clearing the set (as confirmed by the benchmark at the bottom – see the most efficient version in EDIT 2):

for (int j = 0, x; j < m; j++) {
    Set<Integer> values = new HashSet<Integer>();
    for (int i = 0; i < n; i++) {
        x = X[i][j];
        if (!values.add(x)) continue; //value.add returns true if the element was NOT in the set before
        System.out.println(x);
    }
}

However, the only way to know which is quicker (new object vs. clear) is to profile that portion of your code and check the performance of both versions.

EDIT

I ran a quick benchmark and the clear version seems a little faster than creating a set at each loop (by about 20%). You should still check on your dataset / use case which one is better. Faster code with my dataset:

Set<Integer> values = new HashSet<Integer>();
for (int j = 0, x; j < m; j++) {
    for (int i = 0; i < n; i++) {
        x = X[i][j];
        if (!values.add(x)) continue; //value.add returns true if the element was NOT in the set before
        System.out.println(x);
    }
    values.clear();
}

EDIT 2

An actually even faster version of the code is obtained by creating a new set of the right size at each loop:

for (int j = 0, x; j < m; j++) {
    Set<Integer> values = new HashSet<Integer>(n, 1); //right size from the beginning
    for (int i = 0; i < n; i++) {
        x = X[i][j];
        if (!values.add(x)) continue; //value.add returns true if the element was NOT in the set before
        System.out.println(x);
    }
}

Summary of result

After JVM warm up + JIT:

Set<Integer> values = new HashSet<Integer>(n, 1); =====> 280 ms
values.clear();                                   =====> 380 ms
Set<Integer> values = new HashSet<Integer>();     =====> 450 ms

More Related Contents:

  1. How to convert ArrayList to String[][]?
  2. How to move elements of Java ArrayList to file in java [closed]
  3. ArrayList with 2 dimensions [closed]
  4. Initialization of an ArrayList in one line
  5. Why does my ArrayList contain N copies of the last item added to the list?
  6. How to avoid “ConcurrentModificationException” while removing elements from `ArrayList` while iterating it? [duplicate]
  7. How to create a Multidimensional ArrayList in Java?
  8. How to use an arraylist as a prepared statement parameter [duplicate]
  9. Retrieving a random item from ArrayList [duplicate]
  10. Distinction between the capacity of an array list and the size of an array
  11. How to make a deep copy of Java ArrayList [duplicate]
  12. How do I clone a generic List in Java?
  13. Stream Filter of 1 list based on another list
  14. Add multiple items to an already initialized arraylist in Java
  15. Creating an Arraylist of Objects
  16. How to use invokeAll() to let all thread pool do their task?
  17. ArrayList.remove is not working in a loop
  18. Most efficient way to see if an ArrayList contains an object in Java
  19. Load arrayList data into JTable
  20. Using contains on an ArrayList with integer arrays
  21. ArrayList contains case sensitivity
  22. What is the Simplest Way to Reverse an ArrayList?
  23. Create an ArrayList with multiple object types?
  24. Java ArrayList Contain always return false although it contain the same value
  25. Sorting ArrayList of Objects by Object attribute
  26. Converting an ArrayList into a 2D Array
  27. How to change value of ArrayList element in java
  28. In Java, can you modify a List while iterating through it?
  29. How to merge two ArrayLists without duplicates? [duplicate]
  30. Add ArrayList to another ArrayList in java

Leave a Comment