Memoization – Python and C++

Dan Bader shows a neat way to implement a simple cache and speed up your Python programs here: https://dbader.org/blog/python-memoization

He writes a generic decorator class that wraps any function with a lookup cache for each set of input arguments and uses it for an exponential complexity function — Fibonacci.

While I will defer the generic decorator class version in C++, we can implement a simple cache for each specific function, given a known set of arguments. Below is the code for a caching Fibonacci function in C++:

C++

unsigned long fibonacci(unsigned long n, bool use_cache)
{
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;

    static std::map<unsigned long, unsigned long> cache;

    if (use_cache)
    {
        if (cache.find(n) == cache.end())
            cache[n] = fibonacci(n - 1, use_cache) + fibonacci(n - 2, use_cache);
        return cache[n];
    }

    return fibonacci(n - 1, use_cache) + fibonacci(n - 2, use_cache);
}

We simply implement a static std::map that will retain it’s value for each subsequent function call, and when using the cache version of the function, check for the existence of the argument n and use it’s value, or compute it and add it to the map.

That’s pretty easy.

Here’s some output from my computer for the C++ version:

Fibonacci[35] use_cache=false:   9227465 in  0.103 s
Fibonacci[36] use_cache=false:  14930352 in  0.167 s
Fibonacci[43] use_cache=false: 433494437 in  4.821 s

Fibonacci[35] use_cache=true:   9227465 in 7.079e-06 s
Fibonacci[36] use_cache=true:  14930352 in 5.420e-07 s
Fibonacci[43] use_cache=true: 433494437 in 1.475e-06 s

Full Source code for my example is below:

C++

#include <iostream>
#include <chrono>
#include <map>
#include <iomanip>

unsigned long fibonacci(unsigned long n, bool use_cache=false);
void test_fibo(unsigned long , bool use_cache);


int main()
{
    test_fibo(35, true);
    test_fibo(36, true);
    test_fibo(43, true);

    return 0;
}



unsigned long fibonacci(unsigned long n, bool use_cache)
{
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;

    static std::map<unsigned long, unsigned long> cache;

    if (use_cache)
    {
        if (cache.find(n) == cache.end())
            cache[n] = fibonacci(n - 1, use_cache) + fibonacci(n - 2, use_cache);
        return cache[n];
    }

    return fibonacci(n - 1, use_cache) + fibonacci(n - 2, use_cache);
}

void test_fibo(unsigned long n, bool use_cache)
{
    using namespace std;

    auto start = std::chrono::high_resolution_clock::now();
    auto f = fibonacci(n,use_cache);
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> elapsed = end - start;

    cout << " Fibonacci[" << n << "] (use_cache=" << boolalpha << use_cache << "): "
        << setfill(' ') << setw(15) << f << " in "
        << scientific << setprecision(3) << setw(6) << elapsed.count() << " ms\n";
}

Memoization – Python and C++

Comments

Leave a Reply Cancel reply