Python return one-liner behaves differently than multiple liner code

Question

I was practicing Fibonacci sequence generating in python and following example of memoization from How do I print a fibonacci sequence to the nth number in Python?.

Then I encountered one interesting difference using return one-liner and not. For example, the example code is given below. In the first example, we do not use return one-liner and it runs very fast, however, in the second example we use return one-liner and it runs very slow.

Aren't they supposed to be the same?

Without one-liner

def memoize(func):
    memo = dict()
    def decorated(n):
        if n not in memo:
            memo[n] = func(n)
        return memo[n]

    return decorated

@memoize
def fib(n):
    if n<=1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

print([ fib(i) for i in range(100,110)]) # runs very fast

With one-liner return

def memoize(func):
    memo = dict()
    def decorated(n):
        return func(n) if n not in memo else memo[n]

    return decorated

@memoize
def fib(n):
    if n<=1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

print([ fib(i) for i in range(100,110)]) # very slow

Question
Aren't they supposed to be the same?
Why the return one-liner is much much slower than another one?
Can we write one-liner with different wordings so that it is equally fast?

2. The second one is slower because you're never saving anything in `memo`, presumably. — FHTMitchell, Mar 18 '19 at 15:30
A correct one-liner would look something like `return memo[n] if n in memo else memo.setdefault(n, func(n))`. (The conditional expression prevents `func(n)` from being evaluated if the lookup would, in fact, succeed.) — chepner, Mar 18 '19 at 15:30
If you care about lines of code I can compress your entire `memorize` function to one line: `from functools import lru_cache as memorize`. This is written in c and will be much faster than anything you can reproduce in python. https://docs.python.org/3/library/functools.html#functools.lru_cache — FHTMitchell, Mar 18 '19 at 15:32
@FHTMitchell I tried using meorize but this gives `TypeError: Expected maxsize to be an integer or None` — BhishanPoudel, Mar 18 '19 at 15:38
@meowgoesthedog, I am in learning phase, sorry for ignorances, but I simply used the @lru_cache decorator to the function `fib(n)` and it does not work and gives above error. — BhishanPoudel, Mar 18 '19 at 15:43
@astro123 the documentation says you must use `@lru_cache(maxsize=)` instead of simply `@lru_cache`. — meowgoesthedog, Mar 18 '19 at 15:44

Scott Skiles · Accepted Answer · 2019-03-18T15:40:54.863

5

This

    if n not in memo:
        memo[n] = func(n)
    return memo[n]

Is not the same as

    return func(n) if n not in memo else memo[n]

The one-liner does not modify the contents of memo. If you want to compare apples to apples then try:

    if n not in memo:
        return func(n)
    return memo[n]

For optimizing your one liner, and saving the dictionary value, you should change the one-liner to:

    return memo[n] if n in memo else memo.setdefault(n, func(n))

Beyond learning how memoize works, you should look into using functools lru_cache's memoize, which is "written in C and will be much faster than anything you can reproduce in Python."

Hat tip to meowgoesthedog, chepner, & FHTMitchell.

edited Mar 18 '19 at 15:40

answered Mar 18 '19 at 15:28

Scott Skiles

3,647
6
40
64

lol, instead of showing how to optimize the one-liner properly, you show how to de-optimize the 3-liner. – Barmar Mar 18 '19 at 15:33
2

@Barmar This is python. Aggressively lowering line count is discouraged. – FHTMitchell Mar 18 '19 at 15:34
1

@FHTMitchell And the point of writing a `memoize` function is that you write it once and forget about it -- there's nothing gained from writing it tersely. – Barmar Mar 18 '19 at 15:36

Python return one-liner behaves differently than multiple liner code

Without one-liner

With one-liner return

1 Answers1