If you’re wondering why it’s been so quiet around here recently …
I’ve been working on a new site, which I and two colleagues will be maintaining, and which I think is potentially the most important thing I’ve ever done. It’s called Who Needs Access? You Need Access!, and you can read it at http://whoneedsaccess.org/
We have a problem: the majority of the research that our governments fund is not available to most people. Continue reading
20th January may seem a strange day to make a New Year’s resolution, but it’s not so much a resolution as a gradually growing realisation of what I want out of the year. Now that I’ve figured it out, I thought I might as well share it here.
When kids are growing up, adults decide what they’re going to do. And not only do we make better choices for kids than they would make for themselves, we make better choices for them than we do for ourselves. Here’s what kids do:
- Learn things (in school)
- Play sports (also in school, if not elsewhere)
- Sing and play instruments (e.g. school concerts)
- Draw and paint
- Write stories
(They also play video games and watch TV, but let’s ignore those for now because those are things that adults also do plenty of.)
All those things are fun. Adults choose them for kids because they know that they’ll enjoy themselves, that they’ll develop their creativity, that they’ll be healthy. Then having set our kids off on that trajectory, we slump in front of our computers for eight or twelve hours every day.
In 2012, I’m going to do those things, too. Why should kids have all the fun?
Thanks to all of you who have taken part in yesterday’s selection-sort challenge, and everyone who’s still submitting code. (If you haven’t yet done so but plan to, then please don’t read this article until you’ve written your code according to the rules laid down in that article, otherwise you’ll see hints that you probably don’t want to see up front.)
I promised yesterday that I’d post some ideas about a test-suite in a subsequent article: this is it.
A month ago today, I posted what’s turned out to be by far the most commented-on article on this site: Are you one of the 10% of programmers who can write a binary search?. The gist of it was that Jon Bentley, in his book Programming Pearls [amazon.com, amazon.co.uk], had found in many seminars that when professional programmers are given a high-level description of the binary-search algorithm and a couple of hours to write code that implements it, only one in ten of the offered solutions are free of bugs. An amazing number of you attempted the challenge — somewhere around 500 — and the results seemed to show a correctness rate somewhere between 10% and 50%.
Now we’re going to try the same exercise with one of the simplest of sorting algorithms: selection sort. (No Wikipedia link for now, because you might see information that you don’t want to see yet.)
The contributions to the original binary search thread continue to trickle in, and now stand at an astonishing tally of 679 comments, most of them containing code. Thanks once more to all of you who’ve attempted this challenge, and to everyone who’s commented.
In one of the more interesting comments, Darius Bacon tested a sample of 20 of the Python submissions, and found that exactly 10% of them both passed the functional test and appeared to run in O(log n) time — which of course is exactly in line with Jon Bentley’s original statistic, that 10% of the professional programmers he’d examined were able to write correct binary search code (albeit under rather different conditions). It subsequently became apparent, though, that Darius’s testing code was overly strict, and that a further two of the sampled routines did run correctly (though not necessarily in O(log n) time). Still — it’s a surprisingly low hit-rate, especially when you bear in mind that, contrary to the rules, many of the programmers did use testing to help them develop the code. (You should read the second linked comment, as it has plenty of other interesting observations, too.)
[Update, an hour or two later: as Darius Bacon points out in a comment below, I misinterpreted his results. Once the testing code had been fixed, his sample of 21 routines found 9 that passed all test, of which 6 were O(log n).]
Many, many thanks to all of you who have contributed to the astonishing response to the previous article on the difficulty of getting binary search right. I’ve never seen anything like this: in just over 24 hours since I posted the article, 541 comments have been posted, and they’re still rolling in. (That number is a bit inflated by people re-posting the same code-samples multiple times after seeing WordPress mangle their source, but even taking that into account it still amazes me.)
You guys rule. Seriously.
I have a lot to say in response to it all. Read on …
There are some programming books that I’ve read from cover to cover repeatedly; there are others that I have dipped into many times, reading a chapter or so at a time. Jon Bentley’s 1986 classic Programming Pearls is a rare case where both of these are true, as the scuffs at the bottom of my copy’s cover attest:
(I have the First Edition [amazon.com, amazon.co.uk], so that’s what I scanned for the cover image above, but it would probably make more sense to get the newer and cheaper Second Edition [amazon.com, amazon.co.uk] which apparently has three additional chapters.)