Create a gist now

Instantly share code, notes, and snippets.

Source file to play with the C++14 memoize method, see http://cpphappyfunhouse.com/posts/2014/6/memo-this.html
#include <iostream>
#include <functional>
#include <unordered_map>
#include <chrono>
// This file was tested only in clang 3.4
// It requires -std=c++1y and a stdlib conforming to at least C++11
template <typename T, typename U>
auto memoize(std::function<U(T)>&& f) {
return [memo = std::unordered_map<T, U>(), f](const T& t) mutable {
auto have = memo.find(t);
if (have != memo.end())
return memo[t];
U val = f(t);
memo[t] = val;
return val;
};
}
template <typename F>
void timeTest(F&& f) {
namespace k = std::chrono;
auto t0 = k::high_resolution_clock::now();
f();
auto t1 = k::high_resolution_clock::now();
std::cout << "time: " << k::duration_cast<k::microseconds>(t1 - t0).count() << "µs\n";
}
double fibslow(int n) {
return n < 2 ? double(n) : fibslow(n - 2) + fibslow(n - 1);
}
int main(int argc, char *argv[]) {
std::function<double(int)> fib = memoize<int, double>([&fib](int n) {
return n < 2 ? double(n) : fib(n - 2) + fib(n - 1);
});
// note: running both profiles in the same program will affect execution time
// of whichever test comes second, so comment one out.
timeTest([] {
std::cout << "φ slow = " << fibslow(45) / fibslow(44) << "\n";
});
timeTest([&fib] {
std::cout << "φ = " << fib(45) / fib(44) << "\n";
});
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment