Lazy prime counting function [closed]

Question

I have written a simple snippet of code that implements a function that returns a list of primes up to a certain integer n. Assuming that this function could be called several times in the script for different values of n, I wanted to make it as "lazy" as possible—that is, able to reuse previously-calculated variables.

Here is the code (assume isPrime(n) returns True if n is prime and False otherwise):

primes = []


def pi(n):
    global primes

    if len(primes) == 0:
        # Full
        for i in range(2, n + 1):
            if isPrime(i):
                primes.append(i)
        return primes

    elif n <= primes[-1]:
        # Lazy
        return list(filter(lambda m: m <= n, primes))

    else:
        # Semi-lazy
        for i in range(primes[-1] + 1, n + 1):
            if isPrime(i):
                primes.append(i)
        return primes

The problem is, as you may have spotted, that I'm using a global variable (primes) to store the list of primes, and later modifying it inside the pi function. I've heard that relying on mutable global variables is a bad design choice. What are better ways to implement this?

---

This question should actually be generalized to the following: what's the best design pattern to implement a 'lazy' function (i.e. a function that reuses previously calculated values)?

Answer 1

The technique you're looking for is called memoization (or in other contexts it might have names like caching). Lazy evaluation is something else entirely.

Memoization is the canonical example for how decorators work in Python, but you don't need to learn the additional language construct if you don't like. Consider the following snippet. It could be more general, but that's beside the point.

def memoize(f):
    cache = {}
    def _f(n):
        if n not in cache:
            cache[n] = f(n)
        return cache[n]
    return _f

What we've created is a function that takes another function as an argument. How do we use it? Well, we pass a function into it.

def pi(n):
    # do stuff
pi = memoize(pi)

Take a close look at this.

1. First we make our normal function that deals with primes.
2. Next, we pass it into this memoize() monster that we just made.
3. When memoize() sees this function (now just called f), it makes a cache and defines a new function _f(). It's this new function _f() that's finally returned (i.e., at the end of all this, pi is the same as whatever _f happened to be), so let's look closely at what _f() does.
   1. First, _f() takes a look in the cache to see if we've already seen the value n. If not, it stores the output f(n), i.e. the original pi(n) we wanted, in the cache.
   2. Next, it returns the pre-computed value straight from the cache. That's it.

Now we've eliminated the use of globals (behind the scenes the cache thing we described is stored in what's called the closure of _f), we've taken the problem of caching away from pi() to give pi() a small, single purpose, and we've created a reusable memoization mechanism that we can apply to any other function that takes exactly one hashable input.

Back to the decorator thing I mentioned earlier, you could just as well write

@memoize
def pi(n):
    # do stuff

to memoize the pi function instead of applying the memoizer after the fact. It doesn't make much of a difference either way, but the latter is considered more pythonic.

To be able to take multiple arguments, you can start to do things with *args and **kwargs in your memoizer, but that's additional complexity without a lot of added benefits for the sake of this problem.