| Arrays are good for iterating and adding. Bags are good for finding a specific element. Dictionaries are also fast for finding a specific element, and they are good for insertion, retreival and caching. ~Sabina Karkin |
| How are bags different from dictionaries? Barbara Ericson |
| Bags store the number of times an element occurs rather than store copies of that object. -Kerry |
| Right, Kerry Barbara Ericson |
| Sets are faster because they use dictionaries (which is a hashtable) to find an element. It also remembers the element once, it doesn't keep track of the duplicates. Thus, it's easier and faster to see if the element is in the collection. ~Sabina Karkin |
| How do dictionaries help you find the element fast? Barbara Ericson |
| Dictionaries have a key (which can be any object) and a value and can reference those two to find an element. ~Sabina Karkin |
| Actually you just need the key to find the value. How does a dictionary use a key to find an element quickly? Barbara Ericson |
| Dictionaries use a hash function on the key value to determine the location of an element. So, given the key, you can apply the hash funtion to the key and get back the element's location. -Kerry |
| Good answer, Kerry, Barbara Ericson |
| OrderedCollections are much slower than Arrays when inserting an element in a specific spot because Array's at:put: is a primitive, and OrderedCollection's at:put: checks bounds first. Array doesn't check for bounds. ~Sabina Karkin |
| Good start Sabina, anyone want to answer the rest? Barbara Ericson |
| OrderedCollections are almost the same speed as Arrays when accessing an element. ~Sabina Karkin |
| In my version of squeak, an OrderedCollection actually uses an array underneath rather than a linked list type structure. So they'd pretty much be the same speed. timmy |
| Yes, an ordered collection is implemented as an array. But, what is different about an ordered collection? Why don't we just use an array? Barbara Ericson |
| Ordered Collections are like Java's Vector - when they grow, they grow by a lot. This prevents constant resizing, so they are slower than Array's to grow but faster to add (most of the time). -Kerry |
| You are right Kerry about ordered collections being like Java's Vector and they do grow (default is double) in size when they need to grow. But, they wouldn't be faster to insert in than arrays. Barbara Ericson |
| Well, I was factoring in the cost of copying the array into a newer, larger array when we wanted to add an element to it. So, it's more like Arrays are faster for putting an element in it and OrderedCollections are (generally) faster for adding new elements -Kerry |
| Well, an ordered collection is using an array and does copy the old elements to the new array when it needs to grow. The big advantage to using an ordered colleciton is that you don't need to worry about it. The code is written and works well for growing the array and doing the copying. So, we usually only use arrays when we know the size. So, that is why I say an ordered collection isn't any faster for adding new elements, in fact it can be slower but that is assuming that the array is the right size. Barbara Ericson |
| You can find out by using MessageTally and TimeProfileBrowser. ~Sabina Karkin |
| You shouldn't worry about speed when doing the design of your program because you would waste a lot of time. It is better to code first and then see what parts of the code take up a long time because it might be something that you might not think takes a long time. It's easier this way. Then you simply change that part of code to make it faster. Also, at the beginning, you don't know what you are going to end up using in your code and how it will all come together, so you might waste time worrying about something taking a long time that you don't end up using. ~Sabina Karkin |
| Right, Sabina, Barbara Ericson |