View this PageEdit this PageAttachments to this PageHistory of this PageHomeRecent ChangesSearch the SwikiHelp Guide
Hotspots: Admin Pages | Turn-in Site |
Current Links: Cases Final Project Summer 2007

Sp02 Final Exam Review: Collection Differences

a. Identify a use where Arrays are the best choice, where Bags are the best choice, and where Dictionaries are the best choice.
b. For figuring out if an element is in the Collection, Sets are much, MUCH faster than Arrays. Why?

A set is actually a sorted array and it also only stores one element if an element is added that already exists in the set. An array will store every element that is added and an array is NOT sorted. The search time is greater for an array because every element must be traversed, where as this is unnecessary with a set.

c. When are OrderedCollections much slower than Arrays? When are OrderedCollections almost the same speed as Arrays? What causes OrderedCollections to be slower?

Justin Daniel

(a) Close, but some misses. (b) A set is not a sorted array. Mark Guzdial



a.

b. Sets do not add an object if it already exists in the set. Thus if you add the same object again, the set will remain unchanged. Arrays will however, add the object more than once. Therefore sets are much faster than arrays if you want to check whether an elements exists in it or not. The entire array will have to be traversed even if the object has been found, this is not so in the case of a set.

Jai Kejriwal
Why are OC's slower than arrays when adding? Always? Just sometimes? Mark Guzdial


OC's are slower than arrays when adding. OC's double in size when they run out of room. The time it takes to double is a lot of overhead, but it doesn't happen often. Once an OC has reached a fairly constant size, OC's are almost as fast as arrays.

Also, from b) . . . Sets are hashtables.

Justin Daniel


Adding to the above answers
a. -Arrays are great for quick access when you know the location of the object you are searching for, and you don't care if there are multiples of them.

b.Sets are faster because they use a hashing function to store the elements with in it. That way when you ask it if it contains something it does the proper hashing calculation and checks for the object there. This calculation takes very little time. Arrays on the other hand have to be searched at every element in order to see if it contains the desired object.
c. As above ordered collections are slower when adding elements. They are about the same speed as arrays when it comes to accessing elements. The reason they are slower is because they have to check there bounds before adding a new element. Where as with an array the bounds are not checked.
Eric Soto



Link to this Page