Complex List Comprehension slower than straight loop

Question

I saw an interesting solution for a programming exercise on leetcode It's not even about the problem/solution itself, so you can read it up on the link provided if you wish. However a high voted solution is this one liner:

Snippet 1

def fizzBuzz2(n):
    return  ["Fizz" * (not i%3) + "Buzz" * (not i%5) or str(i) for i in range(1, n+1)]

Snippet 2

def fizzBuzz(n):
    out = []
    for i in range(1, n+1):
        if i % 3 == 0 and i % 5 == 0:
            out.append("FizzBuzz")
        elif i % 3 == 0:
            out.append("Fizz")
        elif i % 5 == 0:
            out.append("Buzz")
        else:
            out.append(str(i))
            
    return out

However, I've expected that the list comprehension is going to beat the common loop, but when I've timed it and it wasn't the case. Even doing a dis, Snippet 2 has more instructions.

What is making Snippet 1 slow?

Answer 1

your snippet

def fizzBuzz2(n):
    return  ["Fizz" * (not i%3) + "Buzz" * (not i%5) or str(i) for i in range(1, n+1)]

performs a lot of string concatenations (even with empty strings). I traded that with an extra modulo operation which saves the concatenation and it's already faster.

def fizzBuzz3(n):
    return  ["FizzBuzz" if not i%15 else "Fizz" if not i%3 else "Buzz" if not i%5 else str(i) for i in range(1, n+1)]

and BTW on my machine, both comprehensions are faster than the "classical" approach so I get different results than you stated:

your comp: 4.927702903747559
my listcomp: 4.343341112136841
classical: 6.015967845916748

So my optimized listcomp wins (and seems to win too on your machine), even if I'm not satisfied with the extra modulo operations induced by the flow control of the listcomp)

My test protocol is performing 10000 times the operation with n=1000:

import time
start_time = time.time()
for i in range(10000):
    fizzBuzz2(1000)
print("your comp:",time.time()-start_time)
start_time = time.time()
for i in range(10000):
    fizzBuzz3(1000)
print("my listcomp:",time.time()-start_time)
start_time = time.time()
for i in range(10000):
    fizzBuzz(1000)
print("classical:",time.time()-start_time)

note that even with pre-computing the modulos in the "classical" approach, it drops to 5.375272035598755 seconds (which is good) but still worse than listcomps because of all the instructions (you also kill the listcomp speed by calling a method to save modulo computations). I guess that python is not the proper language to obtain the fastest speed in that case.

Answer 2

A lot of people already answered your question, but I want to add that there are still faster solutions. To me it seems wrong to test the numbers in hindsight, although you already know at which places "Fizz", "Buzz" and "FizzBuzz" will occur. Try this instead:

def fizz_buzz(n):
    result = []
    for i in range(1, n + 1, 15):
        result += [str(i), str(i + 1), 'Fizz',
                   str(i + 3), 'Buzz', 'Fizz',
                   str(i + 6), str(i + 7), 'Fizz', 'Buzz',
                   str(i + 10), 'Fizz', str(i + 12), str(i + 13),
                   'FizzBuzz']
    return result[:n - len(result)]

start_time = time()
for i in range(10000):
    fizz_buzz(1000)
print("fizz_buzz:", time() - start_time)

Compared to the previous answers:

your comp: 3.3942723274230957
my listcomp: 2.586350202560425
classical: 3.879168748855591
fizz_buzz: 1.6374053955078125

Answer 3

Yes, because in the comprehension all the instructions are being evaluated in each loop.

While in Snippet 2 atmost 1 if branch is evaluated. Thus, reducing the computation, and making it a faster alternative.

Answer 4

While we’re exploring implementations, here’s a fun slice one that’s faster than the single list comprehension, but not as fast as @seenorth’s solution:

from math import ceil


def fizz_buzz(n):
    result = list(range(n))
    result[::3] = ["Fizz"] * ceil(n / 3)
    result[::5] = ["Buzz"] * ceil(n / 5)
    result[::15] = ["FizzBuzz"] * ceil(n / 15)

    return list(map(str, result))