Explaining cache with python

What is cache? I define cache as "a saved answer to a question". Caching can speed up an application if a computationally complex question is asked frequently. Instead of the computing the answer over and over, we can use the previously cached answer. This post will present one method of adding cache to a python program. Specifically we will write a program that computes prime numbers and saves the answers into cache for quick retrieval.

EDIT: The kind people of the Internet have expressed concern with my loose use of the term cache; the techniques that follow are most accurately described as memoization.

One algorithm for determining if a number is prime follows:

prime_flag = True # default state
x = 5 # number to test
if x == 1:
    prime_flag = False
else:
    for i in range( 2, x ):
        if x % i == 0:
            prime_flag = False
            break
print prime_flag

Create a prime_flag variable to hold the answer and default it to true. Let x be the number being tested and if x is equal to 1, the x is not prime. Otherwise iterate over each number in the range of 2 to x. Let i be the current number to be tested. if x is divided by i without any remainder, x is not prime. Set the prime_flag to False and break out of the loop. Print the result.

Next we will move the algorithm into a function which will allow for code reuse:

def is_prime( x ):
    """Determine if a number is prime, return Boolean"""
    prime_flag = True
    if x == 1:
        prime_flag = False
    else:
        for i in range( 2, x ):
            if x % i == 0:
                prime_flag = False
                break
    return prime_flag

# invoke function:
print is_prime( 5 ) # True
print is_prime( 4 ) # False

This function saves us a lot of typing and enables the ability to quickly determine if a given number is prime.

Next we will use a python dictionary to implement a result cache. Also by circumstance we introduce objects and classes.

class Primer( object ):
    def __init__( self ):
        """create a cache dictionary"""
        self.cache = {}

    def is_prime( self, x ):
        """Determine if x is prime, cache and return result"""
        if x in self.cache:
            return self.cache[x] # lookup result

        prime_flag = True

        if x == 1:
            prime_flag = False
        else:
            for i in range( 2, x ):
                if x % i == 0:
                    prime_flag = False
                    break

        self.cache[x] = prime_flag # cache result
        return prime_flag

p = Primer() # create a new primer object
p.is_prime( 5 ) # True
p.is_prime( 4 ) # False
p.is_prime( 5 ) # True and fetched from cache

What is great about this solution is that we can avoid looping and computation if an answer is already in cache. Looking up a cached result is much more efficient and will ultimately make a program feel more responsive.

Determining if 97352613 is prime takes my laptop nearly 18 seconds. Fetching the cached result seems to happen instantly.

>>> s1 = time();p.is_prime( 97352613 );e1 = time()
False # not prime
>>> s2 = time();p.is_prime( 97352613 );e2 = time()
False # not prime from cache
>>> e1 - s1
17.970067977905273 # seconds
>>> e2 - s2
2.5987625122070312e-05 # or approx .000026 seconds

A look-up will always beat a computation. Anything that can be cached, should be cached. I hope this helps clear things up.