Nested loops or Set operations?

[Robin Tropper]

Is there any advantage to using Java's operations defined in sets or collections over inspecting in nested for-loops?

For example, suppose I want to keep items from one array that do not appear in another, I could do:

for( PrimitiveType prim_1 : someArray ){
    for( PrimitiveType prim_2 : otherArray ){
         if( prim_1 != prim_2){
              ///put in some return list
         }
    }
}

Or else I could do:

ArrayList<NotPrimitive> excludedElements =
   new ArrayList(Arrays.asList(primitiveArrayToExclude));
for( PrimitiveType elem : someArray){
   if( ! excludedElements.contains( elem ) {
        //put in some return list
   }
}

I personally see no improvement in legibility nor any reduction of error potential.....

Any comment or observation is appreciated.
Thanks!

[Teo Filimon]

I wrote a mini-article a while back about looping ArrayLists. Essentially it's a lot faster when you loop using a good old-fashion counter, like:

for (int i=myArrayList.size()-1; i>-1; i--){
  final MyClass object = myArrayList.get(i);
  ...
}

But i would only write it like that if i really care about speed. Otherwise, i'm not sure i understand your question or the 2 code samples, i'm not sure they're doing the same thing

[Teo Filimon]

At a second read, i think i understand your question. Normally it doesn't really matter which one you loop (array or arraylist - however making arraylists will prevent you from using primitives which might be costly with boxing/unboxing). There might be some nuances with sorted data structures (slower to add objects, faster to check if it contains certain elements) but it really depends on the case.

[James Boswell]

Teo

I would strongly contest your "a lot faster" claim about a loop using a counter. In nearly all cases, the performance difference will be negligible.

The foreach syntax is much more readable and less error prone.

[Teo Filimon]

2 to 3 times faster is not really negligible (but i only mean ArrayList). But if you care more about readability i would also suggest the foreach syntax.

[Mike Simmons]

Addressing the original question, it's worth noting that if you look at a HashSet or TreeSet, a method like contains() can be MUCH faster than looping through an iterator or using a traditional for loop on an ArrayList or other structure. Depending on what operations you need to optimize, different data structures can offer different benefits. This can be much more significant than the iterator-vs-traditional-for-loop distinction, which (I agree with James) is often remarkably unimportant.

[James Boswell]

Teo Filimon wrote:2 to 3 times faster is not really negligible

Do you really mean 2 to 3 times faster? Or 2 to 3 milliseconds faster? Sorry to go off topic from the author's question but you shouldn't make a claim like this unless you have some figures to back it up.

[Paul Clapham]

Robin Tropper wrote:I personally see no improvement in legibility nor any reduction of error potential.....

Well, your second example avoids the error of comparing two objects using == instead of equals(), which error you committed in the first example. However the problem with the second example is that it doesn't go far enough in using the built-in methods. Here's a third example:

HashSet baseElementsSet = new HashSet(baseElements);
baseElementsSet.removeAll(elementsToExclude);
ArrayList result = new ArrayList(baseElementsSet);

In this code baseElements and elementsToExclude can be any kind of Collection.

When you read the code it's reasonably obvious what it's doing (and notice that the variable naming helps with that).

[Mike Simmons]

James Boswell wrote:

Teo Filimon wrote:2 to 3 times faster is not really negligible

Do you really mean 2 to 3 times faster? Or 2 to 3 milliseconds faster? Sorry to go off topic from the author's question but you shouldn't make a claim like this unless you have some figures to back it up.

Personally I've seen it as much as almost twice as fast. Not more. Of course, it all depends on what else you're doing inside the loop. If you're doing anything remotely complicated, it's very easy for the difference in these techniques to appear nonexistent. But it's possible to construct scenarios where you do something useful in the loop (enough to prevent the JVM from optimizing the whole thing away to nothing) and you do see a significant difference. Here are some sample test cases to run:

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class LoopingSpeed {
  public static final int REPETITIONS = 1000;
  private static final int N = 1000000;
  private static final int[] primitiveArray = new int[N];
  private static final Integer[] wrapperArray = new Integer[N];
  private static final List<Integer> arrayList = new ArrayList<>(N);

  static {
    Random r = new Random();
    for (int i = 0; i < N; i++) {
      int x = r.nextInt(100);
      primitiveArray[i] = x;
      wrapperArray[i] = x;
      arrayList.add(x);
    }
  }

  public static void main(String[] args) {
    Test[] tests = {
        new Test("foreach arraylist") {
          @Override
          long getSum() {
            long sum = 0;
            for (Integer i : arrayList)
              sum += i;
            return sum;
          }
        },
        new Test("foreach wrapper array") {
          @Override
          long getSum() {
            long sum = 0;
            for (int  i : wrapperArray)
              sum += i;
            return sum;
          }
        },
        new Test("foreach primitive array") {
          @Override
          long getSum() {
            long sum = 0;
            for (int  i : primitiveArray)
              sum += i;
            return sum;
          }
        },
        new Test("indexed wrapper array") {
          @Override
          long getSum() {
            long sum = 0;
            for (int  i = 0; i < wrapperArray.length; i++)
              sum += primitiveArray[i];
            return sum;
          }
        },
        new Test("indexed primitive array") {
          @Override
          long getSum() {
            long sum = 0;
            for (int  i = 0; i < primitiveArray.length; i++)
              sum += primitiveArray[i];
            return sum;
          }
        },
        new Test("indexed primitive array optimized") {
          @Override
          long getSum() {
            long sum = 0;
            for (int  i = 0, len = primitiveArray.length; i < len; i++)
              sum += primitiveArray[i];
            return sum;
          }
        },
        new Test("indexed primitive array reversed") {
          @Override
          long getSum() {
            long sum = 0;
            for (int  i = primitiveArray.length - 1; i >= 0; i--)
              sum += primitiveArray[i];
            return sum;
          }
        },
    };
    System.out.printf("%40s %10s %20s%n%n", "test", "time", "sum");
    for (int i = 0; i < 3; i++) {
      for (Test t : tests)
        t.run();
      System.out.println();
    }
  }

  static abstract class Test {

    final String name;

    Test(String name) { this.name = name; }

    abstract long getSum();

    void run() {
      long sum = 0;
      long start = System.currentTimeMillis();
      for (int i = 0; i < REPETITIONS; i++)
        sum += getSum();
      long finish = System.currentTimeMillis();
      System.out.printf("%40s %10d %20d%n", name, finish - start, sum);
    }
  }
}

[Teo Filimon]

@James I have my own performance tests to back it up. I've seen that depending on the arraylist size the boost varies between 2x and 3x. Also, please check: http://developer.android.com/training/articles/perf-tips.html#Loops

[James Boswell]

Mike, thanks for the example. Nice to see you also took the time to indent the output

Teo, fair enough if you have your own results and some evidence to back it up. It is very easy for new developers to follow advice to the letter and someone might avoid the for-each syntax based upon comments like "2 to 3 times faster".

[Martin Vashko]

Mike Simmons wrote:Addressing the original question, it's worth noting that if you look at a HashSet or TreeSet, a method like contains() can be MUCH faster than looping through an iterator or using a traditional for loop on an ArrayList or other structure.

It really depends. For small sizes, iterating over a primitive array (not ArrayList) can be much faster than a HashSet. For larger sizes, binary search over a pre-sorted primitive array can still beat a HashSet.

Apparently ArrayList iterators is slowed down by the comodification checks. Interesting. In any case, a for-each loop didn't ever turned out to be a bottleneck in a profiler for me yet. But I'm only developing in Java for several years

[Robin Tropper]

AMAZING DISCUSSION - thank you all for your replies!
That more than answers my question - SUPER!

[Winston Gutkowski]

Martin Vajsar wrote:It really depends. For small sizes, iterating over a primitive array (not ArrayList) can be much faster than a HashSet. For larger sizes, binary search over a pre-sorted primitive array can still beat a HashSet.

I guess the question is: how fast do you need it to be?

HashSet's offer O(1) contains() capability, as opposed to O(log(n)) for a TreeSet or binary search - the latter of which requires a sort() - so if I was doing it, I think I'd be looking at HashSet, simply because I reckon it would scale better.

@Robin: So, in answer to your original question: "Is there any advantage to using Java's operations defined in sets or collections over inspecting in nested for-loops?", the answer is: Yes.

And furthermore, a linked "Hashed" collection (LinkedHashSet/LinkedHashMap) might be the best of all. If List elements can't be duplicate, or if you're not worried about them, then I'd say that LinkedHashSet.removeAll() is what you want; but if you need to account for possible duplicates, then what about a:
LinkedHashMap<T, AtomicInteger>
where the AtomicInteger is the count of duplicate items in the source List<T>.

I'll leave you to work out how that might be useful.

Winston