CODEWITHSUNDEEP
pythonperformancepython-3.x
Tsonglew
Tsonglew

Reputation: 673

Why python statement `if something is None` works much quicker than `if not something`?

I came across this question when writing a fibonacci function. To make it quicker, I use a dictionary named cache to store the numbers that already have been calculated. So I wrote

def fib(n, cache=None):
    if not cache:
        cache = {}
    if n in cache:
        return cache[n]
    if n==0 or n==1:
        return 1
    else:
        cache[n] = fib(n-1, cache) + fib(n-2, cache)
    return cache[n]

def fib_run(n):
    start = time.time()
    fib(n)
    end = time.time()
    print("fib_run cost: {}".format(end-start))

And I callfib_run(30), the output is fib_run cost: 0.8419640064239502, it just as slow as the function without a cache. But when I change if not cache: into if cache is None: in the function fib2, it works much quicker.

def fib2(n, cache=None):
    if cache is None:
        cache = {}
    if n in cache:
        return cache[n]
    if n==0 or n==1:
        return 1
    else:
        cache[n] = fib2(n-1, cache) + fib2(n-2, cache)
    return cache[n]

def fib2_run(n):
    start = time.time()
    fib2(n)
    end = time.time()
    print("fib_run cost: {}".format(end-start))

>>> fib2_run(30)
fib2_run cost: 2.6226043701171875e-05

I wonder why there is such a great difference between the two methods(I thought they were just the same in the early days). Thank you.

Upvotes: 1

Views: 769

Answers (2)

Elan
Elan

Reputation: 443

In the first case, the cache is always empty! No wonder you get the same timing as the function without a cache. All you need is a print to see what happens. 

if not cache:
#if cache is None:
    print(n, "No cache!")
    cache = {}

As explained above, empty collections evaluate to false. In the recursive call, if not cache is always true, you create a new dict, which you send a level below, which is again evaluated false and so on. There is never a single entry in the cache.

(Doing extra work even in the cases where cache already is equal to {}, as mentioned above, is one time operation. Shouldn't cost anything for bigger n)

Upvotes: 0

Dimitris Fasarakis Hilliard
Dimitris Fasarakis Hilliard

Reputation: 160657

The issue here isn't the performance of is None vs not cache, instead, it's that if cache is None is True only during the first invocation of fib2 while if not cache is True even if cache == {} for fib. 'Empty' collections evaluate to False therefore not an empty collection will be True:

>>> not {}
True

So you're doing extra work (assigning cache to {}) even in the cases where cache already is equal to {}.

In general, these operations are pretty similar in performance, one is a simple identity check while the other is based on the boolness of the value (which, for dictionaries, is based on the result of __len__ if I'm not mistaken).

Upvotes: 1

Related Questions