// Write code that computes the Fibonacci sequance upto n #include <cstdint> #include <vector> #include <iostream> #include <functional> #include <chrono> // Recursive implementations of Fibonacci are all the rage in a teaching // environment as it demonstrates recursion nicely. The problem is that a recursive // implementation is completely a inefficient way to code the task in practice. // Each call of function calls 2 more and those 2 call 2 more each resulting in 4. // And those 4 call 4 more each resulting in 8 so at this point your space and time // complexity is 1 + 2 + 4 + 8 + ... which is exponential growth and just awful uint32_t fib_naive(uint32_t n) { if (n == 0) return 0; if (n == 1) return 1; return fib_naive(n-1) + fib_naive(n-2); } // So what google is really testing here is the "dynamic programming" paradigm. // https://en.wikipedia.org/wiki/Dynamic_programming. Unfortunately the term // "dynamic programming" has had its meaning diluted and corrupted a bit. In // this context what it means is the breaking of a larger problem into sub // parts and solving each sub part to solve the whole. This sounds exactly // like recursion and it is, the distinction is that recursive implementations // tend to stop at raw mathematical conversion where as DP implementations look // at lazy caching results to cut off repeated computations // There are two textbook approaches to this; top-down and bottom-up // in the top-down approach you start working from the answer point and compute // the values of the breakdowns, you deploy memory as needed to cache the // results of prior computations so that if they are used again you use the // cached value rather than recomputing it from scratch again uint32_t fib_top_core(uint32_t n, std::vector<uint32_t>& cache) { if (n > 0 and cache[n] == 0) { cache[n] = fib_top_core(n-2,cache) + fib_top_core(n-1,cache); } return cache[n]; } uint32_t fib_top(uint32_t n) { if (n == 0) return 0; std::vector<uint32_t> cache(n+1, 0); cache[1] = 1; return fib_top_core(n, cache); } // in the bottom-up approach you start working from the known terminators // and work your way up to the answer point. You do this by computing // the values of all the breakdowns you could possibly need and memorize // these the results for use in the next computations. Often you can optimize // the memory to forget values that we know we will not revisit uint32_t fib_bot(uint32_t n) { if (n == 0) return 0; uint32_t fib_minus_2 = 0; uint32_t fib_minus_1 = 0; uint32_t fib_current = 1; while (n > 1) { fib_minus_2 = fib_minus_1; fib_minus_1 = fib_current; fib_current = fib_minus_2 + fib_minus_1; --n; } return fib_current; } void test(std::function<uint32_t(uint32_t)> func, uint32_t n) { auto start = std::chrono::system_clock::now(); std::cout << "result:" << func(n); auto end = std::chrono::system_clock::now(); std::cout << " -- time:" << std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count() << "nSec\n"; } int main() { int n = 40; test(fib_naive,n); test(fib_top ,n); test(fib_bot ,n); }

and the output looks like:

result:102334155 -- time:1282786361 nSec result:102334155 -- time:51012 nSec result:102334155 -- time:690 nSec

## No comments:

## Post a Comment