5 ms·

To be precise, the post says that only 10% of programmers can write it correctly without testing. I agree that this is an interesting statistic, however the ind

To be precise, the post says that only 10% of programmers can write it correctly without testing. I agree that this is an interesting statistic, however the industry has been deprecating implementing an entire algorithm in one go in favour of implementing algorithms incrementally. Were I to write it without testing I would probably write it incrementally and try to perform the testing in my head as I went along. It feels very retrograde to try to write the whole thing out and only then start thinking about off-by-one errors, computer arithmetic issues, and other edge cases.

RiderOfGiraffes 17y ago
Of course you shouldn't just write the whole thing out and then start to think about the errors. And these days most code is developed incrementally. However, not all code is developed incrementally, testing miniscule details on the way. Some code is written perhaps 20 lines at a time before testing. Binary search is only about 20 lines, my implementation is significantly less. So there are cases where 20 lines are written, then tested. The thought experiment here is to assume that this is one of those cases, one instance of which there are probably 5 or 10 in a moderate sized project. Places where people perhaps got a little lazy, it was obviously easy, or didn't bother following the full TDD. And as I say in a comment elsewhere, only 1 in 3 of the people who tested passed my test suite. Your point is valid, but misses some of the point of the article, and the exercise.
- raganwald 17y ago
  Well I wouldn't say the point of the exercise and my point are entirely disconnected, perhaps the point of the exercise is to remind people that the size of their increments is really driven by the complexity of the test suite and not by the expected length of the code. It's an idea I explored very poorly in an old blog post: http://github.com/raganwald/homoiconic/blob/master/2009-06-02/functional_complexity.md#readme http://github.com/raganwald/homoiconic/blob/master/2009-06-0...
- hammerdr 17y ago
  I think that writing a binary search algorithm without tests is evidence of a poor programmer (or, at the very least, poor programming practice; there are talented programmers out there that can just sling code). This is a difficult and, as the sibling comment noted, error prone algorithm. These types of problems are poster children for TDD and testing. There is under 20 lines of code but several ways to make logical errors. If we test drive the code, we can ensure that the algorithm performs exactly how we want it to.
  - queensnake 17y ago
    I hate to break it to you but you'll fail interviews at the better companies with that attitude(1). No matter much support your work methods give you, you have to be able to hold and work with a few moving parts in your head at once, correctly. (1) Don't ask me how I know :)
    - hammerdr 17y ago
      In my experience, this isn't true. In fact, my 'attitude' of approaching work like a craftsman has served me very well in job interviews (even landing me opportunities at pie-in-the-sky type of jobs).
cschneid 17y ago
It feels like a totally made up problem: "Here's a binary search algo description, implement it perfectly without testing". That's not even close to how developers work, and he amplifies the disconnect with the real world by choosing a problem known for it's boundary and off-by-one risks.
- DLarsen 17y ago
  While this scenario may not allow developers to work like they normally do, I think the author's point is that a simple binary search isn't that complicated. A decent dev should still be able to a pretty good job despite those artificial constraints.
  - brazzy 17y ago
    And the author is simply wrong about his point (if that is indeed his point). A binary search is that complicated. It just doesn't look like it until you've considered all the possible edge cases, and chances are that most "decent devs" will miss some and be part of the 90%.
    - MikeTaylor 17y ago
      Speaking as the author: his point, if any, is more along the lines that if we need a test-as-you-go approach to get something this simple to work, it's no wonder we have problems when we have to implement something that's actually complex. Also: no amount of test-drivenness can save you from just not grokking the problem (as Peter Norvig's Sudoku solver showed ... er, by counter-example.)
      - darthpanda 17y ago
        It's an interesting problem. People miss the point - that programmers are missing the basics and not really thinking the problems through, relying on our tools to think for us. Too many of us are hackers by day, myself included. A binary search just exposes the weakness.
      - 17y ago
jheriko 17y ago
"however the industry has been deprecating implementing an entire algorithm in one go in favour of implementing algorithms incrementally" I dunno - for something as simple as a binary search there is nothing to increment. Maybe I misunderstand and you meant "incremental" as in where you write a whole algorithm, make sure it works, and then improve it (optimise/remove bugs/add features - not finish it)? "It feels very retrograde to try to write the whole thing out and only then start thinking about off-by-one errors, computer arithmetic issues, and other edge cases." Yeah... that is backwards. You should think of these things in advance, and if you have experience, you might have had to deal with them already. Binary search is especially simple - if you get the algorithm wrong I'm inclined to believe you are inexperienced, but if you just make typos and such, well... I'd expect that from anyone. Then again all the rapid application development options today mean that anyone can use a binary search without writing one... or even write complete software with no real understanding of how it works. Maybe I'm just out of date?
- raganwald 17y ago
  > for something as simple as a binary search there is nothing to increment. Maybe I misunderstand and you meant "incremental" as in where you write a whole algorithm, make sure it works, and then improve it (optimise/remove bugs/add features - not finish it)? I strongly suspect--and I am not being sarcastic or falsely modest--that I am not up to scratch as far as programming is concerned. I almost always get stuff like this wrong when I implement it. My code breaks for empty lists, or with just one element, or lists with an odd number of elements, or something else I can't imagine. Exposure to recursive algorithms has taught me to build this kind of thing up from simple cases like an empty list or a list with one element. So yes, I really would write a version that works for the empty list, a version that works for either the empty list or just one element, and go from there.
  - eru 17y ago
    You'll love "How to Design Programs" (http://www.htdp.org/ http://www.htdp.org/), they put a lot of emphasis on structural recursion.

RiderOfGiraffes 17y ago

Of course you shouldn't just write the whole thing out and then start to think about the errors. And these days most code is developed incrementally. However, not all code is developed incrementally, testing miniscule details on the way. Some code is written perhaps 20 lines at a time before testing. Binary search is only about 20 lines, my implementation is significantly less. So there are cases where 20 lines are written, then tested. The thought experiment here is to assume that this is one of those cases, one instance of which there are probably 5 or 10 in a moderate sized project. Places where people perhaps got a little lazy, it was obviously easy, or didn't bother following the full TDD. And as I say in a comment elsewhere, only 1 in 3 of the people who tested passed my test suite. Your point is valid, but misses some of the point of the article, and the exercise.

raganwald 17y ago
Well I wouldn't say the point of the exercise and my point are entirely disconnected, perhaps the point of the exercise is to remind people that the size of their increments is really driven by the complexity of the test suite and not by the expected length of the code. It's an idea I explored very poorly in an old blog post: http://github.com/raganwald/homoiconic/blob/master/2009-06-02/functional_complexity.md#readme http://github.com/raganwald/homoiconic/blob/master/2009-06-0...
hammerdr 17y ago
I think that writing a binary search algorithm without tests is evidence of a poor programmer (or, at the very least, poor programming practice; there are talented programmers out there that can just sling code). This is a difficult and, as the sibling comment noted, error prone algorithm. These types of problems are poster children for TDD and testing. There is under 20 lines of code but several ways to make logical errors. If we test drive the code, we can ensure that the algorithm performs exactly how we want it to.
- queensnake 17y ago
  I hate to break it to you but you'll fail interviews at the better companies with that attitude(1). No matter much support your work methods give you, you have to be able to hold and work with a few moving parts in your head at once, correctly. (1) Don't ask me how I know :)
  - hammerdr 17y ago
    In my experience, this isn't true. In fact, my 'attitude' of approaching work like a craftsman has served me very well in job interviews (even landing me opportunities at pie-in-the-sky type of jobs).

cschneid 17y ago

It feels like a totally made up problem: "Here's a binary search algo description, implement it perfectly without testing". That's not even close to how developers work, and he amplifies the disconnect with the real world by choosing a problem known for it's boundary and off-by-one risks.

DLarsen 17y ago
While this scenario may not allow developers to work like they normally do, I think the author's point is that a simple binary search isn't that complicated. A decent dev should still be able to a pretty good job despite those artificial constraints.
- brazzy 17y ago
  And the author is simply wrong about his point (if that is indeed his point). A binary search is that complicated. It just doesn't look like it until you've considered all the possible edge cases, and chances are that most "decent devs" will miss some and be part of the 90%.
  - MikeTaylor 17y ago
    Speaking as the author: his point, if any, is more along the lines that if we need a test-as-you-go approach to get something this simple to work, it's no wonder we have problems when we have to implement something that's actually complex. Also: no amount of test-drivenness can save you from just not grokking the problem (as Peter Norvig's Sudoku solver showed ... er, by counter-example.)
    - darthpanda 17y ago
      It's an interesting problem. People miss the point - that programmers are missing the basics and not really thinking the problems through, relying on our tools to think for us. Too many of us are hackers by day, myself included. A binary search just exposes the weakness.
    - 17y ago

jheriko 17y ago

"however the industry has been deprecating implementing an entire algorithm in one go in favour of implementing algorithms incrementally" I dunno - for something as simple as a binary search there is nothing to increment. Maybe I misunderstand and you meant "incremental" as in where you write a whole algorithm, make sure it works, and then improve it (optimise/remove bugs/add features - not finish it)? "It feels very retrograde to try to write the whole thing out and only then start thinking about off-by-one errors, computer arithmetic issues, and other edge cases." Yeah... that is backwards. You should think of these things in advance, and if you have experience, you might have had to deal with them already. Binary search is especially simple - if you get the algorithm wrong I'm inclined to believe you are inexperienced, but if you just make typos and such, well... I'd expect that from anyone. Then again all the rapid application development options today mean that anyone can use a binary search without writing one... or even write complete software with no real understanding of how it works. Maybe I'm just out of date?

raganwald 17y ago
> for something as simple as a binary search there is nothing to increment. Maybe I misunderstand and you meant "incremental" as in where you write a whole algorithm, make sure it works, and then improve it (optimise/remove bugs/add features - not finish it)? I strongly suspect--and I am not being sarcastic or falsely modest--that I am not up to scratch as far as programming is concerned. I almost always get stuff like this wrong when I implement it. My code breaks for empty lists, or with just one element, or lists with an odd number of elements, or something else I can't imagine. Exposure to recursive algorithms has taught me to build this kind of thing up from simple cases like an empty list or a list with one element. So yes, I really would write a version that works for the empty list, a version that works for either the empty list or just one element, and go from there.
- eru 17y ago
  You'll love "How to Design Programs" (http://www.htdp.org/ http://www.htdp.org/), they put a lot of emphasis on structural recursion.