[REBOL] Fun with literal blocks!
From: joel:neely:fedex at: 26-Oct-2000 23:25
How about some non-curmudgeonly comments on a unique REBOL idiom, the
appearance of literal blocks in function bodies?
This can be a handy tool to *GREATLY* improve performance in some
cases. 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-
