FizzBuzz in Python
I find myself focusing on interviewing these days. On the one hand I might need to get a “real job” and will be sitting in the interviewee chair. On the other I may soon be able to hire or at least contract out some Python work and will need to evaluate a potential candidate.
FizzBuzz is one of those annoying exercises that, at least in theory, helps to evaluate how a candidate thinks. Can he or she actually do the loops and evaluation necessary to derive a correct answer? What’s their first instinct and what approach does she take to optimize her approach? Does he get stuck on some part of it?
Using lookup sets pre-generated is faster.
Well…seems like a good exercise for a rainy morning. How would I approach this in Python? My first reaction was to pre-build sets of multiples of 3 and of 5 up to 100 and then use membership comparison in evaluating if the output is a “Fizz”, a “Buzz”, a “FizzBuzz” or the raw number. Sure: the traditional logic would involve division or “mod”, but what would be the fastest way to do it?
Using Sets with Membership
Back in the day I found myself writing a lot of parsers and evaluating text to branch execution. The quickest method was to generate or embed lookup tables. Compile time rather than execution time.
Applying this to the FizzBuzz problem one can generate four Python sets each with the numbers from 1–100 that match.
Then when figuring out which is which, a number is evaluated with set membership.
I add the matching number to an output set rather than print it, because to see what’s quickest I’m going to do it (as Austin Powers says) 1 million times. Pinky pointing to the side of your mouth, of course.
The solution is a bit more complex, but is quicker than the “traditional” approach using modulo.
Using Modulo Comparison
Modulo is math. (num % 5) evaluates to 0 if there is no remainder, and hence is evenly divisible by 5. While this is somewhat expensive, it’s rarely that expensive to worry about. Unless one is writing firmware for a lower-power embedded CPU.
Using a straight-forward approach (trying to organize the “if” statements for what we know would be most frequently true):
How did this approach fare for performance:
Not too badly, but slower by about 10 seconds on average. Interestingly, when I attempted to “optimize” the code by performing the modulo comparisons just once and then using the booleans to find matches it was slower — probably because the Python runtime was not able to optimize as well.
Comparing Sets vs Modulo
So when looking at the two methods:
- Using set membership: ~40 seconds
- Using modulo compares: ~50 seconds
Would our world-changing problem solving fix the economy, feed the hungry and disrupt inefficient old-world business models? Naw. And would the extra complexity be worth the enhanced performance? For a single run, no way. But if this were an “inner loop” that is called thousands or hundreds of thousands of times, then it probably would be worth the extra lines of code. However, if the numbers were needed to evaluate were from 1 to 100,000,000 then the size of the sets and the overhead to generate them would probably negate the final run-time advantage. Unless it mattered — really mattered — for performing up to required expectations.