Introduction Edit

If we perform many costly queries, then caching commonly-issued queries along with the results we got in memory is likely to increase the overall performance of the program. Caching is implemented in all kinds of software - from operating system kernels that hold recently-accessed file-system entries in cache, to database servers that keep caches of the various stages of the queries given to them.

There's a variation on caching called Memoization, in which we never relieve of our results. It can be demonstrated that by memoizing the naïve (tree-recursive) Fibonacci-number calculation, one can actually reduce its complexity from an exponential one to a linear one.

One should note that caching or memoization cannot be done in many cases, for example, if the queries have most kinds of side-effects.

Example Edit

Let's suppose we have the following naïve tree-recursive algorithm for the Fibonacci numbers :

  integer fib(n):
        if n == 0 or n == 1 then
             return 1
             return fib(n-1) + fib(n-2)
   end function

This will have exponential complexity. However, if we memoize the results, we can have the following:

   Cache = { 0 => 1 , 1 => 1 }
   integer fib(n):
        if (! exists(Cache[n])) then
            Cache[n] = fib(n-1) + fib(n-2)
        return Cache[n]
   end function

This has a linear running time (but see Peteris Krumins' vital correction for its complexity when being used for large numbers).

Attribution Edit