2010 September 19 / |j|d|a|v|i|s|@|c|a|r|l|e|t|o|n|.|e|d|u
Carleton College CS 201, Prof. Joshua R. Davis
This assignment has two goals. The first is to implement the List type discussed in class, which is similar to the built-in Python list. The second is to compare the performance of List 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 two files list.py and listtests.py electronically; you also hand in a report on paper. I recommend that you type the report. Both are due by Tuesday 11:59 AM.
List
As we've discussed in class, a List is a sequence of objects indexed from 0, like a Python list. The precise Python specification is as follows.
__init__(): Initializes an empty list.
__len__(): Returns the number of objects in the list.
__str__(): Returns a human-readable string representation of the list, from first to last object.
__getitem__(i): Returns the ith element of the list, or None if i is out of bounds.
__setitem__(i, x): Sets the ith element of the list to the given value x, or does nothing if i is out of bounds.
insert(i, x): If i is out of bounds, then does nothing. If i is in bounds, then inserts the given value x at the ith position in the list, shifting the objects that were formerly at position i, i+1, etc. to the right, thus increasing the length of the list by one.
delete(i): If i is out of bounds, then does nothing and returns None. If i is in bounds, then removes the ith object from the list and returns it; the objects to the right of position i are shifted to the left, thus decreasing the length of the list by one.
append(x): Adds the given value x to the end of the list, thus increasing the length of the list by one.
self as the first argument; this is omitted in the notation above. The five methods with underscores in their names are Python special methods. This means that you call them using special syntax provided by Python, rather than calling them by their actual names:
a = List() causes __init__() to be called; after this statement, a is a List.
n = len(a) causes __len__() to be called on the list a; after this statement, n is an integer.
s = str(a) causes __str__() to be called on the list a; after this statement, s is a string.
x = a[i] causes __getitem__(i) to be called on the list a.
a[i] = x causes __setitem__(i, x) to be called on the list a.
The first part of your assignment is to implement this List type in Python. Type it in a file list.py. Use a linked list construction, not the built-in Python list. Don't rewrite LinkedListNode; just import it from linkedlistnode.py. (That's why we made linkedlistnode.py — we're going to use it again and again.) Maintain a count of the items in the list so that __len__() is fast. Don't forget Good Python Style elements such as docstrings and a demo section.
In the rest of this assignment we'll collect data on how fast List is, compared to the built-in Python list. First I want to know how fast our List's append operation is. I suspect that its speed may depend on how many items are in the list. So I set up the following test procedure.
List of 1000 items (say). It's good to use items that are all the same, such as the integer 0.
0).
startTime = time.clock() myList.append(0) endTime = time.clock() elapsedTime = endTime - startTime
In a new file listtests.py, write some code to perform the timing test just described. My version tests Lists of up to 10000 items. Depending on how fast your computer is, you may have to adjust the specific numbers you use. There is always some small noise or error in the elapsed times. Sometimes the noise goes away if you rerun the test. If not, then you can mitigate the noise by running bigger tests. (On the other hand, you can't make your elapsed times so big that you go past the due date for this assignment.)
Now you have a bunch of data about how long it takes to append to lists of various sizes. For your paper report, make a precise graph of your data, using a spreadsheet, Mathematica, pen and paper, or whatever you like. Describe the trend using big-O notation (Section 4.2.1). Also, based on your knowledge of how List is implemented, explain why the trend occurs.
Similarly, obtain timing data for Python's list's append method. Graph your data, and describe the trend in words and in big-O notation. Which is faster at appending: List or Python's list?
Whereas appending adds an element to the end of a list, prepending adds an element to the start of a list. How do you prepend to List? To an ordinary Python list? (Hint: You don't need to write any methods.)
Just as you did for appending, obtain timing data for how long it takes to prepend to List and to Python's list, for lists of various sizes. Describe the efficiency using big-O notation. Which is faster at prepending: List or Python's list? Based on your knowledge of how List is implemented, explain why it exhibits the behavior that it does.
We've tested how long it takes to access the end of a list and how long it takes to access the start of a list. Now I want to access the middle. Specifically, how long does it take to read a value out of the very middle of the list? For example, on a list a of length 1000, how long does the operation x = a[500] take?
Obtain timing data for how long it takes to access items in the middle of List and in the middle of Python's list. Describe the efficiency using big-O notation. Which is faster? Explain why List exhibits the behavior that it does.
Make sure that list.py and listtests.py exhibit Good Python Style. Submit both files electronically, as you did for the preceding assignment. Your report, including graphs, explanations, and big-O descriptions, should be submitted to me on paper; give it to me in person, or put it in my mailbox (the one that says "Josh Davis") in the CS/Math departmental offices. These are the grading criteria:
List works (6 points).