a. Identify a use where Arrays are the best choice, where Bags are the best choice, and where Dictionaries are the best choice.
Arrays – when adding a lot of elements (fast), traversing every element
Bags – when you're concerned with the number of identical elements in the collection
Dictionaries – when using lookups (key value such as a hash function) to access an element from a collection
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?
OrderedCollections are much slower than Arrays when adding.
Arrays and OrderedCollections are almost the same speed when accessing an index.
OrderedCollections are slower that arrays because an OrderedCollection checks its bounds before adding and an array doesn't.
(a) Close, but some misses. (b) A set is not a sorted array. Mark Guzdial
Arrays: are the best choice when you want to index by numbers and have a fixed number of objects. Thus arrays would work really well if you are doing iterations.
Bags: as Justin said to check the number of occurences of an object in the collection.
Dictionaries: they can be indexed by actual objects. They work like hash functions so they are good when you are working with complex interactions of objects and need fast lookup.
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.
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.
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.
Bags are great when you want to just have a collection which can tell you if it has a particular type of object in it with out having to run a search.
Dictionaries are great when you need a hash table type of structure.
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