9
\$\begingroup\$

This is my first attempt at solving Fizzbuzz. I've always been pretty weak at algorithms, so I'm trying to improve. Specific feedback on performance would be appreciated.

def fizzBuzz(fizzNumber, buzzNumber):
  i = 0
  for i in range(1, 101):
      fizzBuzzValues = [i%fizzNumber, i%buzzNumber, i%(fizzNumber * buzzNumber)]
      if(0 in fizzBuzzValues):
          if(fizzBuzzValues[2] == 0):
              print("Fizzbuzz")
          elif(fizzBuzzValues[0] == 0):
              print("Fizz")
          elif(fizzBuzzValues[1] == 0):
              print("Buzz")
          else:
              break
      else:
          print(i)

fizzBuzz(3, 5)
\$\endgroup\$
  • 1
    \$\begingroup\$ Just so you know, potential performance gain in FizzBuzz is nil. It would be better to try to get something more complex than this example to learn algorithms; fizzbuzz doesn't give you a lot of freedom in this aspect. \$\endgroup\$ – MatthewRock Jan 27 '17 at 14:48
7
\$\begingroup\$

Specific feedback on performance would be appreciated.

There are some things to improve performance-wise:

  • on every single iteration, you are calculating all the 3 remainders, even though you need a single one (in the best case)
  • the 0 in fizzBuzzValues check is not really needed (and the "in list" is O(n) in general, even though n=3 in this case, but you are doing that in a loop) - you can compare each of the remainders one by one
  • if you can calculate something before the loop - always do it - the fizzNumber * buzzNumber can be defined before the loop

Modified code:

def fizz_buzz_new(fizz_number, buzz_number):
    fizz_buzz_number = fizz_number * buzz_number
    for i in range(1, 101):
        if i % fizz_buzz_number == 0:
            print("Fizzbuzz")
        elif i % fizz_number == 0:
            print("Fizz")
        elif i % buzz_number == 0:
            print("Buzz")
        else:
            print(i)

Some timeit tests (replaced print() with yield to avoid seeing impact of printing to stdout):

$ ipython3 -i test.py 

In [1]: %timeit for x in range(100): list(fizzBuzz(3, 5))
100 loops, best of 3: 3.52 ms per loop

In [2]: %timeit for x in range(100): list(fizz_buzz_new(3, 5))
100 loops, best of 3: 1.98 ms per loop
\$\endgroup\$
7
\$\begingroup\$

If you are going to support arbitrary fizzNumber and buzzNumber, then you should do it correctly. For fizzBuzz(3, 6), you would print "Fizz" for 6 instead of "FizzBuzz" as I would expect.

Note that interCaps is not recommended by PEP 8.

\$\endgroup\$
  • 1
    \$\begingroup\$ Answer might be improved by including a pointer to docs.python.org/3.5/library/math.html#math.gcd \$\endgroup\$ – Taemyr Jan 27 '17 at 8:07
  • 1
    \$\begingroup\$ @Taemyr No, that is not an improvement. That is absolutely not the purpose of a code review that the reviewer explains the OP how to implement a necessary feature that the OP has forgotten to think of. \$\endgroup\$ – miracle173 Jan 28 '17 at 8:11
  • \$\begingroup\$ @miracle173 My comment is to an answer that is pointing out a bug. I think such an answer would be imroved by information on how that bug can be avoided. \$\endgroup\$ – Taemyr Jan 28 '17 at 10:24
6
\$\begingroup\$

Specifics on unneeded code:

Setting a variable just before using it in a loop is a no-op:

  i = 0

Pre-calculating your fizzbuzz values, might be useful if the calculations were expensive, or the results were used multiple times. But in this case, the values are not expensive to calculate, and are only needed once:

  fizzBuzzValues = [i%fizzNumber, i%buzzNumber, i%(fizzNumber * buzzNumber)]

Testing if any value is zero, might be useful, except if any of the values are zero, the stacked if will test them all for zero again:

      if(0 in fizzBuzzValues):

Since you previously checked if any of the values were zero, there is no way to get to this else:

          else:
              break

Removing non-pythonic and uneeded code and formatting to pep8:

def fizz_buzz(fizz_number, buzz_number):

    for i in range(1, 101):
        if i % (fizz_number * buzz_number) == 0:
            print("Fizzbuzz")
        elif i % fizz_number == 0:
            print("Fizz")
        elif i % buzz_number == 0:
            print("Buzz")
        else:
            print(i)

fizz_buzz(3, 5)
\$\endgroup\$
4
\$\begingroup\$

To add to the existing answers, one of the principles of functions and functional programming is that a function should have one single responsibility. Right now your function does the following things:

  1. Create and populate a list with modulus calculations;

  2. Iterate 100 times over the list;

  3. Associate results with a value (Fizz, Buzz, FizzBuzz or a number);

  4. Print results to the console.

If I were to break down the function, I would make one function that simply checks for Fizz/Buzz and return the appropriate string, or None (a.k.a null) when there is no match, given two numbers. You could also give it optional string arguments to make it able to return other values besides Fizz and Buzz.

def get_fizz_buzz(target_num,  fizz_num, buzz_num, fizz_word="Fizz", buzz_word="Buzz"):
    result = None
    # calculations...
    return result

Then you call either get_fizz_buzz(i, 3, 5) or get_fizz_buzz(i, 3, 5, "Hello", "World") from a loop, and check if the return is None then you know it's not a FizzBuzz number.

For the iteration and printing parts, you could either run that in your main function, or make a function that takes numbers as input then calls the above function and prints the correct result.

Others have pointed out that you could do away with the list part, but if you needed the results in a list for some reason, I'd make a separate function that returns a list, then you can do whatever you need to with the list after it returns.

\$\endgroup\$
4
\$\begingroup\$

If you wait on outputting a newline character until after you fizz, buzz, or both, you can very slightly reduce the logical overhead of each iteration. I have no idea what the performance cost is for making multiple output calls instead of making one larger output call, so this could actually make the performance worse in practice.

In the case of a FizzBuzz, Fizz is written with no newline, then Buzz is also written with no newline. After both Fizz and Buzz are printed, a newline is printed. The output of this is equivalent to printing FizzBuzz with a newline all at once.

import sys


def fizz_buzz(fizz, buzz):
    for i in range(1, 16):
        wrote = False
        if i % fizz == 0:
            wrote = True
            sys.stdout.write("Fizz")
        if i % buzz == 0:
            wrote = True
            sys.stdout.write("Buzz")
        if wrote:
            sys.stdout.write('\n')
        else:
            sys.stdout.write(str(i) + '\n');

    sys.stdout.flush()

fizz_buzz(3, 5)
\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review, nice answer! I posted an answer showing the affect of more print, or sys.stdout.write, statements. You may be interested in it. (Also you don't print i if it's neither fizz nor buzz.) \$\endgroup\$ – Peilonrayz Jan 27 '17 at 17:13
  • \$\begingroup\$ I added an else on the final condition to handle printing i if it is neither fizz nor buzz. Thanks for the heads up. Also, based on your answer, it does seem that this could possibly be improved by building a string up and then writing it to stdout all at once. \$\endgroup\$ – Kelsie Jan 27 '17 at 18:19
3
\$\begingroup\$

Performance isn't an issue. This is FizzBuzz. Let's take a look at good practice:

  i = 0

This is neccessary in C if you want to see i after the loop, but not in Python. In Python, you have

  • function scope - each variable declared in the function is visible afterwards in the function, everywhere.
  • implicit binding in for - for i in x creates binding for i if there isn't one, or overwrites if there is.

fizzBuzzValues = [i%fizzNumber, i%buzzNumber, i%(fizzNumber * buzzNumber)]

First of all, you don't exactly need to all of these three at once, but there's other problem in here.

You define only one variable. Why? Having three variables would be better in the practical application, since it improves debugability. Also,

else:
    break

is unneccessary.Let's look at refactored code:

def fizz_buzz(fizz, buzz):
    for i in range(1, 101):
        do_i_fizz = i % fizz
        do_i_buzz = i % buzz
        if(do_i_fizz == 0 and do_i_buzz == 0):
            print("Fizzbuzz")
        elif(do_i_fizz == 0):
            print("Fizz")
        elif(do_i_buzz == 0):
            print("Buzz")
        else:
            print(i)

fizz_buzz(3, 5)

Not that much of a change. That's why you should try learning on something more complicated than that :)

\$\endgroup\$
  • \$\begingroup\$ No, in C it also does not make sense to assign a value to a variale that is overwritten before it is used. \$\endgroup\$ – miracle173 Jan 28 '17 at 8:17
  • \$\begingroup\$ @miracle173 I was referring to the fact of declaring the variable before the for loop in C. In C, if you want to use i after the for loop, you need to keep it outside the loop. In Python, scopes don't exist so you have a one big variable party. I wrote about i = 0 because in Python there's no variable declaration. You always use variable somehow, so the moment you declare it, you assign a value to it. Anyway, reworded to make my intention clearer. \$\endgroup\$ – MatthewRock Jan 28 '17 at 13:54
  • \$\begingroup\$ I noticed that you have edited your answer to clarify this. \$\endgroup\$ – miracle173 Jan 28 '17 at 18:59
2
\$\begingroup\$

print is slow, like really slow. Instead it's faster to combine a list, with say '\n'.join, and print it once. It incurs \$O(n)\$ rather than \$O(1)\$ memory however.

Here's a quick timing:

>>> from timeit import timeit
>>> timeit('print("\\n".join(arr))', 'arr = list(map(str, range(100)))', number=10)
0.11
>>> timeit('for n in arr: print(n)', 'arr = list(map(str, range(100)))', number=10)
3.79

And so to speed up your code, all you need to do is minimize the amount of prints. You can do this by building a list like we did in the setup above. Including some of the other changes suggested by other users you can get:

from math import gcd

def _fizz_buzz(fizz, buzz):
    fizzbuzz = gcd(fizz, buzz)
    for i in range(1, 101):
        if i % fizzbuzz == 0:
            yield 'fizzbuzz'
        elif i % fizz == 0:
            yield 'fizz'
        elif i % buzz == 0:
            yield 'buzz'
        else:
            yield str(i)

def fizz_buzz(fizz, buzz):
    print('\n'.join(_fizz_buzz(fizz, buzz)))

fizzBuzz(3, 5)
\$\endgroup\$
1
\$\begingroup\$

[This answer has a repository https://github.com/brudgers/python3-fizzbuzz]

There are many other good answers, so I will focus on performance since it is at the heart of the question.

Classic FizzBuzz

The classic FizzBuzz uses the numbers 3 and 5 over the range 1 to 100. Since this is a constant, the best performance is simply to print the constant:

def fizzbuzz():
  print("1\n\2\fizz\n4\n\buzz\n....")

Because the fastest operation is one that is not performed (but only when performing it is not required).

Of course the code is not very interesting in Python. The code for such an approach might be more interesting in a language that provides compile time calculations -- for example Lisp via its macro facility. The cost of more interesting code is often similar to that of execution optimizations: the code is harder to read and to understand.

Arbitrary Fizzbuzz

By 'arbitrary FizzBuzz' I mean that the values for 'fizz' and 'buzz' can be arbitrary (for some definition of 'arbitrary') as is the case in the question where values for fizz and buzz are supplied as arguments and not hard coded as in classic FizzBuzz. As is the case with Classic Fizzbuzz and problems in general, performance optimization of Arbitrary FizzBuzz requires tuning the code to take advantage of the structure of the problem in order to minimize the amount of work the computer has to do.

The underlying arithmetic creates a structure that repeats:

# Classic FizzBuzz Cycle
int, int, fizz, 
int, buzz, fizz, 
int, int, fizz, 
buzz, int, fizz, 
int, int, fizzbuzz

And the location of a value within the Classic FizzBuzz cycle can be determined by:

# g(value) is a function that compensates
# for potential off-by-one errors
g(value) % 15

An Ugly First Implementation

The main code is reasonably clean. Improvements related to print() are described in other answers, but I've ignored them to focus on the algorithmic abstractions rather than performance related to language implementation.

def fizzbuzz (fizz, buzz):
    first = 1
    last = 100
    end = last + 1
    cycle = fizzbuzz_cycle(fizz, buzz)
    product = fizz * buzz
    for val in range(first, end):
        index = (val - 1) % product
        if cycle[index]:
            print (cycle[index])
        else:
            print (val)

The key call is to the function fizzbuzz_cycle which takes two numbers and returns a list.

def fizzbuzz_cycle (fizz, buzz):
    """Generate a cycle of fizzes and buzzes and fizzbuzzes and False's"""
    product = fizz * buzz
    cycle = list(range(1, 1 + product))    

It contains three functions {fb, f, b} which take a number and either return that value or an appropriate string:

    def fb (v):
        #This function checks for fizzbuzz
        if v % product == 0:
            return "fizzbuzz"
        else: return v

    def f (v):
       #This function checks for fizz        
        if v % fizz == 0:
            return "fizz"
        else: return v

    def b (v):
       #This function checks for buzz 
        if v % buzz == 0:
            return "buzz"
        else: return v

The three functions {fb, f, b} are used within the function fizzbuzz_fizz_buzz_or_False which takes a value and returns either a string {'fizz', 'buzz', 'fizzbuzz'} or False. The big-hairy nested if is written to be more easily translated into a lower level language where {fb, f, b} could be inlined should additional optimization be sought.

    def fizzbuzz_fizz_buzz_or_False (v):
       #This function returns:
       #fizzbuzz or fizz or buzz or False
       fb_val = fb(v)
       if fb_val == v:
           f_val = f(v)
           if f_val == v:
               b_val = b(v)
               if b_val == v:
                   return False
               else:
                   return b_val
           else:
               return f_val
       else:
           return fb_val

And we return fizzbuzz_fizz_buzz_or_False mapped over the range of the cycle.

    return list(map(fizzbuzz_fizz_buzz_or_False, cycle))

Like I said, it ain't exactly pretty. Like I didn't say, this might be more efficient on paper but not in real life. Modern compilers do a lot of sophisticated optimizations including JIT'ing at runtime, and CPU's that do predictive branching optimization. Therefore optimization should begin with measuring something that works and determining where the actual bottlenecks are. The other answers that optimize around print() are examples of why ideas about optimization are not always actual optimizations.

On the other hand, the general approach of precomputing a cycle is applicable to other languages and other problems and the larger strategy of avoiding work is a good place to start changing code when measurements indicate changes are warranted.

Final Comments

I appreciate that the code in the question seeks to generalize the problem by tackling the 'Arbitrary FizzBuzz'. I also like that all of the modulo's are done in one place...one of the optimizations that are built into Python is optimizing development time.

\$\endgroup\$
-1
\$\begingroup\$

I've always been pretty weak at algorithms, so I'm trying to improve. Specific feedback on performance would be appreciated.

The thing is FizzBuzz is not a problem that shows your algorithms knowledge, I've seen lots of solutions and never seen one done in O(n^2). I mean if you will think about it, you might find a solution in O(n^2) but most obvious solutions will still be O(n). So again this problem is not about algorithms.

The main goal of FizzBuzz is just to show your basic knowledge on specific programming language since it contains all the main operations (loop, output and number operations). It's also a good thing to have a basic image on candidate coding style.

If I would be asked to solve a fizzbuzz I will do something like this:

def real_fizz_buzz(fizz=3, buzz=5):
    print(*('Fizz'*(not i % fizz)+'Buzz'*(not i % buzz) or i for i in range(1, 101)), sep='\n')

Or this:

print(*(map(lambda x: 'Fizz'*(not x % fizz)+'Buzz'*(not x % buzz) or x, range(1, 101))), end='\n')

Or using F literal:

print(*map(lambda x: f"{'Fizz' * (not x%3)}{'Buzz' * (not x%5)}" or x, range(1,101)), sep='\n')

I know this is something that is not easy to read for a beginner, but I just like that python allows you to solve that simple problem in one line and I would use it if I would be asked.

However, my personal opinion that is long as a candidate can solve this problem and does it in O(n), it's fine and acceptable.

So for this particular problem just use any solution that is easier for you to write and understand.

\$\endgroup\$
  • 2
    \$\begingroup\$ I'm tempted to downvote for the code alone. You yourself say "this is [...] not easy to read for a beginner," which means the code is un-Pythonic. Where a readable equivalent is just as easy to write. \$\endgroup\$ – Peilonrayz Jan 27 '17 at 11:50
  • \$\begingroup\$ @Pelionrayz if it's not easy for the beginner it does not mean that it's not pythonic. Meta classes are hard to understand even for some experienced python devs but it does not make it non-pythonic. They are widely used in libraries and they are part of python itself. To read my solution you should know about argument unpacking and print optional arguments, most likely if you are beginner you dont know it. \$\endgroup\$ – Alex Jan 27 '17 at 12:03
  • 1
    \$\begingroup\$ 'hard to understand' and 'hard to read' are not the same thing. You can, as you did, make easy to understand things hard to read. \$\endgroup\$ – Peilonrayz Jan 27 '17 at 12:24
  • 1
    \$\begingroup\$ Again you ignore what I'd written, and argue about understandability. Something you brought up. \$\endgroup\$ – Peilonrayz Jan 27 '17 at 13:44
  • 2
    \$\begingroup\$ This looks rather like a code golfing solution rather than a code review. While I like what you did there, I don't think OP will understand anything . Please bare with the beginner tag. \$\endgroup\$ – Grajdeanu Alex. Jan 27 '17 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.