Author | Message |
---|---|
rabbott
Posts: 1649
|
Posted 21:30 Oct 04, 2013 |
Daanyaal Syed did a nice experiment to determine how much memoizing helps. Here is how his code (slightly modified) runs in a worksheet. You can see that the archive makes an enormous(!) difference. (fibArchive is defined inside the outer function to ensure that it starts with a fresh archive. Of course to make best use of an archive you don't want to do this but want to accumulate results from call to call.) But using the helper function is even faster. def fibonacciWithArchiveOption(n: Int, useArchive: Boolean): Int = { var fibArchive = Map[Int, Int]() // Create a new archive def fibonacci(n: Int): Int = { if (useArchive) fibArchive += n -> value fibonacci(n)
// Do you get the same answers with and without the archive? Yes. (1 to 5).map(fibonacciWithArchiveOption(_, false)) == (1 to 5).map(fibonacciWithArchiveOption(_, true)) def fibonacciWithHelper(n: Int): Int = { def fibonacciHelper(prevFib: Int, fibSoFar: Int, upTo: Int): Int = { fibonacciHelper(0, 1, 1)
// Do you get the same answers recursively and with the helper? Yes. (1 to 5).map(fibonacciWithArchiveOption(_, false)) == (1 to 5).map(fibonacciWithHelper(_)) //> res1: Boolean = true
// This function times the evaluation of its argument. def time[A](f: => A) = {
// The time recursively without the archive. time { fibonacciWithArchiveOption(46, false) } //> time: 11712.123557ms // The time recursively with the archive. (Much faster.) time { fibonacciWithArchiveOption(46, true) } //> time: 0.765622ms // The time using the helper function. (Even faster.) time { fibonacciWithHelper(46) } //> time: 0.023811ms
Would an archive help fibonacciWithHelper? If you think about it, the answer is that it would not because fibonacciWithHelper never makes a call to a possibly pre-computed fibonacci number. One could modify fibonacciWithHelper so that it could make use of an archive, but doing so would be a bit of work.The job would be to check the archive to see if the desired number has already been computed. If not, see what the largest number in the archive is and start the helper function from there rather than from 1. Also, fibonacciWithHelper should insert every fibonacci number it computes into the archive. That's the first thing the internal fibonacciHelper function should do. (If anyone takes this on, please post your code.) Last edited by rabbott at
09:36 Oct 05, 2013.
|
daanyaalasyed
Posts: 4
|
Posted 14:53 Oct 05, 2013 |
This is the implementation I came up with:
The helper function seems to only benefit from the archive when large prime numbers are calculated. But even without an archive it's pretty fast! However, if I add this line:
to the beginning of fibonacciHelper (to attempt to insert every number computed by the helper to the archive), the run time is slower for all tests, and it calculates a big prime much slower when using the archive.
My guess is that it is slowing down because it is adding redundant entries to the archive, but I haven't yet found a solution. |