• 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
  • Tim Cooke
  • paul wheaton
  • Jeanne Boyarsky
  • Ron McLeod
Sheriffs:
  • Paul Clapham
  • Liutauras Vilda
  • Devaka Cooray
Saloon Keepers:
  • Tim Holloway
  • Roland Mueller
Bartenders:

Iteration speed of Collections

 
Ranch Hand
Posts: 183
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


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 ??
 
Bartender
Posts: 2700
IntelliJ IDE Opera
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Greenhorn
Posts: 25
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
among linked list and vector ,Linked list performs better because the methods of linked list are asynchronous where as methods of vector are synchronized
 
Ranch Hand
Posts: 504
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Sheriff
Posts: 9708
43
Android Google Web Toolkit Hibernate IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
When you iterate over elements sequentially, ArrayList is slower than LinkedList. ArrayList is faster in random access of elements, LinkedList is slow in that...
 
Neha Daga
Ranch Hand
Posts: 504
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks Ankit...... now you know, why so many people noticed you were missing
 
Ankit Garg
Sheriff
Posts: 9708
43
Android Google Web Toolkit Hibernate IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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


Yes now I know for sure
 
Simran Dass
Ranch Hand
Posts: 183
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


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
Posts: 504
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I think it should be true.
 
Simran Dass
Ranch Hand
Posts: 183
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 504
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
yes, I guess so.

Whers's is Ankit???
 
Ranch Hand
Posts: 65
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Neha Daga
Ranch Hand
Posts: 504
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
oh yes.
 
Simran Dass
Ranch Hand
Posts: 183
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Thanks a lot guys .
 
Ranch Hand
Posts: 5575
Eclipse IDE Windows XP Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 9708
43
Android Google Web Toolkit Hibernate IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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...
 
Greenhorn
Posts: 21
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 9708
43
Android Google Web Toolkit Hibernate IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Someone did some extensive experimentation on this here. The results are interesting...
 
Waclaw Borowiec
Greenhorn
Posts: 21
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 9708
43
Android Google Web Toolkit Hibernate IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I modified his program and the results on my system were that ArrayList was slower in iteration than LinkedList
 
Seetharaman Venkatasamy
Ranch Hand
Posts: 5575
Eclipse IDE Windows XP Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 9708
43
Android Google Web Toolkit Hibernate IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 5575
Eclipse IDE Windows XP Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks Ankit, Had a Nice Discussion
 
Master Rancher
Posts: 5116
82
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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

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

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

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

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

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
Posts: 9708
43
Android Google Web Toolkit Hibernate IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Master Rancher
Posts: 5116
82
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 9708
43
Android Google Web Toolkit Hibernate IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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

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


Nice discussion.

I think that the question that I put should have been a bit more clear.
 
Why is the word "abbreviation" so long? And this ad is so short?
Smokeless wood heat with a rocket mass heater
https://woodheat.net
reply
    Bookmark Topic Watch Topic
  • New Topic