rc3.org

Strong opinions, weakly held

Binary search implementations

A couple of friends have taken a stab at the binary search exercise and posted the results to their blogs. Check out Kellan Elliott-McCrea’s implementation and Erik Kastner’s implementation(s).

3 Comments

  1. I am not one of teh el33t 10%, but I’m not too worried about that. Two silly bugs in the first version.

    http://jacobdavies.tumblr.com/post/551617235/binary-search

    That is fairly typical first-draft code for me, that is to say, it has a lot of local variables and logging to let me check that it’s doing what I expect, and it starts by testing the terminating condition which I think leads to an extra recursive call. I wouldn’t be surprised if it still has a bug or if it’s otherwise inefficient. Despite the logging, the two bugs noted were the only ones found.

    Tracing execution with logging is distinct from a reliance on testing, in my view, because tracing is a question of knowing what you expect to see happening and checking that it actually is happening, whereas testing just says “did it work or not?”

    I kind of think that the real message of the exercise is “don’t write fiddly algorithms yourself in almost all circumstances”, which is advice I would give to just about anyone doing just about anything: unless it is absolutely essential that you implement something yourself, don’t do it. I sense a certain melancholy longing for the days of writing this kind of code yourself, which I get, but it’s a bit like lamenting the loss of widespread skill in making furniture by hand in the era of Ikea; there’s something to it, but at the end of the day, most people don’t want to make furniture by hand, they just want the chair.

    The value of software is primarily that of “making chairs”, that is, it’s the end result that matters, and to the extent that it is possible to get to that end result without risking sawing off one’s own hand, one should appreciate the wonderful advances made.

  2. Yep. I may write a binary search implementation for practice, but it would be unprofessional to use my own implementation if a perfectly good one that I don’t have to maintain is already built into the class library of whatever language I’m using.

  3. Yeah. It’s also interesting to me how little this resembles the sort of programming I actually do. And it’s not that algorithms never come up, they do all the time, it’s that they’re not this kind of thing; they’re not generally fiddly, they don’t tend to involve arithmetic, and efficiency is not usually at the top of my mind – largely because of cheap, efficient hash implementations. (“If it can’t be solved with another hash, I don’t want to solve it.”)

    So like I say, interesting exercise, but probably not related to any of the most common problems with software, so maybe not that instructive.

Leave a Reply

Your email address will not be published.

*

© 2016 rc3.org

Theme by Anders NorenUp ↑