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\$

closed as off-topic by πάντα ῥεῖ, pacmaninbw, t3chb0t, Sᴀᴍ Onᴇᴌᴀ, Peilonrayz Jan 7 '18 at 5:43

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions containing broken code or asking for advice about code not yet written are off-topic, as the code is not ready for review. After the question has been edited to contain working code, we will consider reopening it." – πάντα ῥεῖ, pacmaninbw, t3chb0t, Sᴀᴍ Onᴇᴌᴀ, Peilonrayz
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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.

\$\endgroup\$

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