[REBOL] Re: Fun with literal blocks!
From: lmecir:geocities at: 27-Oct-2000 9:13
Hi Joel,
picking the WYSIWYG flag and trying to answer ;-)
> How about some non-curmudgeonly comments on a unique REBOL idiom, the
> appearance of literal blocks in function bodies?
>
My purpose here is to non-curmudgeonly present a WYSIWYG approach to Rebol
programming, as I stated before.
> This can be a handy tool to *GREATLY* improve performance in some
> cases.
Not at all, see below!
> The technique, well-known in formal computing science, is
> known as memo-ization. The guinea pig of choice for demonstrating
> this technique is the old familiar Fibonacci series. That series
> (well-known to breeders of imaginary rabbits everywhere) can be
> recursively defined by knowing that
>
> Fibonacci n = if n = 0, 0
> if n = 1, 1
> otherwise, Fibonacci n-1 + Fibonacci n-2
>
> As the last line can be rewritten as
>
> Fibonacci n-2 = Fibonacci n - Fibonacci n-1
>
> we can understand Fibonacci as a total function over the integers,
> with typical small values such as
>
> n: ... -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 ...
> Fibonacci n: ... 13 -8 5 -3 2 -1 1 0 1 1 2 3 5 8 13 ...
>
> Notice that the positive and negative values have the relationship
>
> Fibonacci -n = if odd n, Fibonacci n
> if even n, - Fibonacci n
>
> With those facts in hand, we can compose the more-or-less classic
> recursive function
>
> fibo: func [n [integer!] /local t] [
> either n < 0 [
> t: fibo - n
> either odd? n [ t ][ - t ]
> ][
> either n = 0 [
> 0.0
> ][
> either n = 1 [
> 1.0
> ][
> (fibo (n - 1)) + (fibo (n - 2))
> ]
> ]
> ]
> ]
>
> This definition is correct, but performs very poorly as the argument
> becomes larger -- in fact, requiring exponential time. A quick
> benchmark confirms this (on a slow box...)
>
> for n 0 24 1 [
> wall: now/time prin [n fibo n] print [" " now/time - wall]
> ]
>
> 0 0 0:00
> 1 1 0:00
> 2 1 0:00
> 3 2 0:00
> 4 3 0:00
> 5 5 0:00
> 6 8 0:00
> 7 13 0:00
> 8 21 0:00
> 9 34 0:00
> 10 55 0:00
> 11 89 0:00
> 12 144 0:00
> 13 233 0:00
> 14 377 0:00:01
> 15 610 0:00
> 16 987 0:00
> 17 1597 0:00:01
> 18 2584 0:00:01
> 19 4181 0:00:01
> 20 6765 0:00:03
> 21 10946 0:00:03
> 22 17711 0:00:07
> 23 28657 0:00:09
> 24 46368 0:00:16
>
> Each increase by 1 of the argument multiplies the run time by about
> 1.6 (as we get large enough values to settle down).
>
> The problem, of course, is that many (most) values are computed over
> and over as the recursion descends and ascends. To illustrate the
> pattern of recursion (using an abbreviation of F for the function):
>
> F 5
> |
> -------------^-------------
> / \
> F 4 F 3
> | |
> --------^------- ----^----
> / \ / \
> F 3 F 2 F 2 F 1
> | | | |
> -----^----- ---^--- ---^--- 1
> / \ / \ / \
> F 2 F 1 F 1 F 0 F 1 F 0
> | | | | | |
> ---^--- 1 1 0 1 0
> / \
> F 1 F 0
> | |
> 1 0
>
> Computing F 5 makes the following number of calls for each argument
>
> F 5 1
> F 4 1
> F 3 2
> F 2 3
> F 1 5
> F 0 3
>
> and it only gets worse as we go up.
>
> Wouldn't it be nice to cache each value, and avoid ever computing a
> value which is in the cache? Enter the REBOL literal series!
>
> fibonacci: func [n [integer!] /local t cache] [
> cache: [1.0]
> either n < 0 [
> t: fibonacci - n
> either odd? n [ t ][ - t ]
> ][
> either n = 0 [
> 0.0
> ][
> while [n > length? cache] [append cache none]
> if none? t: pick cache n [
> poke cache n t:
> (fibonacci (n - 1)) + (fibonacci (n - 2))
> ]
> t
> ]
> ]
> ]
>
> The literal series referenced by Cache contains previously-known
> values for positive values of N, so that
>
> pick cache n = fibonacci n
>
> whenever that position in Cache has been set to a number.
>
> Since we know the base case of Fibonacci 1 = 1, we initialize the
> literal series referenced by Cache to contain 1 at position 1 (as
> in the earlier function Fibo, we'll use decimal! values to allow
> larger values to be computed without overflow).
>
> After handling negative arguments (done as in Fibo) and taking
> care of zero arguments, our modified Fibonacci function first
> ensures that Cache is big enough to save the result for the current
> argument (if it's not already). Then it checks to see if the
> result for the current argument is already available in Cache.
> It does the recursive calculation only if needed, saving the
> result into Cache. Finally, the result (retrieved or newly-
> computed) is returned.
>
> Using the same benchmark scheme as before, we see a big improvment
> in speed -- as in too fast to measure!
>
> for n 0 24 1 [
> wall: now/time prin [n fibonacci n] print [" " now/time -
> wall]
> ]
>
> 0 0 0:00
> 1 1 0:00
> 2 1 0:00
> 3 2 0:00
> 4 3 0:00
> 5 5 0:00
> 6 8 0:00
> 7 13 0:00
> 8 21 0:00
> 9 34 0:00
> 10 55 0:00
> 11 89 0:00
> 12 144 0:00
> 13 233 0:00
> 14 377 0:00
> 15 610 0:00
> 16 987 0:00
> 17 1597 0:00
> 18 2584 0:00
> 19 4181 0:00
> 20 6765 0:00
> 21 10946 0:00
> 22 17711 0:00
> 23 28657 0:00
> 24 46368 0:00
>
> Examining the function afterwards shows that the cache has been put
> to use:
>
> >> source fibonacci
> fibonacci: func [n [integer!] /local t cache][
> cache: [1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987
> 1597 2584 4181 6765 10946 17711 28657 46368]
> either n < 0 [
> t: fibonacci - n
> either odd? n [t] [- t]
> ] [
> either n = 0 [
> 0
> ] [
> while [n > length? cache] [append cache none]
> if none? t: pick cache n [
> poke cache n t:
> (fibonacci (n - 1)) + (fibonacci (n - 2))
>
> ]
> t
> ]
> ]
> ]
>
> Of course, the nice thing is that all of those cached values are
> still there, ready for any future calls to Fibonacci.
>
> Persistence pays off!
>
> -jn-
Why not use a WYSIWYG code (code which doesn't try to modify itself during
its execution, but does everything we need):
fibonacci-cache: copy [1.0]
fibonacci: function [n [integer!]] [t] [
either n < 0 [
t: fibonacci - n
either odd? n [ t ][ - t ]
][
either n = 0 [
0.0
][
insert/dup tail fibonacci-cache none n - length?
fibonacci-cache
if none? t: pick fibonacci-cache n [
poke fibonacci-cache n t:
(fibonacci (n - 1)) + (fibonacci (n - 2))
]
t
]
]
]
Regards
Ladislav
