« Observational Injunction | Main | Thought Experiment for AI People »
April 29, 2005
Algorithms
It’s nice that Bill is talking about retaking Algorithms after incompleting it. I have to say, Mazumdar was completely right: most days, you don’t use it at all, but on some days, it’s the difference between night and day. I think he said algorithm analysis will never get you a job, but you may lose your job if you don’t know about it. It hasn’t been that way at Matterform, but there are times when we go, “Why is this so slow?” And usually, there are two possible answers:
- The SQL statement we’re using is really bad. 9 times out of ten, this is the problem. (SQL is very fast! You just need to know how to tweak it.)
- Somebody did something really stupid
Last week, we discovered that there was a priority queue in the middle of our POP3 code. The guy who wrote it had used the naïve implementation—put all the elements into an array, and sort the array by priority after each insert. So, if I have N items, it’s going to take what, 1/2N * NlogN, just to insert all the items? So that makes it what, about O(N**2 log N)? Of course, popping is a snap, because they’re all sorted. Popping is O(1).
Then I recalled priority queues. Couldn’t recall a fucking thing about them. Pulled out my copy of “Algorithms in C++”, which really is a great book even though it’s in C++, and wrote an array-based priority queue in about an hour. This one has the property O(log N) for insertion and removal (although it maintains O(1) if you just want to look at the top item). So here are the rough numbers:
Naïve implementation: in 6 seconds, 100 items
Heap-in-array implementation: in 7 seconds, 20,000 items
I think we have a winner. :)
Sadly, I think what I mostly got out of the class is that I can recognize runtime behavior (more-or-less ;), recall the names of alternatives that we should be using, and code up an alternative and be able to tell that it’s right. But even this is a big edge over the competition (apparently).
Posted by FusionGyro at April 29, 2005 02:04 PM
Trackback Pings
TrackBack URL for this entry:
http://www.clanspum.net/~fusion/blog/admin/mt-tb.cgi/114