• 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:
  • Tim Cooke
  • Campbell Ritchie
  • Paul Clapham
  • Ron McLeod
  • Liutauras Vilda
Sheriffs:
  • Jeanne Boyarsky
  • Rob Spoor
  • Bear Bibeault
Saloon Keepers:
  • Jesse Silverman
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
Bartenders:
  • Piet Souris
  • Al Hobbs
  • salvin francis

which is fastest

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

A programmer needs his application to support a collection that will allow the fastest possible traversal of extended travel itineraries.In addition ,the application must support the fastest possible traversal of all customers based on the order in which they applied for discount cards.Which class best support these requirements?(choose all that apply)
A) java.util.Vector
2) HashSet
3)TreeSet
4)HashSet
5)ArrayList
6)LinkedList
7)LinkedHashList


Answer given is ArrayList and LinkedHashSet.
Can anyone please explian the logic ??As per my knowledge LinkedList is fastest because its elements have doublylink one to their next elements and one to their previous elements..
 
Ranch Hand
Posts: 262
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I think that while posting questions copied from somewhere, you'd like to QuoteYourSources, cause I think it's not an optional thing at Coderanch.

Abhishek KumarSoni wrote:Can anyone please explian the logic ??As per my knowledge LinkedList is fastest because its elements have doublylink one to their next elements and one to their previous elements..



Traversing through an ArrayList would be faster than traversing through a LinkedList cause in the case of an ArrayList you can directly access the list element at any position without having to traverse through the list either from the beginning or from the end. On the other hand, in the case of a LinkedList, to reach a certain element, you traverse the list from one of the two ends of the list.

Following is what the API docs say about the LinkedList.

Oracle docs wrote:Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.



Granted you can invoke the index based get method in the case of a LinkedList also, but that is just an abstraction.

ArrayList elements can be directly accessed via their indices. Also remember that ArrayList also implements the RandomAccess interface. It's a marker interface. You can read about it here.


This is wrong.
 
Heena Agarwal
Ranch Hand
Posts: 262
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Actually whatever I said earlier are general things but they are not applicable in the context of the question. So I've striked it off.

I think the question is not clear. I think the answer should be just the LinkedHashSet.

Where have you copied this question from?
 
Heena Agarwal
Ranch Hand
Posts: 262
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Anyway, I'll pass cause I'm not sure why the answer has an ArrayList also. Fastest means there should be only one right answer. At least that's what I think. Also even other options could be applicable if more details were specified. But with just the given details, I think I would have chosen a LinkedHashSet only.
 
author
Posts: 23909
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Heena Agarwal wrote:Anyway, I'll pass cause I'm not sure why the answer has an ArrayList also. Fastest means there should be only one right answer. At least that's what I think. Also even other options could be applicable if more details were specified. But with just the given details, I think I would have chosen a LinkedHashSet only.




Agreed. "fastest" is a superlative form of the word "fast", which of course, should state an absolute. Debating whether there should only be two answers, or more answers, does seem weird.

Henry
 
Abhishek KumarSoni
Ranch Hand
Posts: 61
Firefox Browser Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Heena Agarwal wrote:I think that while posting questions copied from somewhere, you'd like to QuoteYourSources, cause I think it's not an optional thing at Coderanch.

Abhishek KumarSoni wrote:Can anyone please explian the logic ??As per my knowledge LinkedList is fastest because its elements have doublylink one to their next elements and one to their previous elements..



Traversing through an ArrayList would be faster than traversing through a LinkedList cause in the case of an ArrayList you can directly access the list element at any position without having to traverse through the list either from the beginning or from the end. On the other hand, in the case of a LinkedList, to reach a certain element, you traverse the list from one of the two ends of the list.

Following is what the API docs say about the LinkedList.

Oracle docs wrote:Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.



Granted you can invoke the index based get method in the case of a LinkedList also, but that is just an abstraction.

ArrayList elements can be directly accessed via their indices. Also remember that ArrayList also implements the RandomAccess interface. It's a marker interface. You can read about it here.


This is wrong.



First of all a heartfuly thanks to you .I learnt a lot from your notes.even this striked notes teach me a lot.
Second I copied this question form K& B master exam.You are right that when it comes to fastest there should be only one answer but in question in was mentioned that select two answer.So it was expecting fastest and second fastest.
Third Can you please explain me why LinkedHashSet is answer?
Fourth you said that an ArrayList support faster traversing than LinkedList because it supports random access but when it comes to traversing you will traverse form initial to final there is no need of random access.In this way i think Linked List should be faster because it has links to their next elements..
If you want i can also post k&B explanation for it.Here is the explanation

E and G are correct.ArrayList provides the fastest iterations through collections that can have duplicates are common in extended itineraries.LinkedHashSet provides the fastest iteration through a (no duplicates ) set wherer you care about the order in which entries were added
A,b,C,D,f are incorrect based on the above explaination

 
Sheriff
Posts: 3837
66
Netbeans IDE Oracle Firefox Browser
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

A programmer needs his application to support a collection that will allow the fastest possible traversal of extended travel itineraries.In addition ,the application must support the fastest possible traversal of all customers based on the order in which they applied for discount cards.


That really feels like an artificial requirement. If you do at least a minimal processing of the items you iterate over, the cost of the iteration will be probably negligible compared to the cost of the processing. You'd also need to keep millions of records in memory to really feel the effect of choosing the most efficient collection in terms of iteration, which is also somewhat weird - in real world, the records would be stored in a database and the cost to retrieve them from there will be many orders of magnitude higher than the iteration costs. In my opinion it is unfortunate that questions like this appear in exams, as they're completely detached from the real world -- iteration speed is really one of the least important criteria when choosing a type of collection for my program.

Abhishek KumarSoni wrote:Can anyone please explian the logic ??As per my knowledge LinkedList is fastest because its elements have doublylink one to their next elements and one to their previous elements.


Have a look at this discussion. Mike Simmons posted an amazing test there, which can be easily tweaked to allow testing the iteration speed over a LinkedHashSet (remember a set cannot hold duplicate values!). The LinkedList and LinkedHashMap are a lot slower than an ArrayList on my machine (using JDK 7, I should also say).

If you really want to see why, you'd probably have to have a look at the implementations. Sometimes the library classes do a lot of (important!) work which is not immediately apparent.

(Edit: some of the effect could also be caused by memory caching - data in an arraylist occupy one continuous segment of memory and during iteration are traversed in a predictable pattern, for which CPU caches have been optimized. Data in a linked list generally are scattered randomly in memory and even during simple iterations are accessed in ways the CPU caches are not programmed to deal with. CPU cache hit or miss constitutes a huge difference.)
 
Heena Agarwal
Ranch Hand
Posts: 262
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks Henry, and Martin.
 
You showed up just in time for the waffles! And this tiny ad:
Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop
https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton
reply
    Bookmark Topic Watch Topic
  • New Topic