A small triumph of explicitly readable code

Recently I was asked to write an implementation of FizzBuzz*, a new notion to me. I took, I suppose, a quarter of an hour and put together a little Python program — it worked, and I felt clever because I had found two little time-saving tactics:

1. taking care of the cases in order of how frequently they crop up (unmarked cases account for 8 in every 15; the "Fizz" case is 4 in 15, "Buzz" is 2 in 15, and the co-occurrence "FizzBuzz" is 1 case in 15);
2. taking care of the FizzBuzz case as a subset of the Fizz case.

I submitted the code yesterday and went to sleep feeling good. This morning, however, I started to wonder how many different implementations there might be, since the basic idea is not terribly complicated.

Well, there are large numbers of implementations, and I was impressed to see how many crafty one-liners people have come up with. I studied a few of them and learned a thing or two. Although I classify myself as a fox on the Archilochan dichotomy, my mind is slower than other people's, and it is my weakness as a programmer always to write as simply and explicitly as I can. When I see craftiness at work, after the initial envy subsides, I always feel I'll never catch up to it, although I usually then try to untangle what the experts have created, for my own education. I timed the various implementations, too, and mine came out far and away the slowest (results in seconds):

1
2
3
4
5
6
7
8
9

iterations =  100
<function dpb at 0x1107791b8>: 0.00968
<function tamurakoichi at 0x110779320>: 0.00067
<function anonymous at 0x110779398>: 0.00144
<function smog at 0x110779410>: 0.00158
<function chrisclark at 0x110779488>: 0.00181
<function jefallbright at 0x110779500>: 0.00158
<function anonymous2 at 0x110779578>: 0.00072
<function anonymous4 at 0x1107795f0>: 0.00171

So much for the advantages of writing clear, explicit code!

But then I looked a little more closely, and saw that most of these faster methods assembled the whole output as a string or array first, and then printed it all at once. I had been printing each line at a time, surely an expensive luxury.

So I rewrote all the implementations to generate an output-string without sending it to the console.** That allowed me to compare the results, string to string, and gave me a more equable basis for timing comparisons. And the results now?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

iterations =  100
<function dpb at 0x10a729230>: 0.00018
<function tamurakoichi at 0x10a729668>: 0.00021
<function anonymous at 0x10a7291b8>: 0.00023
<function smog at 0x10a7292a8>: 0.00021
<function chrisclark at 0x10a729320>: 0.00117
<function jefallbright at 0x10a729398>: 0.00100
<function anonymous2 at 0x10a729410>: 0.00024
<function anonymous4 at 0x10a729488>: 0.00019

iterations = 10000000
<function dpb at 0x10a729230>: 12.48893
<function tamurakoichi at 0x10a729668>: 15.50518
<function anonymous at 0x10a7291b8>: 19.88059
<function smog at 0x10a7292a8>: 72.46663
<function chrisclark at 0x10a729320>: 87.58923
<function jefallbright at 0x10a729398>: 70.65603
<function anonymous2 at 0x10a729410>: 17.89535
<function anonymous4 at 0x10a729488>: 19.54576

My painfully explicit code is also the fastest of the implementations I've examined.

Well, I feel a little better now. Readable code is vindicated!

20140518: A friend looked at this recently and suggested that use a joined list rather than string accretion, for better speed. That's what I'd do now. But when I originally wrote this, I didn't know about the poor time complexity of string concatenation. So I'm leaving it as is.

* "Count incrementally, replacing any number divisible by three with the word 'fizz', and any number divisible by five with the word 'buzz'." Wikipedia article "FizzBuzz", accessed 20121206.

** Here is my code, with the algorithm just as submitted but revised to save the printing time:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def dpb(limit = 101):
    output = ''
    for i in xrange(1, limit):
        if i%3 and i%5:
            \# neither of the special cases
            output += str(i) + '\\n'
        else:
            \# the special cases
            if not i%3:
                \# divisible by 3;
                \# we are not done yet so no linebreak
                output += 'Fizz'
            if not i%5:
                \# divisible by 5
                output += 'Buzz\\n'
            else:
                \# now add linebreak after Fizz case
                output += '\\n'
    return output

[end]