I spent some time last night working on Kata 19 (these Katas are little programming exercises, a nice programming break from writing Useful Code). This was definitely the hardest one I've done so far -- you find paths between words, where words are connected if they only differ by one letter. For example: beast to least to leant to leans to loads to loons to loops.
The algorithm I used was pretty quick. Searches take at most 0.1sec, return the shortest path, and do not block on impossible paths. It does a breadth-first search, starting from both the first and terminal words (finding where they meet somewhere in the middle).
The problem was that it was really slow to start up. Reading my dictionary of 96 thousand words took about 53sec (and 166Mb of memory) on my Athlon 650MHz PC. Once it is loaded it is really fast. Perfect for a word-path-finding-server. But I don't think this justifies a persistent server.
Here is this original code. I then set upon optimizing the start time. Here's the things that worked well:
By using Psyco I can cut the 8sec (with all the little optimizations) down to 3.5sec, using psyco.full() It only brings the original down to 41sec (and increases memory to 180Mb), which is still pretty slow. Pysco plus turning GC off gives us 11sec, which is pretty good -- it does better when we tell Psyco psyco.bind(load_words) (i.e., tell Psyco to only try to optimize the one function: 11sec vs 15sec). In contast, psyco.bind doesn't even effect our optimized load_words, only psyco.full helps there.
I'm pretty happy with the finished program. For the most part all the important, time-critical parts are already in C -- they are dictionaries, sets, and lists. These data structures make algorithm implementation in Python really easy and scalable all at once. While you could write this in C for more performance, it would take a lot of work just to get something that worked, and a lot more work to match the speed of Python's built-in data structures. Maybe a language like OCaml or Haskell could match (or beat) Python's agility and performance. I'd be curious.
For more on Python optimization: loop optimization, another anecdote, and an anecdote using images. Some specific tips, and some general tips
Just a minor nit: sets aren't in C yet. They're a 100% Python library module. If there's enough interest (and I think there is) they'll become a builtin (see http://python.org/peps/pep-0218.html).# Johannes Gijsbers
I didn't bother optimising the initial dictionary loading: instead I built a precompiled dictionary for each word-length. As graphs of linked word-nodes, they're pretty small.
[epiphany:~/Code/kata19] cmiller% ./nodef.rb ruby gold
dictionary loaded in: 0.397383s
ruby => rubs => cubs => cues => cued => cued => coed => cold => gold
261 nodes touched in 0.020318s
Erk. Just noticed the bug in the output. :)
My coworker and I had a good time with this kata.
After finishing it I created a corollary. Find the longest word chain. For example, the longest word chain for all three letter words is [asp ask ark are abe aye rye rae ray say sky ski sri uri uzi]. That took 210 milliseconds to find.
I highly recommend trying the corollary.
My longest time are for the 8 letter words. The chain is 30 words long and it takes 991 milliseconds to find.