Question 1: What are differences between Dictionary, Array, OrderedCollection, Bag, and Set?
All of them are sets of collection of objects.
1. Dictionary: a collection which each object has an assigned key for easy access. The key can be of any type of object.
2. Array: a collection of objects that also has key, but the key are corresponding integer as indices, and elements are of 1 uniform type.
3. OrderedCollection: a collection like a vector which has specific index and can carry different types of object at once.
4. Bag: an unordered collection which does not have any key/value specifically assign to each element for easy access. However, it does maintain the total number of elements it has (identical elements).
5. Set: an unordered collection just like Bag, but it does not maintain the total number of element been added to.
Question 2: Rank the running time of operations perform by each collection class mentioned above in an increasing order.
Array - Dictionary - Bag - OrderedCollection - Set.
Question 3: Advantages and Disadvantages
In general, array is one of the fastest data structure. It has specific index and it can put data in or take it out within a single call. However, it can only hold a uniform type of objects as elements and has a fix size which is not very efficient for dynamic storing structures.
Dictionary, on the other hand, uses a hash table to store data so it can perform insertion and provide access in constant time. Another advantage of dictionary is that it can hold different object’s type as its elements with any type of key the user can input. This certainly gives it a great flexibility in organizing object.
Bag is just another implementation of dictionary. It maintains a dictionary variable which will last through its execution cycle, and it uses the object itself as key and the number of time an element repeated as actual value. This helps to make bag a little more efficient in looking up how many time such an object had been added, but it does not provide a way to get the object with a particular key.
OrderedCollection is another implementation of arrays for which will grow to double its size every time a new element being added to. And even though its contents can be accessed via integer index keys, its memory consuming can become a very big problem when the running system has limited memory/disc’s space.
Set is the worst kind of all. It requires running time of O(n) in order to find a element within its set, output its current size, or to modify a particular element. Since it have to loop through the whole set in general to perform any particular tasks, implementing a set could mean taking a risk some developers do not want to be involved.
All in all, array and dictionary are the two best data structures to optimize Squeak’s program performance. However, choosing one over another is depended entirely on what effect each structure brings to the whole picture of a design.
Actually, arrays, just like OrderedCollections, can contain any objects in them. OrderedCollections actually do a nice job of balancing performance and memory allocation.
Link to this Page
Fall 2005 Discussion 5 last edited on 11 December 2005 at 7:39 pm by r44h79.res.gatech.edu
