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

Sp00 Final Exam Review: Choosing your collection objects

See Final Exam Review - Sp2000

b) Sets are faster for searching purposes compared to Arrays, since arrays do element by element iteration looking for the element, while elements in Sets are stored in a hash table, and therefore the lookup for an element can take considerably lesser amount of time.

Sherry
"faster for searching" - Let's be specific. Let's say you want to find item #432 – which is faster, Sets or Arrays? Now let's say you want to find the first item > 500 and 600. Which? Mark Guzdial
for finding item #432 : use set b/c you can hash to it immediately. for finding item based on criteria: use array b/c iteration is needed, and Arrays are much faster for iteration then a hash -Stephen Belknap

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

c) OrderedCollections are slower than arrays when adding elements since an OrderedCollection doubles its size everytime an element is added just like a Java Vector. OrderedCollections, on the other hand, are almost the same speed as arrays (since OC is an array) when doing iteration up the elements, considering they are the same objects. I am not sure if the speed of an OrderedCollection and Arrays are similar when removing an element. Mark, can you help here?
OrderedCollections are slower only when first initialized. This is because it does not have a static size, requiring some computations to be done which is not needed in Arrays.

Ryan Blane

If OC's doubled their size with every insertion, they'd be really slow and huge. Mark Guzdial



OC's are slow only when you need to grow their size. So, if you init it with say... 1000 elements, then you add 1001, it'll be slow b/c it'll double its internal array. this internal copying takes time, which is your performance hit. Outside of growing, they are comparable to Arrays

Note: There are two parts there – growing and copying. Mark Guzdial


b) In responce to Mark, if you are trying to get the #432 element, then arrays would be the fastest, because you can get at elements by index very fast. (O(1) I believe). For finding a value between 2 numbers, I'm not sure. A sorted array would seem like the best bet, but if you are just asking about Sets and Arrays, I'd still go with the Array. Arrays are fast to iterate through and that would be the way to find it. Hashing would not help, you'd have no key. (So, no sets)

Not the 432nd element, but the element whose ID is #432. To find the 432nd element, yes, Arrays are O(1). But to find ID#432... Mark Guzdial

c) Ordered Collections are slower than arrays. They are much slower when they have to grow (copying all elements to a new array takes time), but they are also slower when just adding. This is due to the bounds checking that OrderedCollections must do that arrays do not. (i.e. OC's must ask themselves each add "should I grow?")

Comments?

Gary Herndon


a) Since arrays know their size from the beginning, they would be good for static data needs. They are also good if you need something in a specific order. Bags are good for times when you don't care about order. It could be used for Math programs (ie, to illustrate combinatorics or probablity). Dictionaries are like hash tables, and good for storing any kind of record that is hashed to a specific value (ie, student records hashed on student ID).

b) We weren't too sure on this one. Isn't there some kind of magic "contains" method for a Collection? You would have to traverse the array to find the value.

Susi Rathmann, jeremy, and Matt Flagg

Link to this Page