Source file to play with the C++14 memoize method

memoize.cpp

#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";
	});
}