1
\$\begingroup\$

Here's a snippet of code I use to examine the functionality of Python decorator(@memorize). An example of Fibonacci computation:

def memorize(f):
    memo = {}
    def helper(*args):
        if args not in memo:
            memo[args] = f(*args)
        return memo[args]
    return helper

def fib(n):
    if n==0:
        return 0
    elif n==1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

Here's the problem:

Different naming is causing a huge speed difference, why is it?

  • Execution 1:

    s = time.time()
    fib = memorize(fib)
    a = fib(40)
    e = time.time()
    print(a)
    print(e-s)
    

    returns

    102334155

    7.319450378417969e-05

  • Execution 2:

    s = time.time()
    memo_fib = memorize(fib)
    a = memo_fib(40)
    e = time.time()
    print(a)
    print(e-s)
    

    returns

    102334155

    46.79982662200928

Edited:

A screen copy from running the code enter image description here

Edited:

Unless running the two executions seperately, to obtain aforementioned results, "Execution 2" must be run before "Execution 1".

\$\endgroup\$
  • 1
    \$\begingroup\$ I can't reproduce your reported timing results. Can you double-check your work, please? \$\endgroup\$ – Gareth Rees Jan 6 '18 at 8:26
  • \$\begingroup\$ Got it double checked and attached with a screenshot, still couldn't figure out where it goes wrong. @GarethRees \$\endgroup\$ – Logan Jan 6 '18 at 9:51
  • 2
    \$\begingroup\$ Aha, you have to do execution 2 before execution 1. That wasn't clear from your original post. \$\endgroup\$ – Gareth Rees Jan 6 '18 at 11:28
2
\$\begingroup\$

fib works by recursively calling the function named fib:

def fib(n):
    if n==0:
        return 0
    elif n==1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

In your "execution 1" the function named fib is the memoized version of the function, because you have assigned it like this:

fib = memorize(fib)

But (assuming that you haven't run "execution 1" yet), in your "execution 2" the function named fib is the original function (not the memoized version of the function, which you have assigned to memo_fib), so when you call memo_fib it calls the original fib and when that recurses it calls the original fib, bypassing the memoization.

| improve this answer | |
\$\endgroup\$

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