Thursday, May 5, 2011

Relearning Data Structures with Python

I realized the other day that I had learned about tons of data structures in class, but I've never used some of them in production. So, I set out to write simple implementations of a hash table and binary tree. After all, after I've made one in practice I'm more likely to make one when it's actually useful.

The focus in this exercise was clean implementation. Keep the code as short as possible, not sacrificing for readability. I think I've struck a good balance.

I've found that since I've learned Clojure, I'm more likely to use functional style coding in other languages. For example, here's my hash_function in Python:
Note the use of map. I was even using reduce for a while, but Python's sum led to a cleaner implementation. Also note that I'm using the decorator @staticmethod. Functional style calls for functions that have well defined inputs and outputs without side effects - declaring this method to be static explicitly shows that I am following that principle.

Compare that to how I would have written this six months ago:
The new, functional way is much cleaner. 

There are definitely many things I could add for my next steps. Some structure changing methods (dynamically allocated hash table? self balancing tree?) could be pretty cool.

You can check out the source on github. There is a tester file that shows how to use the class (and even provides some profiling code I used). To enable a tester, call it from the main function in tester.py

    No comments:

    Post a Comment