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

Summer 2003 Final Exam Review: Optimization


a. Identify a use where Arrays are the best choice, where Bags are the best choice, and where Dictionaries are the best choice.

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

b. For figuring out if an element is in the Collection, Sets are much, MUCH faster than Arrays. Why?

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

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 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

d. If my Squeak program is slow how can I find out what parts are taking the most time?

You can find out by using MessageTally and TimeProfileBrowser. ~Sabina Karkin

e. Should you worry about speed when doing the design of your program? Why or why not?

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

Link to this Page