# Lazy evaluation and memoization in Python computations

We use memoization to cache the computed results to help speed up the computation of Fibonacci numbers, and lazy evaluation to create a generator that outputs new Fibonacci numbers indefinitely.
Contents

# What is lazy evaluation

In programming language theory, lazy evaluation, or call-by-need is an evaluation strategy which delays the evaluation of an expression until its value is needed (non-strict evaluation) and which also avoids repeated evaluations (sharing).

Simply put, lazy evaluation is to put some part of the program into a compute-on-demand mode. The opposite mode to lazy evaluation is called eager evaluation, in which the computation is always performed, regardless whether the result is demanded or not.

A simple example in Python is the `range()` function. You probably already know that `range(x)` gives a collection of integers ranging from `0` to `x-1`. In Python 2, `range(x)` will generate a list in memory to store the integers and return it to you. There is also an `xrange()` function, which does the similar thing as `range()`, except that it returns an `xrange` object instead of `list`. See the listing below:

```Python 2.7.18 |Anaconda, Inc.| (default, Apr 23 2020, 22:42:48)
[GCC 7.3.0] on linux2
>>> aa=range(10)
>>> type(aa)
<type 'list'>
>>> aa
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>>
>>> bb=xrange(10)
>>> type(bb)
<type 'xrange'>
>>> bb
xrange(10)
```

The difference between `aa` and `bb` is that `aa` is an eagerly evaluated `list`, and by the time you call it to see its value, all elements in the list are already there. In this toy example its size is 10, no big deal. But if for some reason you need to use such a thing to do a 10M `for` loop (like `for i in range(10**7):`), you will be creating a big list containing 10M integers, that is starting to stress the RAM.

On the contrary, `bb` is a lazily evaluated `generator`. When you call it in the interpreter, no element gets created and returned, it tells you that `bb` is `xrange(10)`. Elements only get created when you access them, like:

``````for i in bb:
print(i)
``````

Therefore, `xrange(10)` has the same memory footprint as `xrange(10**7)`. Besides saving memory usage, it often makes your program run faster when used with a loop, because it doesn’t need to create the full collection before going into the 1st iteration of the loop.

In Python 3, the `xrange()` function is removed, instead `range()` becomes a lazily evaluated generator.

Lazy evaluation allows one to use infinite series in a programming language. Recently I have been learning the Clojure language. In Clojure, most of its sequence types are lazy, and the most frequently used sequence functions, including `map`, `filter` and `reduce` all return lazy sequences. For instance, `(iterate inc 0)` creates an infinite integer sequence, but it won’t blow up your computer, because nothing gets evaluated just yet, since it is a lazy sequence. New values will be created when you need them, like `(take 10 (iterate inc 0))`, which will take the first 10 elements from the infinite sequence.

In Python we can do the similar thing, by creating a `generator`:

```def infIntegers(start):
while True:
yield start
start+=1```

The unconditional while loop (`while True:`) tells that this thing is going to run forever. In each iteration, it yields out an output. For the 1st iteration, the output is the given starting number `start`. After yielding out `start`, the function returns back the control flow to the calling stack. Then next time the generator is asked for a return, execution resumes from Line 4 (`start+=1`), so it increments the `start` value by 1, and enters into the next iteration, in which the next number is yielded. If you use such a thing like this:

``````for i in infIntegers(0):
print(i)
``````

It will print out all the integers, starting from 0, indefinitely.

# What is memoization

I sometimes confuse lazy evaluation with memoization, because they are often used together. But there are some differences.

In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

In the simplest form, you write your program to cache some results that you don’t want it to re-compute again. For computations that are deterministic, one can use the input argument as the key to a cache where the results are stored. The next time the results are needed, you provide the cache with the key and it returns the corresponding values, bypassing the computation process. Therefore the same key (input) always corresponds to the same result. This can’t be done with non-deterministic computations – you certainly don’t want a random number generator to repeatedly generate the same number.

A simple cache can be created using dictionary in Python. Here is one:

```def fib(n):
if n==0 or n==1:
return n
return fib(n-1)+fib(n-2)

def fibCache(n, cache):
if n==0 or n==1:
cache[n]=n
return n

result=0
for x in [n-1, n-2]:
if x in cache:
result+=cache[x]
else:
new=fib(x)
cache[x]=new
result+=new
cache[n]=result
return result```

The `fib(n)` function computes the nth Fibonacci number. And `fibCache()` is the version using a cache, which is a dictionary. Some computation time comparison:

```N=40
aa=[]
t1=time.time()
for i in range(N):
aa.append(fib(i))
t2=time.time()
print('No cache time=', t2-t1)
print(aa)

bb=[]
cache={}
t1=time.time()
for i in range(N):
bb.append(fibCache(i, cache))
t2=time.time()
print('Cache time=', t2-t1)
print(bb)```
```No cache time= 44.94058156013489
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986]

Cache time= 2.384185791015625e-05
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986]```

The difference is HUGE. To help you memoize a function, Python provides a decorator that simplifies the process even more (note that the `lru_cache` decorator is only available since Python version 3.2):

```from functools import lru_cache

@lru_cache(maxsize=256)
def fib(n):
if n==0 or n==1:
return n
return fib(n-1)+fib(n-2)```

Now compare the decorated `fib()` with our `fibCache()`:

```N=40
aa=[]
t1=time.time()
for i in range(N):
aa.append(fib(i))
t2=time.time()
print('No cache time=', t2-t1)

bb=[]
cache={}
t1=time.time()
for i in range(N):
bb.append(fibCache(i, cache))
t2=time.time()
print('Cache time=', t2-t1)```
```No cache time= 2.4318695068359375e-05
Cache time= 2.288818359375e-05```

Therefore you achieve the same level of performance boost without having to modify any of the inner workings of the function yourself. What a bonus.

# Combine lazy evaluation with memoization

The above functions are all returning the nth Fibonacci number. Now let’s try combining lazy evaluation and memoization to create a new function that keeps on producing the next Fibonacci number from a given start point. Here is my implementation:

```def fibGen(start):
cache={}
# get the start number
result=fibCache(start, cache)
yield
while True:
yield result
start+=1
result=fibCache(start, cache)```

And here is the code snippet that keeps on getting a new Fibonacci number, starting from the 5th one, until the number is greater than `10^10`:

```t1=time.time()
f_gen=fibGen(5)  # start from the 5th Fibonacci number
next(f_gen)  # compute the starting number

while True:
new=next(f_gen)  # yield a new number, starting from the 5th
print(new, end=' ')

if new>=10**10:
print('\n')
break

t2=time.time()
print('t2-t1 = ', t2-t1)```

Note that at Line 2, we created a generator specifying the starting number `f_gen = fibGen(5)`. Line 3 primes the generator by calling the `next()` function on the generator. What it does is telling the generator to run its inner lines till the 1st `yield`, in this case, these 3 lines are run:

```cache={}
# get the start number
result=fibCache(start, cache)
yield```

And it stops, and returns the control back to the main script.

The next call of `next(f_gen)` happens at Line 6 in the `while True:` loop, this will resume the execution of the generator, letting it enter its own `while True:` loop, and yield out the 1st `result`, which would be the 5th Fibonacci number it computed during the previous call of `next(f_gen)`.

After yielding the result out, the generator stops and returns back the control again. The yielded value (number `55`) is assigned to the variable `new`, which gets printed out at Line 7. Since the new number is smaller than `10^10`, the loop continues. In the next call of `next(f_gen)`, execution inside the generator starts from the line `start+=1`, and executes these following lines in sequence:

```start+=1
result=fibCache(start, cache)
while True:
yield result```

Then the generator hands back the control again, and execution moves on in the outer `while` loop. This same process repeats from then on, until a newly yielded Fibonacci number exceeds the upper bound and the `while` loop terminates. Below is the output:

```5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049 12586269025

t2-t1 =  7.677078247070312e-05```

# Conclusion

In the above example, we used memoization to cache the computed results to help speed up the computation of Fibonacci numbers, and lazy evaluation to create a generator that outputs new Fibonacci numbers indefinitely.

In-memory caching can be quite helpful in many situations. For instance in GUI applications, responsiveness is one of the key ingredients in the delivery of a pleasant user experiences. Sometimes your graphical interface thread may have to wait for some computations to finish before it can display the outputs to the user. If such computations take too long (maybe longer than 1 or 2 seconds), you may consider caching the computed results (memoization) and only doing new computations when new data are demanded, or existing data need update (lazy evaluation). Then, the next time the user clicks into the same interface, the contents can be delivered from the cache and in a much faster speed.

In-memory caching is suitable for relatively small sized data. Sometimes, the computed results may be too large to fit into the RAM, and the time required to redo the computation is significantly longer than the time needed to read them from disk, then one may consider caching the results to disk as the memoization method. In a future post I’ll share some functions to cache the intermediate NetCDF data to disk, and load them in if re-computation can be bypassed.

### One comment

1. […] a previous post we talked about in-memory caching using the dictionary in Python. Sometimes the data may be too big […]