2

Below is an iterative calculation of Fibonacci Sequence. 

def fibonacci(n):
    if n < 0:
            raise ValueError("invalid index!")
    if n==0:
            return 0
    if n==1:
            return 1

    f = [0,1]
    for i in range(2,n+1):
            f.append(f[i-1] + f[i-2])
    return f[n]

Code Source: brilliant.org

As it is, the list f is a local variable inside the function and will be recreated and repopulated each time the fibonacci function is called. How could this code snippet be rewritten so that Python would not need to recalculate fibonacci(5) once it was called and could use it the next time fibonacci(5) or above was called? I know global variable is one option but what would be the most "Pythonic" way of doing this?

Semihcan Doken
  • 776
  • 3
  • 10
  • 23
  • 1
    `global` or pass a mutable variable to the function. – Torxed Sep 28 '17 at 09:00
  • Is that the most pythonic way of doing this? I thought global variables were frowned upon. I am looking not just for an answer that works but for an explanation of best coding practice. – Semihcan Doken Sep 28 '17 at 09:02
  • 1
    You might want to check better implementation's alternatives: https://technobeans.com/2012/04/16/5-ways-of-fibonacci-in-python/ – SuperKogito Sep 28 '17 at 09:02
  • 2
    You should look up memoization. An example here: https://stackoverflow.com/a/13865482/104349 – Daniel Roseman Sep 28 '17 at 09:02
  • 1
    Does that matter? I don't get this whole `pythonic` religious bs tbh. If it solves your problem and is a readable and or fast operation, isn't that good? Anyway, yes it's pythonic -.- – Torxed Sep 28 '17 at 09:02
  • 1
    A quick extension to my rant. If you're learning or getting stuck with something. Ignore every rule you think you need to follow, and just figure out a way to solve the problem. It's not worth getting stuck on trying to find the most perfect language solution if you get stuck there forever AND you learn nothing by it. It's better to just go with what feels right as long as it works in the start and figure out how to make it prettier later (unless you're a savant and can do both at the same time). End rant. – Torxed Sep 28 '17 at 09:07
  • 2
    @Torxed global variables are neither fast, thread-safe, nor pythonic (which simply means using the language in the most straight forward and forward thinking manner, and not e.g. like you're used to from another language). There are plenty of people who enjoy hacking code into submission, with no regard for maintainability or reliability, so by all means feel free to do so ;-) – thebjorn Sep 28 '17 at 09:08
  • @Torxed: noo... do not use `global`, it is a terrible anti-pattern. – Willem Van Onsem Sep 28 '17 at 09:08
  • @WillemVanOnsem Does it solve the problem? Is it built in to Python? Will everyone reading it know what happens?. The answer is yes, so the short answer will be: use it! Long answer: are there better ways to do it? yea sure. But if you're starting out, and dont wanna get frustrated and stop learning, use whatever works. Don't get hung up on semantics or ridiculous optimizations. You can learn why global is bad later. – Torxed Sep 28 '17 at 09:19
  • Starting a new programming language by learning how to do it the wrong way is an ... interesting approach. – Matthias Sep 28 '17 at 10:31

3 Answers3

3

You can store the f in a variable outside the scope of the function. For instance:

def memoize_fibonacci():
    f = [0,1]
    def inner_fibonacci(n):
        if n < 0:
                raise ValueError("invalid index!")
        for i in range(len(f),n+1):
                f.append(f[i-1] + f[i-2])
        return f[n]
    return inner_fibonacci

So each time we inspect the length of f. In case we have not generated the requested index yet, we generate until we obtain the index. Regardless whether we extend the list, we eventually can return f[n].

Now we can extract the fibonacci function, with:

fibonacci = memoize_fibonacci()

If we now query twice for the 200'000th element, the second time it is faster.

Willem Van Onsem
  • 443,496
  • 30
  • 428
  • 555
  • 1
    This is actually faster than using Binet's formula, by quite a margin too(!) – thebjorn Sep 28 '17 at 09:50
  • Thanks, @Willem Van Onsem, would it have made a difference if you did not have the last line `fibonacci = memoize_fibonacci` and just used `memoize_fibonacci` as your function? In terms of runtime? – Semihcan Doken Oct 18 '17 at 21:08
  • 1
    @Semihcan: yes. Since `memoize_fibonacci` is **not** a fibonacci function. It is a factory of Fibonacci functions. – Willem Van Onsem Oct 18 '17 at 21:51
1

You can memoize the results using a closure: In this case, the memo dict is created when the function is first executed (usually, when the module is loaded); it is persistent, and is populated as the function is called. 

def fibonacci(n, memo={}):
    try: 
        return memo[n]
    except KeyError:
        pass
    if n < 0:
            raise ValueError("fibonacci must be called with positive numbers")
    if n == 0:
        memo[n] = 0 
        return 0
    if n == 1:
        memo[n] = 1
        return 1
    memo[n] = fibonacci(n-1) + fibonacci(n-2)
    return memo[n]
Reblochon Masque
  • 35,405
  • 10
  • 55
  • 80
  • 3
    the memo dict is created when the function definition is executed (normally when the file it resides in is imported), not when the function is called for the first time.. – thebjorn Sep 28 '17 at 09:09
  • Due to its recursive nature, this blows up with an initial call of `fibonacci(1000)`, which other solutions can handle. The memoization doesn't help with this. Also, is this technically a closure? I.e. who's variable is `memo`? (Besides increasing Python's stack size, you can also game this one by calling `fibonacci(900)` before `fibonacci(1000)` to ease into the answer!) – cdlane Sep 30 '17 at 18:54
-1

Use a python dictionary and check if the key is present and return the result from dictionary or calculate and add the result to the dictionary before returning.

fib_dict = {};

def fibonacci(n):
    if n in fib_dict:
        return fib_dict[n];
    else:
        if n < 0:
            raise ValueError("invalid index!")
        if n==0:
            return 0
        if n==1:
            return 1

        f = [0,1]
        for i in range(2,n+1):
            f.append(f[i-1] + f[i-2])

        fib_dict[n] = f[n];
        return f[n];
Suhas Shelar
  • 963
  • 2
  • 10
  • 23