wood burning stoves 2.0*
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes Iteration speed of Collections Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "Iteration speed of Collections " Watch "Iteration speed of Collections " New topic
Author

Iteration speed of Collections

Simran Dass
Ranch Hand

Joined: Jan 09, 2010
Posts: 183


Hi All,

Hope I am not starting a new topic. I have doubt on Iteration speed of Collections.
I will put my doubt in 2 parts : -


a) What do you mean by iteration in Collections ? Does it mean using specifically an ITERATOR or it can also mean using a for loop(or for that matter any loop) to access the elements one by one.


b) What is meant by iteration speed ? When there is a question regarding iteration speed or
which one iterates faster should we understand that we're using iterator's next()


ArrayList iterates faster than LinkedList.
But among LinkedList , Vector which one iterates faster ??
Wouter Oet
Saloon Keeper

Joined: Oct 25, 2008
Posts: 2700

A. Not all collections have an iterator. A HashMap for instance doesn't.
B. I think you should understand why a collection is "faster".For instance because it uses hashes to put objects in buckets.

A Vector uses synchronization and a LinkedList doesn't so there is a big difference in functionality so you're comparing apples and pears.


"Any fool can write code that a computer can understand. Good programmers write code that humans can understand." --- Martin Fowler
Please correct my English.
Manish Awasthy
Greenhorn

Joined: Jan 11, 2010
Posts: 25
among linked list and vector ,Linked list performs better because the methods of linked list are asynchronous where as methods of vector are synchronized


SCJP 1.6 98%

"Successful People Don't Plan Results,They Just Plan Proper Beginings.Right Result Always Follow Right Begining".
Neha Daga
Ranch Hand

Joined: Oct 30, 2009
Posts: 504
Even I thought so at first instant, but linked list have implementation different from that of vector. as of java 6 they can be implemented as queue also. So ye I agree with Wouter you are comparing apple with pear.


SCJP 1.6 96%
Ankit Garg
Sheriff

Joined: Aug 03, 2008
Posts: 9291
    
  17

When you iterate over elements sequentially, ArrayList is slower than LinkedList. ArrayList is faster in random access of elements, LinkedList is slow in that...


SCJP 6 | SCWCD 5 | Javaranch SCJP FAQ | SCWCD Links
Neha Daga
Ranch Hand

Joined: Oct 30, 2009
Posts: 504
Thanks Ankit...... now you know, why so many people noticed you were missing
Ankit Garg
Sheriff

Joined: Aug 03, 2008
Posts: 9291
    
  17

Neha Daga wrote:now you know, why so many people noticed you were missing

Yes now I know for sure
Simran Dass
Ranch Hand

Joined: Jan 09, 2010
Posts: 183


Thanks.

There was a question in ExamLab ...

[color=darkblue] LinkedList iterates faster than Vector - True or False.[color]

What should be my answer ?
Neha Daga
Ranch Hand

Joined: Oct 30, 2009
Posts: 504
I think it should be true.
Simran Dass
Ranch Hand

Joined: Jan 09, 2010
Posts: 183
Neha so this means that whenever the words are " iterates faster than..." and the words
SEQUENTIALLY OR RANDOMLY is not mentioned I should understand that they are talking
about SEQUENTIAL ACCESS.

Please correct me if I am wrong.
Neha Daga
Ranch Hand

Joined: Oct 30, 2009
Posts: 504
yes, I guess so.

Whers's is Ankit???
rushikesh sawant
Ranch Hand

Joined: Dec 22, 2009
Posts: 65
Iterator always works sequentially. Random access is specified by providing an index of particular object in question. Iterator just iterates from start to end accessing elements sequentially.


SCJP 5.0 100%
Neha Daga
Ranch Hand

Joined: Oct 30, 2009
Posts: 504
oh yes.
Simran Dass
Ranch Hand

Joined: Jan 09, 2010
Posts: 183

Thanks a lot guys .
Seetharaman Venkatasamy
Ranch Hand

Joined: Jan 28, 2008
Posts: 5575

Ankit Garg wrote:When you iterate over elements sequentially, ArrayList is slower than LinkedList.


Hi Ankit,i think not for an iterateration [it may for Access]. i tested for ArrayList as well as LinkedList . i found that ArrayList is faster than LinkedList in terms of iteration.

For ArrayList : 1152102 nano seconds
For LinkedList : 1210768 nano seconds

Ankit Garg
Sheriff

Joined: Aug 03, 2008
Posts: 9291
    
  17

seetharaman, how many times did you execute that code?? I executed it 5-6 times, and sometimes ArrayList was faster, and sometimes LinkedList was faster. But if I increase the elements in the List, i.e. from 3 to around 30, most of the times LinkedList was faster. Measuring the iteration time on very small samples isn't much accurate. The execution time depends on a lot of things like how much the CPU is busy etc...
Waclaw Borowiec
Greenhorn

Joined: Dec 14, 2009
Posts: 21
Ankit Garg wrote:When you iterate over elements sequentially, ArrayList is slower than LinkedList. ArrayList is faster in random access of elements, LinkedList is slow in that...


We can't say ArrayList is slower than LinkedList when iterating over it. ArrayList is implemented as an array, so iteration means going through subsequent cells in memory. In LinkedList cells are scattered in memory but linked together by additional pointers. In both cases iterating means jumping from one memory location to another and it's impossible to say that one structure is significantly faster than another.

Indeed ArrayList is much better than LinkedList in random access because we can get each element in constant time by its index (by adding it to the beginning of the array) whereas in LinkedList we have to always iterate over it until we find required element.
Ankit Garg
Sheriff

Joined: Aug 03, 2008
Posts: 9291
    
  17

Someone did some extensive experimentation on this here. The results are interesting...
Waclaw Borowiec
Greenhorn

Joined: Dec 14, 2009
Posts: 21
Ankit Garg wrote:Someone did some extensive experimentation on this here. The results are interesting...


I have a doubt here. The author of the tests uses System.currentTimeMilis() function for measurement where its resolution is less than 1ms (about 10ms; currentTimeMilis). His average results are from 0.05 ms to 35 ms, so I'm afraid they may be inaccurate. The tests should run longer, or nanoseconds should be used here.
Ankit Garg
Sheriff

Joined: Aug 03, 2008
Posts: 9291
    
  17

I modified his program and the results on my system were that ArrayList was slower in iteration than LinkedList
Seetharaman Venkatasamy
Ranch Hand

Joined: Jan 28, 2008
Posts: 5575

Ankit Garg wrote:seetharaman, how many times did you execute that code??

i executed around 10 times. all the times ArrayList was faster

Ankit Garg wrote:But if I increase the elements in the List, i.e. from 3 to around 30, most of the times LinkedList was faster


i executed 5 times . most of the time ArrayList was faster

i dont think that in term of Iteration LinkedList is Faster than ArrayList . please correct me , if i am wrong
Ankit Garg
Sheriff

Joined: Aug 03, 2008
Posts: 9291
    
  17

Okay I remembered it wrong, I had read about this from the Khalid Mughal book long time ago, and I reread it and there's nothing given about LinkedList being faster than ArrayList in terms of Iteration. Sorry, my bad ...
Seetharaman Venkatasamy
Ranch Hand

Joined: Jan 28, 2008
Posts: 5575

Thanks Ankit, Had a Nice Discussion
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 2994
    
    9
Simran Dass wrote: a) What do you mean by iteration in Collections ? Does it mean using specifically an ITERATOR or it can also mean using a for loop(or for that matter any loop) to access the elements one by one.

This is a false choice. Many for loops use iterators, and many do not. But they all access elements "one by one". If they're accessing a collection at all, of course.

Here's a for loop that uses an iterator:

Here's another that uses an iterator:

Here's one that does not use an iterator:

So for this question, talking about whether a for loop is used is useless. Instead, as whether it's better to use an iterator, or to use the get() method from List. That is the key distinction. Some posters talk about random access vs sequential - this is very close to the key issue, and for most good programmers, it means the same thing. Sequential access means using an iterator, and random access means using get(). Usually. But not all programmers understand this, and I think it's more useful to draw the distinction at using an iterator vs. using get(). Because it's possible to use get() to access items sequentially (as in the third code sample I gave above) - but for a LinkedList, it's probably a horrible idea. Using an iterator is much better.

In general, I would say using an iterator is better than using get() - unless you really need random (not sequential) access. There are a few cases where using get() is faster than using an iterator, true. But - and this is, to me, the most important point in all of this - in those situations where get() is faster than an iterator, it's just a little bit faster. Maybe twice as fast, at best. But in those cases where an iterator is faster than using get(), it can be much, much, MUCH faster. Ten times, hundreds of times, thousands of times, and much more. In general it's proportional to the size of the list. So if your list has less than ten items on it: well, in all likelihood, no one will ever care how fast it is to loop through it. But if it has a million items or more, it can make a huge difference how you loop through it. And using an iterator is so much better than using get(), one would have to be a fool not to do it.
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 2994
    
    9
Wouter Oet wrote:A. Not all collections have an iterator. A HashMap for instance doesn't.

A HashMap is not a Collection. But it does have three different views which are Collections, provided by the methods keySet(), values(), and entrySet(). If I need to iterate through a Map of any type, I almost always use entrySet(). Unless I only need the keys, or I only need the values. Regardless, in all cases I would then use an Iterator to loop through them. Specifically, I'd use the "new" (JDK 5) for loop, which would use an iterator implicitly, without me having to waste keystrokes on it:
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 2994
    
    9
Manish Awasthy wrote:among linked list and vector ,Linked list performs better because the methods of linked list are asynchronous where as methods of vector are synchronized

Hm, I think "asynchronous" has a somewhat different meaning than "not synchronized". I think you meant the latter. Many asynchronous communication techniques require synchronization in order to make them reliable. Like the wait-notify protocol, for example. But I don't think this thread has anything to do with asynchronous techniques. Let's just say that Vector is synchronized, and LinkedList and ArrayList are not synchronized.
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 2994
    
    9
Wouter Oet wrote:A Vector uses synchronization and a LinkedList doesn't so there is a big difference in functionality so you're comparing apples and pears.

Hm, I would say the difference in performance is small, and the difference in functionality is small. The difference in reliability could be huge, but in practice anyone relying on Vector to magically make their code "thread safe" without adding any other synchronization - is probably deluding themselves. The key difference is that Vector fools bad programmers into believing their code is typesafe, when it really isn't. (Usually.) ArrayList and LinkedList make no such false promises. Therefore Vector is evil, and ArrayList and Linked List are not.
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 2994
    
    9
Simran Dass wrote:

Thanks.

There was a question in ExamLab ...

[color=darkblue] LinkedList iterates faster than Vector - True or False.[color]

What should be my answer ?

I suggest writing to ExamLab and telling them this is a stupid question. It depends on how you iterate, and it depends on the platform, and the version of the Java compiler and JVM you're using. And in all likelihood, the difference is too small to matter to anyone. Real exam questions, in my experience, are very unlikely to be this stupid. Don't worry about it.
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 2994
    
    9
Simran Dass wrote: [color=darkblue] LinkedList iterates faster than Vector - True or False.[color]

Also, I suggest replacing the second "[ color ]" with "[ / color ]". Omit the spaces.
Ankit Garg
Sheriff

Joined: Aug 03, 2008
Posts: 9291
    
  17

Also, I suggest replacing the second "[ color ]" with "[ / color ]". Omit the spaces.

There's a trick to write BB tags in a message-> I suggest replacing the second [color] with [/color] ...
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 2994
    
    9
Yeah, I could think of several possible tricks, but I chose the one that took the least effort from me personally. I know how to look up ASCII codes when I'm being paid to do so. But as a user of a public service, I don't feel like doing that. Making things look pretty is not my concern.
Ankit Garg
Sheriff

Joined: Aug 03, 2008
Posts: 9291
    
  17

Mike Simmons wrote:I know how to look up ASCII codes when I'm being paid to do so.....Making things look pretty is not my concern.

1. If you felt insulted by what I said, that was not my intention at all. If you felt so, then I'm sorry for that.
2. The moderators on javaranch are not paid, everyone here at javaranch is a volunteer, just to clarify if that's what you were thinking...
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 2994
    
    9
Ankit Garg wrote:If you felt so

No.

Ankit Garg wrote:if that's what you were thinking...

And no.

I do appreciate your clarifications. I wasn't offended - I just didn't feel like looking up ASCII codes to make my post more palatable. I figured it was readable enough as it was. I just wanted to clarify that it wasn't my fault that the [ color ] tags had not been rendered as Simran probably hoped they would be.
Simran Dass
Ranch Hand

Joined: Jan 09, 2010
Posts: 183


Nice discussion.

I think that the question that I put should have been a bit more clear.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Iteration speed of Collections
 
Similar Threads
Question from Devaka's Practice 1
continue.....doubt....
Doubt in Collections.Pls help
ArrayList or LinkedList
Linked List - inserting value to correct position