• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Ron McLeod
  • Rob Spoor
  • Tim Cooke
  • Junilu Lacar
Sheriffs:
  • Henry Wong
  • Liutauras Vilda
  • Jeanne Boyarsky
Saloon Keepers:
  • Jesse Silverman
  • Tim Holloway
  • Stephan van Hulst
  • Tim Moores
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Mikalai Zaikin
  • Piet Souris

Nested loops or Set operations?

 
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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:


Or else I could do:


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

Any comment or observation is appreciated.
Thanks!
 
Greenhorn
Posts: 15
Android Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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:

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
Greenhorn
Posts: 15
Android Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Bartender
Posts: 1051
5
Hibernate Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Greenhorn
Posts: 15
Android Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Master Rancher
Posts: 4023
53
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Bartender
Posts: 1051
5
Hibernate Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Sheriff
Posts: 26770
82
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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:



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
Master Rancher
Posts: 4023
53
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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:
 
Teo Filimon
Greenhorn
Posts: 15
Android Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
@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
Bartender
Posts: 1051
5
Hibernate Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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".
 
Sheriff
Posts: 3837
66
Netbeans IDE Oracle Firefox Browser
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
AMAZING DISCUSSION - thank you all for your replies!
That more than answers my question - SUPER!
 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic