# “FIZZ BANG BUZZ!” 3,7,11 efficiency

I wrote a fizz buzz variation method in Python which prints "fizz", "bang", and "buzz" for 3, 7, and 11 respectively.

def FizzBang():
string = ''
for n in range(1,101):
msg = ""
if not n % 3:
msg += "Fizz"
if not n % 7:
msg += "Bang"
if not n % 11:
msg += "Buzz"
print msg or str(n)


What can I do to increase the speed of this program? I know the modulus is quite expensive. Also maybe concatenating strings might not be needed as well.

-
You could write it in a native language. –  Trevor Hickey Apr 28 at 21:54

Indeed, addition is faster than modulo. This implementation runs about 33% faster than the original when counting up to 100. However, I expect that it wouldn't scale as well to larger limits due to its O(n) memory usage.

def fizz_bang(limit=100):
limit += 1
strings = [''] * limit

fbb = ((3, 'Fizz'), (7, 'Bang'), (11, 'Buzz'))
for stride, noise in fbb:
for n in range(0, limit, stride):
strings[n] += noise
for n in range(1, limit):
print strings[n] or n


Also, according to PEP 8 conventions, FizzBang should be named fizz_bang instead.

-
You could address the memory usage by putting the two for loops within a larger loop, that is, compute 1000 or 10000 or some other reasonably large number of output values, print them, and then reuse the memory for the next batch of values. There would be some computational overhead to set values for the inner loops on each iteration of the outermost loop, including three uses of the modulo operation. (On the other hand, in practical terms we would probably all lose interest in the output before memory use became a problem.) –  David K Apr 28 at 22:53
@DavidK Actually, the array size can be bounded by the LCM of 3, 7, 11, which is 231. After that it cycles. –  200_success Apr 28 at 23:06
Good point! Yes, of course, so there is still no need to do a modulus. –  David K Apr 29 at 14:39

I don't think the modulo operator is as expensive as you think it is, and even if it would be there's no way you can avoid it.

However, instead of doing string concatenation you can write to sys.stdout directly. This however, requires a temporary variable to know if any previous number has been written already.

Also, your string variable has a bad name, and seems to be unused.

If the code in your question is Python2, use xrange instead of range (if it is Python3, no harm done as the range method in Python3 is Python2's xrange)

Python 3 code:

def FizzBang():
for n in range(1,101):
written = 0;
if not n % 3:
sys.stdout.write("Fizz")
written = 1
if not n % 7:
sys.stdout.write("Bang")
written = 1
if not n % 11:
sys.stdout.write("Buzz")
written = 1
if not written:
print(str(n))
else:
print()

-
I've measured this to be about 3% slower than the original (basically a non-issue), and certainly uglier. –  200_success Apr 28 at 19:28
@200_success That explains the downvote. (Well deserved). In that case I think the best suggestion is: Stick to the old code. –  Simon André Forsberg Apr 28 at 19:33
@200_success this answer is slower? Hmm does this answer use less memory? (string concatenations) –  Liondancer Apr 28 at 19:41
Indeed, print "Fizz", makes it about 10% faster than sys.stdout.write("Fizz"), probably because print is built-in rather than a function call in Python 2. As for any difference in memory usage, I challenge you to find any measurable difference. –  200_success Apr 28 at 20:01
@Liondancer We had a recent Python question about measuring time –  Simon André Forsberg Apr 28 at 20:16
show 4 more comments