3 ms·
racket/stream is lazy, so you only ever generate values when they're directly asked for, and in this case they get discarded almost immediately. This means that
by Jtsummers 5y ago
racket/stream is lazy, so you only ever generate values when they're directly asked for, and in this case they get discarded almost immediately. This means that the two sequences (fibonacci-sequence and even-fibonacci-sequence) use very little memory at any one point in time. If you switched from a lazy stream approach to a naive approach generating every single Fibonacci number below the threshold and then filtering and then summing, you'd see much worse performance. By using a lazy stream approach you end up with something that should be roughly comparable to this C-ish pseudocode, but still has the appearance of the functional map/filter/reduce style:
threshold = whatever;
accum = 0;
for (a = 0, b = 0; a <= threshold; a, b = b, a + b) { // parallel assignment invalid in C, thus pseudocode
if (a % 2 == 0) accum += a;
}
return accum;
Untested, so assuming no errors in my pseudocode. Note how this only ever has two values of the Fibonacci sequence in memory at any one point in time. The lazy stream version should be equivalent to this since it's only when you actually ask for an element of the even Fibonacci numbers that anything should be generated at all from either sequence.
Also, there is a shortcut to generate only the even Fibonacci numbers. Should reduce your execution time by a bit. Since the even Fibonacci numbers are every 3rd entry, this means you can cut out 2/3rds of the generated values and the conditional checking if a value is even or not.
- exdsq 5y agoI guess I'm surprised at the speed of lazy streams then - usually I just pre-generate the fib sequence if I need it and then filter/aggregate as you mention. Probably slightly embarrassing I've only just discovered their power after several years working in software development :)
- Jtsummers 5y agoThis is basically the way that Haskell and other lazy languages work, but also generators in Python and other languages. They're often implemented using something like coroutines or closures in languages that aren't lazy (by default), or perhaps with classes and objects. For instance, in Common Lisp you might do something like this (I'm too rusty on Racket to write it up properly) as a kind of poor man's generator/iterator/stream: (defun new-fib-sequence () (let ((a 0) (b 1)) (lambda () (shiftf a b (+ a b))))) ;; CL detail, permits parallel assignment and returns the value of the first item *before* assignment (untested, should work) and then you can repeatedly use apply or funcall (so not as clean as Scheme or Racket as lisp-1s) to generate the sequence) > (let ((fib (new-fib-sequence)) (loop repeat 3 do (print (funcall fib)))) 0 1 1 racket/stream just gives you all this without the manual elements that I'm doing here. There are libraries in CL that give you all of this, too, but I figured an illustration of what's happening behind the scenes would be useful.
- exdsq 5y agoI appreciate it, thanks!
- Jtsummers 5y agoNP. By the way, for grins I altered my program to generate only even Fibonacci numbers. I was seeing approximately 30% improvements, though I think you will see bigger improvements as you get to much larger numbers than I was testing on (on a cheap VPS box with 1 core and 4GB of RAM so I didn't really feel like stressing it too much because it was slow enough already). The changed recurrence relation is: EF(N) = Nth Even Fibonacci Numbers EF(N) = 4 * EF(N-1) + EF(N) EF(0) = 0, EF(1) = 2 This skips the generation of odd Fibonacci numbers and removes the need for the filtering step (if even then add to accumulator), but it adds in the multiplication which seems to reduce some of the potential performance gains. Once you get to the point that you're dealing with big numbers, addition becomes very expensive and, depending on how multiplication is implemented, you ought to get a larger performance boost as you get to very large numbers.
- exdsq 5y agoMultiplication is more efficient than addition? That’s surprising! I assumed multiplication would be built at least partially from addition when you’re at the lowest levels of the stack
- Jtsummers 5y agoWell, in this case because we also eliminate several additions. For each even Fibonacci number you have to perform multiple additions in the naive approach (generate all, filter): F(0) = 0 F(1) = 1 F(2) = 1 + 0 F(3) = 1 + 1 = 2 (2 additions to get here) F(4) = 2 + 1 = 3 F(5) = 3 + 2 = 5 F(6) = 5 + 3 = 8 (3 more additions to get here, and 3 for each subsequent one) With the faster version you have one multiplication and one addition (2 operations) versus 3 additions. The 3 additions naive version also has a branch that has been eliminated by just generating the even elements. EF(0) = 0 EF(1) = 2 EF(2) = 4 * 2 + 0 = 8 (1 mul, 1 add) EF(3) = 4 * 8 + 2 = 34 (1 mul, 1 add) This is why I was getting about a 30% improvement in performance, it's performing one less op (the branch itself isn't too expensive in comparison so with large numbers it's a minor cost).