2009 April 6 / |j|d|a|v|i|s|@|c|a|r|l|e|t|o|n|.|e|d|u

Efficiency Of Array

Carleton College CS 201, Prof. Joshua R. Davis

This assignment has two goals. The first is to implement the Array ADT discussed in class, which is similar to the built-in Python list. The second is to compare the performance of Array to that of the Python list. You'll gather actual timing data and explain them using conceptual arguments.

You may complete this assignment alone or with a single partner of your choice. You hand in a file array.py electronically, and a report on paper. I recommend that you type the report. Both are due Friday April 10 at 11:59 PM.

0. Implement Array

Last Friday in class we discussed an Array ADT. An array is a list of objects indexed from 0, like a Python list. For the purposes of this assignment, the precise ADT specification is as follows. All methods that take in an index argument assume that the given index is between 0 and N - 1, where N is the length of the array.

• Array() returns an empty array.
• __len__() returns the number of items in the array.
• __str__() returns a string representation of the array — designed to mimic the Python list, using commas to separate entries and square brackets to enclose the array. For example, an array containing 'a', 'b', 'c', 'd', and 'e', in that order, would have string representation "['a', 'b', 'c', 'd', 'e']" (where the " are not part of the string).
• __setitem__(index, item) alters the array so that the object at the given index is the given item object. It does not alter the size of the array. It returns nothing.
• __getitem__(index) returns the object at the given index.
• append(item) adds the given item to the end of the array (thus enlarging the array) and returns nothing.
• insert(index, item) add the given item to the array in spot number index, shifting entries to the right to make room (and thus enlarging the array). For example, inserting 'z' at index 2 in ['a', 'b', 'c', 'd', 'e'] produces ['a', 'b', 'z', 'c', 'd', 'e']. It returns nothing.
• pop(index) removes the item at the given index (thus shortening the array) and returns the item.

len(myarray)
str(myarray)
myarray[3] = 'jen'
myname = myarray[3]

The first part of your assignment is to implement this Array ADT in Python. Type it in a file array.py. Use a linked list construction, not the built-in Python list, and maintain a self.count variable so that the array can respond to the __len__() method quickly.

Remember that you have to include self as the first argument to any Python method. This is omitted from the ADT above because the ADT doesn't know that you're going to implement it in Python rather than, say, Java or Objective-C.

1. Test Appending To Array And To Python's List

In the same array.py file, after your Array class, define a function (not a method) called timeArrayAppend. It should take in a positive integer, build an Array of that many objects, measure the time required to append one more object to the list, and return that time. (For help on timing, see Section 4.2. Remember that you are timing just a single call to append(), not the building of the whole array.)

Then, using the following code, test how long it takes to append to arrays of various sizes. I hope that the test doesn't take longer than a minute. If it seems to be taking too much or too little time, then adjust the numbers. All of your experiments in this assignment should be big enough that you can see the trend.

print "For Array append:"
print timeArrayAppend(10000)
print timeArrayAppend(20000)
print timeArrayAppend(30000)
print timeArrayAppend(40000)
print timeArrayAppend(50000)
print timeArrayAppend(60000)
print timeArrayAppend(70000)
print timeArrayAppend(80000)
print timeArrayAppend(90000)
print timeArrayAppend(100000)

Similarly, write a function timePythonAppend that performs the same test for regular Python lists. Run it for the same test cases as above. Graph your data, and describe the trend in words and in big-O notation. Which is faster at appending: Array or Python's list?

2. Test Prepending To Array And To Python's List

Whereas appending adds an element to the end of a list, prepending adds and element to the start of a list. How do you prepend to Array? To an ordinary Python list? (Hint: You don't need to write any methods.)

Just as you did for appending, write functions timeArrayPrepend and timePythonPrepend that time how long prepending a single object takes. Then collect data and describe the efficiency using big-O notation. You can make graphs, if you like, but this is not required. Which is faster at prepending: Array or Python's list? Explain.

3. Test Accessing Array And Python's List

As you did for appending and prepending, write functions timeArrayAccess and timePythonAccess to test the speed of getting an item (that is, __getitem__()) from the middle of an array, for various sizes of arrays. Collect data, describe the trend using big-O notation, and explain what is happening as well as you can.

4. Hand In Your Work

Submit your array.py file electronically, as you did for the preceding assignment. Your report, including a numerical tables and/or graphs, big-O descriptions, and explanations, should be submitted on paper. Put it in my mailbox in the Math Skills Center (directly in front of you as you enter the MSC). The MSC closes at midnight; your program file and report are both due at 11:59 PM. They will be graded based on these criteria:

• Does all of Array work? (3 points)
• Do your three pairs of test functions work? (3 points)
• Is your code clean, concise, and well-commented? (3 points)
• For the three tests are your numerical results, graphs, and discussions understandable and insightful? (6 points)