New OLPC Spin

Funny thing coincidences.. I was talking to a co-worker about the OLPC and suggesting he avoid vmware images or ISOs and that instead he should use a Fedora system and add Sugar from RPM because the ISOs that I had seen and become out-of-date or unavailable.. and then we found Sebastian Dziallas reports there is a new spin of Sugar available from Fedora. This is a customized version of Fedora that can be run as a live cd or even from a USB stick.

Downloading now..

Ruby Rocks!

About two weeks ago, I was at Nerdbooks (check them out at http://www.nerdbooks.com) and I bought a couple of great books; The Art of Debugging and Programming Ruby.

The Art of Debugging by Matloff and Salzman from Nostarch Press. I picked this up off the shelf and found a couple of things I didn't know about using gdb inside a minute so I went ahead and got it. The plan is to have it around for those late-night sessions when using gdb on some weird version of Unix (like, say, AIX) is keeping me at the office. Its also proven a good book to share with the team..

The other book is Programming Ruby by Dave Thomas from Pragmatic Bookshelf and it is gathering dust. I only got this because I may have to work with some Ruby programmers at the office and I want to find out more about the language. It seemed like a good idea at the time.. After all, Ruby rocks! Right?

Nerd Score

I just tried the Nerd Quiz and thought I was doing so-so, kind of average (missed some of the questions) so I was surprised to get this:

Faster! Faster! And Smaller!

I have been hacking some Python code in a (vain) attempt to get a working algorithm for the Netflix prize and I have something that looks promising but is slow so I have been investigating optimizing it.

I got a dramatic speed-up after I noticed that I was searching a list using index when the list was ordered and so amenable to a binary search.

Using the bisect module for this looks like:
import bisect
pos = bisect.bisect_left(sortedList, val)

Binary searches run in logarithmic which is so much better than the index method of a list which is linear, starting at the left and looking until it either falls off the other end or find a match.

Timings using timeit:

First, using index..
>>> timeit.Timer('a.index(10)', setup='a=range(0,100)').timeit()
0.50195479393005371

>>> timeit.Timer('a.index(99)', setup='a=range(0,100)').timeit()
2.3854200839996338

Now, using bisect:
>>> timeit.Timer('bisect.bisect(a,10)', setup='import bisect; a=range(0,100)').timeit()
0.63758587837219238
#Uh-oh, slower than than index by a little bit

>>> timeit.Timer('bisect.bisect(a,90)', setup='import bisect; a=range(0,100)').timeit()
0.54854512214660645
# Faster



Smaller!
The array module allows the efficient storage of basic values. I have a list of scores for each Netflix subscriber that is probably internally represented as an int or even a long int (at least 4 ytes, maybe 8) but the range of values is 1-5. When I change from list to array('B'), the memory footprint falls from 2.2Gb to 900M.. now I can run this thing on a smaller machine!

MOTD: pyprocessing

I have thought about trying multi-processing in Python before but, sometimes, the heavy lifting of building the infra-structure put me off until I found this:

http://pyprocessing.berlios.de/

Neat. Off to play with it.

Lxml and a Python Optimization Anecdote

One of my co-workers wrote a Python script to check the contents of an xml file written for an OVAL application and remarked it took nearly 48 hours to finish.

"Too slow", says I, "you must be doing something wrong".

"Make it faster then", he said.

My final version completed the same work in under 5 seconds which is an improvement of around 40000 times or 4 orders of magnitude. I was thinking about putting together a talk on optimization for the next DFW Pythoneer meeting but after looking around for information, it seems there is plenty on the web written by wiser people than me.. so instead here is a blog post.

Rules of optimization (applicable to all code, not just Python):

1. Premature optimization is the root of all evil (D. Knuth)
   
2. Make it right then make it fast: not much point in getting a wrong answer quickly.
3. Measure, don't guess. You might think you know what is fast and what is not .. and you may be surprised.
   
4. Rewrite the inner loop (Guido van Rossum). If you don't have any loops then you may not have any opportunity for improvement but otherwise most of your cpu time is spent in the innermost loop so fix that first.
5. Rethink the algorithm. Sometimes, the profiled and optimized code can still be made faster but only by accepting that you need to rethink your approach. As an example, you could check if a number is prime by dividing it by every number that is smaller than it but that would be silly.
   

Measuring Python:

1. timeit.py - a great script that ships with python, look in the lib/python directory, useful to measure small snippets.
   
2. profile - (cProfile or hotshot) collects information about the number of function calls and the time per call and accumulated time.

Using timeit, I (re-)discovered that inserting items into the front of a list is more expensive than an append and that inserting numeric items with a numeric key into a dictionary is cheaper than appending items to a list.

When I used profile, I discovered that xpath queries of lxml are expensive .. so I rewrote lookups to take advantage of knowledge of the structure of the document.

Rewrite the inner loop (or move things out of loops):

1. Prefer generators/iterators/map/reduce/filter over hand-written loops and take advantage of the C language level speed-up (and reduced chances for error)
   
2. Use opportunities for caching (need to look something up? Store the result) or pooling(re-use threads or database connections and amortize start-up costs).
3. Prefer iterators over lookups: If we know we need to process most of the contents of a list then go ahead and iterate over the entire list rather than perform multiple lookups in random order (as was the case in original problem)
   

The file that was being processed had several sections containing items that reference items in other sections - multiple many-to-one-to-many relationship that initially were discovered and resolved in the inner loop. Knowing that we will need almost every lookup, I created a cache and pre-populated it with one side of the lookup. This made a huge difference.

XML entities were discovered and then a string ID was passed to the inner loop where a query looked again for the entity and found child elements. All this was replaced with lxml iterators resulting in a huge speed-up.

Go Psyco!
Psyco is a great optimizer but doesn't work for every problem. If most of the work is done by pure Python code then you should get a great improvement but if you are using C extensions then it may not make any difference. I was using lxml which is mostly written in C and using Psyco slowed things down a little. Of course, you can pick which functions to speed up by looking at your profiler report. You do have a profiler report, don't you?

Prove It

Don't guess, test! Don't test with one set of data, try scaling up. If you are expecting linear behaviour and you don't get it then it may be time to check things. Again the output from profile will help you.

Links to Other Stuff:
Guido's essay
EffBot's example - discusses profiling
David Goodger's presentation on idomatic python

Netflix Submission in 2 lines of awk

Netflix are offering a prize if you can develop an algorithm that improves the accuracy of their suggestion system by 10%.. http://www.netflixprize.com

Some people have developed elaborate schemes based around cross-correlation and clustering etc. I submitted my first results using two lines of awk:

NF==2 {print $0}
NF==1 {print 3.4}

which just scores all movies at 3.4 and gives an RMSE of 1.16.

Using the average for each movie instead of a single number gives an RMSE of 1.0533.

Of course, this has all been done.. and I could have just surfed and found it.

There is also a python library called pyflix which lets you get past building infrastructure and onto the fun of the algorithm.

Nokia Battery

I have a Nokia 6682 phone and it's great, not just because it can run Python, but all of a sudden the battery seems to last not very long at all. So I need a new battery, a BL-5C, and that battery is available on-line for 5 dollars but is that because they are past their shelf-life? Never mind that the particular was recalled for a slight problem with catching fire.

Who can say?

The OLPC is here

I haven't been keeping with news so I was surprised and happy to find my new(est) toy on the doorstep tonight - an OLPC XO. I have been trying to put it down for several hours now so that I can take care of, well, anything else but it's fascinating. Performance wise it is not snappy but I can get on the network, download things, type in the word processor (abiword, I think) and generally fiddle around. I want to download some new apps just to see and then I am going to try and leave it alone for a while. At least overnight..


Has anyone else in Dallas (or elsewhere) received theirs?

Starting a wireless interface properly

I added WPA-PSK to my router recently (the wireless connection has been open up to now) and that immediately caused problems because my Linux laptop (running FC6) didn't want to play nice. My shiny new MacBook had no problems (no surprise there).

After some rummaging around, I found that I needed to start wpa_supplicant so I tried that using the init script but had no success. After some more poking, I edited

1. /etc/wpa_supplicant/wpa_supplicant.conf (to set the passphrase generated by wpa_passphrase)
2. /etc/sysconfig/wpa_supplicant (to change the default driver from ndiswrapper to wext

and created ifup-pre-local and ifdown-pre-local to start and stop wpa_supplicant respectively. These get called from /sbin/ifup and /sbin/ifdown and can be contain anything you want run before bringing up the wireless connection. Mine look like this:

#!/bin/bash

. /etc/init.d/functions

cd /etc/sysconfig/network-scripts
. ./network-functions

. /etc/init.d/functions

cd /etc/sysconfig/network-scripts
. ./network-functions

CONFIG=`echo ${1} | cut -d- -f2`

need_config ${CONFIG}

source_config

if [ "${TYPE}" = "Wireless" ]
then
/etc/init.d/wpa_supplicant restart
fi

Presto! My wireless interface now comes up just like it should!
Now I have to figure how to setup wpa-supplicant for when I am away from my home network..