Source file to play with the C++14 memoize method
#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