Saturday, December 22, 2007

O for Oxygen, 0 for Zero

[reading: Bjørn Lomborg, "Cool It: The Skeptical Environmentalist's Guide to Global Warming"; recently Charles Stross, "The Jennifer Morgue"]

Shocking. The reporting of science in the media has always been pretty rubbish, but the BBC News website can't even spell CO2 correctly.

I'd let them off not doing the subscript correctly, even though it's not exactly difficult to do <sub>2</sub> or &#x2082; for '₂' (U+2082).

But not being able to spell "O" correctly is just impressively awful. And it's endemic.

Tuesday, September 25, 2007


[reading: Michael Spivak, "Calculus"]

Bugger. It turns out that the Apple rep who told me on the phone that the new iPod Classic would work with Mac OS X 10.3.9 was lying.


I don't really want to have to buy Mac OS X 10.4. I particularly don't want to have to buy 10.4 a mere month before 10.5 comes out. It's especially annoying as I spent a while cleaning up my music library and getting album art for everything in anticipation of the Arrival of the New Toy.

So I guess I've got an expensive paperweight for the next month or two (until 10.5 comes out).

Monday, June 11, 2007


So here's today's random question, apropos of, er, nothing. What's the performance of the following incredibly-poor algorithm for randomly permuting a list of numbers?

def bogo_permute(in_list):
    N = len(in_list)
    out_list = []
    # Keep track of whether we have dealt with each element of the input list
    seen = [False] * N
    for iteration in range(N):
        while True:
            which = randrange(N)
            if not seen[which]:
                seen[which] = True
    return out_list

There are N selections needed for the output list. The first time through, the randomly selected entry from the input list will definitely not have been processed already, so it can be transferred across to the output list. The second time through, there's a chance that the random selection process will select the same entry again; for later iterations, this chance of selecting something that has already been selected will get higher and higher. So, on average, how many of these repeated picks are needed?

Given a coin that comes up heads with probability p (and so tails with probability q=1-p), what's the average number of coin tosses needed before the first heads comes up?

As an example, imagine that the first head turns up on the fourth toss. This means that the sequence of tosses is TTTH. The probability of this sequence of coin tosses is then q3p = (1-p)3p. This is easy to generalize:

Number of TossesSequenceProbability

We want the average number of tosses needed to get a head, also known as the expected value. This is a sum of the each possible value multiplied by the probability of that value occurring. In other words, the average number of tosses needed is:

(1*(probability of heads on first toss) + 2*(probability of first heads on second toss) + 3*(probability of heads on third toss) + …)

Put into maths, this means that the average number is an infinite sum: Σm=1 m (qm-1p). From a trusty binomial expansion, the Σm=1 m qm-1 part pops out as (1-q)-2, and since q=1-p this means that the whole thing simplifies down to just 1/p.

(This seems reasonable: for a fair coin, it takes an average of 2 throws to get a head; for a coin that only comes up heads one time in a hundred, it takes an average of a hundred throws.)

So back to the original problem. For the i-th selection (with i running from 1 to N), the chance of picking an array entry that is still there is p=(N+1-i)/N, and so the average number of picks needed is N/(N+1-i). The first selection needs N/N = 1 attempt, the second selection needs N/(N-1) attempts, the third selection needs N/(N-2) attempts, …, the last selection needs N/1 = N attempts (on average).

Taken together, this means that the average number of random picks for the whole process is Σi=1N N/(N+1-i). Rearranging (with j=N+1-i) this is the same as N Σj=1N1/j, which includes a partial sum of the harmonic series, known as a harmonic number HN. In the large N limit, the harmonic numbers tend to HN ≈ ln(N) + γ (where γ is a constant), and so the asymptotic behaviour of the algorithm is O(N ln(N)).

So it's bad, but not quite as bad as I'd expected (I'd guessed it would be O(N2)).

Friday, May 04, 2007


[Edit, Feb 2008: fixed typo—changed extra_content to extra_context]

Today's neat Django trick: getting the create_update generic views for a model to display entries from a subsidiary model in-line—like the admin interface does when you add edit_inline=models.TABULAR.

The (oldforms) Form object that gets generated by the create_update view already has most of the required gubbins inside it; we just need a few extra steps to get at it:

  1. In, set an extra_context argument for the view to be a dictionary that contains inline_related_objects:
     {'inline_related_objects': model._meta.get_followed_related_objects(None) } 
  2. In the template, include a loop to pull in all of the related objects:
     {% for related_object in inline_related_objects %}{% edit_inline related_object %}{% endfor %} 
    within the <form> tag.
  3. Since the edit_inline template tag is not a built-in Django tag, the template also needs to load up the admin_modify extension:
     {% load admin_modify %} 
  4. Make local copies of the relevant admin templates (such as admin/edit_inline_tabular.html and widget/foreign.html) and tweak appropriately.

Of course, I didn't figure this out until after I'd spent a couple of hours dismantling the admin interface code with a view to stealing the relevant bits. Roll on the Django book.

Saturday, April 14, 2007

The Joy of UNIX

UNIX credo: you can do anything from a single command line (as long as the line is allowed to be arbitrarily long).

Case in point: generating a white noise audio file

sox -t sl -r 44100 -c 2 /dev/zero \
-r 44100 -c 2 -w whitenoise.wav synth 10:00 whitenoise vol 0.6 fade q 10 10:00 10

Friday, March 16, 2007

Magic Number

And the number is: 978-1-84753-300-5.

Sunday, February 25, 2007

The Spine is Evil

[reading: Skippy Blair, "Disco to Tango and Back"; recently: Simon Lovell, "How To Cheat At Everything"]

Drat; forgot to add extra space on the inside margins of my current typesetting project, so I had to go back through all of the chapters and re-set everything. Like the man said, the spine is evil.