Exercise 19: Improving Performance

This is a mostly video exercise where I will demonstrate improving the performance of the code you've written so far, but first you should attempt it. You've analyzed how slow and fast the code is from Exercise 18, so now it's time to implement some of your ideas. I'll give you a quick list of things to look for and change when fixing simple performance problems:

• Loops inside loops repeating calculations that can be avoided. The bubble sort is the classic case of this, and that's why I taught it. Once you can see how terrible bubble sort is compared to other methods you'll start to recognize this a common pattern to avoid.

• Repeatedly calculating something that doesn't really change or can be calculated once during the change. The use of a count() function in the sorting.py and other data structures is a great example of this. You can keep track of the count inside the functions to the data structure. Every time you add, you can increase it and every time you remove, decrease it. There's no need to go through the whole list every time. You can also use this pre-calculated count to improve the logic of other functions by checking for count == 0.

• Using the wrong data structure for the job. In the Dictionary I'm using the DoubleLinkedList as a demonstration of this problem. A Dictionary needs to have random access to element, at least in the list of buckets. Using a DoubleLinkedList with DoubleLinkedList inside means every time you want to access the nth element you have to go through all elements up to n. Replacing this with a Python list would vastly improve the performance. This was an exercise in using your existing code to craft a data structure from simpler data structures so not necessarily an exercise in making the best Python Dictionary (it already has one).

• Using the wrong algorithms on data structures. Bubble sort is obviously the wrong algorithm (never use that again), but remember how merge sort and quick sort are better, depending on the data structure? Merge sort is great for these kind of linked data structures but not as good on arrays like Python's list. Quick sort is better on a list but not really as good on linked data structures.

• Not optimizing for common operations in the best place. In the DoubleLinkedList you'll frequently start at the beginning of a bucket and search the slots for a value. In the current code these slots are simply added as they come in, and that may be random or not. If you adopted a discipline of sorting these lists on insert, then finding an element would be easier and quicker. You could stop when a slot's value is greater than what you're looking for because you know it's already sorted. Doing this makes inserts slower but speeds up nearly every other operation, so choose the right design for the job. If you have a need to do tons of inserts, then this isn't smart. But if your analysis shows you're doing few inserts but many accesses, then this is a way to speed it up.

• Hand rolling your own instead of using existing code. We're doing exercises to learn data structures, but in the real world you would not do this. Python already has great data structures that are built into the language and optimized. You should use those first, and if a performance analysis says your own data structure would be quicker then write your own. Even then you should look up an existing data structure someone else has already proven works instead of rolling your own. In this exercise, write a few tests that compare your Dictionary and lists to the Python built-in types to see how far off you may be by comparison.

• Using recursion in a language that's not good at it. The merge_sort code can be broken by simply handing it a list that's bigger than the Python stack. Try giving it something insane like 3000 elements and then slowly bring that down till you find the sweet spot that causes Python to run out of stack. Python doesn't do certain recursive optimizations, so using recursion without special considerations is going to fail like this. In this case, rewriting the merge_sort to use a loop would be better (but much more difficult).

These are some of the big wins you should have discovered during the analysis in Exercise 18. Your task now is to attempt to implement them and improve the performance of this code.