Pete Kruckenberg's Perfect World

Probably a good thing I've gone back to programming full-time.

Posted by pete at 12:54 PM

January 20, 2007

Updates on recent posts

A few updates on recent posts:

Posted by pete at 8:08 AM

January 15, 2007

Adjusting algorithms for dynamic languages

One of my college Computer Science classes introduced me to Sedgewick's Algorithms in C. Though after a decade I don't remember specifics of the class, I regularly find myself applying the principles I learned, evaluating the cost of each way a problem can be solved (and once in a while pulling the book from my reference library).

A Perl program I was working on recently seemed like a textbook case to apply Algorithms. After some testing I realized that though the fundamentals might be the same, Algorithms in Perl would be quite different from Algorithms in C.

The program required dropping the smallest value from a random list of numbers if it was more than 50% smaller than the next-smallest value, and similar for the largest value on the list.

Two possible algorithms came to mind. First would be to run through the list and find the two smallest and two largest values, then compare them and delete as necessary. Another option would be to sort the list, then look at the first two (smallest) and last two values (largest), and delete as necessary.

Sedgewick says sorting takes at least N log N time, while a sequential search takes only N / 2, so the first option seems the best. I was working with a short list (~200 values), so could easily be done in memory. (Of course, you might be wondering why I'm going through all of this when it's probably not noticeable which I use on a small list--don't spoil the fun). So I hacked up both implementations, and iterated each 100,000 times to amplify the difference:

Sequential search: 34.75 seconds
Sort: 7.85 seconds

Surprising, kind of (more in a moment). For comparison, I implemented the same thing using D, a successor to C/C++ (and with similar performance):

Sequential search: 0.566 seconds
Sort: 3.47 seconds

Sedgewick predicts that the sort method would be around 4.6x slower than sequential search, that's pretty close to the results in D. But Perl is almost the opposite (search 4.4x slower than sort).

Explanation? Not suprisingly, Perl implements sort in C (or maybe C++) using quicksort or mergesort. From the perlfunc manpage

Perl 5.6 and earlier used a quicksort algorithm to implement sort. That algorithm was not stable, and could go quadratic. (A stable sort preserves the input order of elements that compare equal. Although quicksort's run time is O(NlogN) when averaged over all arrays of length N, the time can be O(N**2), quadratic behavior, for some inputs.) In 5.7, the quicksort implementation was replaced with a stable mergesort algorithm whose worst case behavior is O(NlogN).

All of this leaves me wondering how the principles from my algorithm class apply to dynamic languages (where's Algorithms in Perl--maybe Sedgewick's book on Java would be a start). Or maybe algorithms and machine performance aren't such a big deal anymore, and I should worry more about cookbooks, patterns and developer performance.

Posted by pete at 8:33 PM

January 10, 2007

Surprise -- DST comes early this year

A question today about plans for Daylight Saving changes came as a bit of a shock. I'd forgotten that dates for Daylight Saving Time (in the US) change this year. DST starts 3 weeks earlier (2^nd Sunday of March--March 11--instead of 1^st of April) and ends a week later. This changed in 2005 (I vaguely remember thinking at the time how far off 2007 was), but doesn't seem to have gotten a lot of attention.

Network/system admins have some work to do in the next couple of months (and any programmers who've unwisely hard-coded DST). Microsoft has a page about patch release plans, though older Windows requires a manual process. Looks like Linux distros have been updating (my Gentoo and Ubuntu machines both work), but any older releases may require manual updating of zoneinfo files.

While testing one of my Linux machines, I got an unexpected error:

$ date -d"03/11/2007 01:59:00"
Sun Mar 11 01:59:00 MST 2007
$ date -d"03/11/2007 02:00:00"
date: invalid date `03/11/2007 02:00:00'
$ date -d"03/11/2007 03:00:00"
Sun Mar 11 03:00:00 MDT 2007

Was somehow expecting date to convert 2am for me, had never thought about how 2am-2:59am does not exist on the day you change to DST (at least, not in timezones that switch). (On the other hand, 1am-1:59am happen twice when switching back to Standard time).

Update: Looks like OS X (10.4.8 fully-patched) is also updated (looks like almost a year ago).

$ date -r 1173603599
Sun Mar 11 01:59:59 MST 2007
$ date -r 1173603600
Sun Mar 11 03:00:00 MDT 2007

Posted by pete at 5:09 PM

January 2, 2007

An interesting mix (of oil and water, kind of)

By coincidence, I happened to watch or read An Inconvenient Truth and State of Fear over the last month. They're both interesting and entertaining (I wish more Powerpoint presentations were like Al Gore's), and highly opinionated in a subtle way that doesn't often detract from the entertainment.

I picked up State of Fear because it was Crighton, had no idea what it was about (a perspective on global warming that's raised some controversy). Not knowing anything about it (even the back cover doesn't give it away), I started reading it after watching half of An Inconvenient Truth. Sure made the second half of the slide show much more interesting and raised a lot more questions (even got me to spend a few hours looking at climate data at NOAA and some other places).

This coincidental mix ended up generating more questions than answers, but more than anything reminded me of lessons (as far back as middle school) in critical thinking and specifically in examining data and charts carefully, and not just accepting the conclusions the presenters advocate. (Was interesting to see Gore and Crighton frequently using the same data and charts to make opposing points.)

(As I wrote this, I realized I also recently read The Davinci Code and a counterpoint by some religious academics at BYU, which soundly debunked every "wow, I never knew that" from Davinci Code.)

The next movie I watched was Who Killed the Electric Car?, Any suggestions on a counterpoint to this one?

Posted by pete at 2:31 PM