http://search.cpan.org/~mjd/Memoize-1.01/Memoize.pm
Memoizing' a function makes it faster by trading space for time. It
does this by caching the return values of the function in a table. If
you call the function again with the same arguments, memoize jumps in
and gives you the value out of the table, instead of letting the
function compute the value all over again.
Here is an extreme example. Consider the Fibonacci sequence, defined by
the following function:
# Compute Fibonacci numbers
sub fib {
my $n = shift;
return $n if $n < 2;
fib($n-1) + fib($n-2);
}
This function is very slow. Why? To compute fib(14), it first wants to
compute fib(13) and fib(12), and add the results. But to compute
fib(13), it first has to compute fib(12) and fib(11), and then it comes
back and computes fib(12) all over again even though the answer is the
same. And both of the times that it wants to compute fib(12), it has to
compute fib(11) from scratch, and then it has to do it again each time
it wants to compute fib(13). This function does so much recomputing of
old results that it takes a really long time to run---fib(14) makes
1,200 extra recursive calls to itself, to compute and recompute things
that it already computed.
Gavino wrote something about a perl memoization thing, though he
didn't actually demonstrate it.
Hmn, what about Lisp?
CL-USER> (defun fib (n)
(if (or (= n 0) (= n 1))
1
(+ (fib (- n 1)) (fib (- n 2)))))
FIB
CL-USER> (time (fib 20))
; Compiling LAMBDA NIL:
; In: LAMBDA NIL
; #'(LAMBDA () (FIB 20))
; Note: Return type not fixed values, so can't use known return convention:
; *
;
; Compiling Top-Level Form:
; Compilation unit finished.
; 1 note
; Evaluation took:
; 0.26 seconds of real time
; 0.252142 seconds of user run time
; 0.003793 seconds of system run time
; 377,892,636 CPU cycles
; 0 page faults and
; 4,277,864 bytes consed.
;
10946
CL-USER> (time (fib 25))
; Compiling LAMBDA NIL:
; In: LAMBDA NIL
; #'(LAMBDA () (FIB 25))
; Note: Return type not fixed values, so can't use known return convention:
; *
;
; Compiling Top-Level Form:
; Compilation unit finished.
; 1 note
; Evaluation took:
; 2.99 seconds of real time
; 2.944418 seconds of user run time
; 0.032573 seconds of system run time
; 4,376,197,122 CPU cycles
; [Run times include 0.17 seconds GC run time]
; 0 page faults and
; 47,474,200 bytes consed.
;
121393
Dang, this is starting to get slow. I'll just use the Lisp speeder-upper:
CL-USER> (speed-up 'fib)
FIB
CL-USER> (time (fib 25))
; Compiling LAMBDA NIL:
; In: LAMBDA NIL
; #'(LAMBDA () (FIB 25))
; Note: Return type not fixed values, so can't use known return convention:
; *
;
; Compiling Top-Level Form:
; Compilation unit finished.
; 1 note
; Evaluation took:
; 0.0 seconds of real time
; 5.19e-4 seconds of user run time
; 0.0 seconds of system run time
; 750,643 CPU cycles
; 0 page faults and
; 6,656 bytes consed.
;
121393
CL-USER> (time (fib 30))
; Compiling LAMBDA NIL:
; In: LAMBDA NIL
; #'(LAMBDA () (FIB 30))
; Note: Return type not fixed values, so can't use known return convention:
; *
;
; Compiling Top-Level Form:
; Compilation unit finished.
; 1 note
; Evaluation took:
; 0.0 seconds of real time
; 2.0e-4 seconds of user run time
; 0.0 seconds of system run time
; 281,586 CPU cycles
; 0 page faults and
; 1,360 bytes consed.
;
1346269
CL-USER> (time (fib 35))
; Compiling LAMBDA NIL:
; In: LAMBDA NIL
; #'(LAMBDA () (FIB 35))
; Note: Return type not fixed values, so can't use known return convention:
; *
;
; Compiling Top-Level Form:
; Compilation unit finished.
; 1 note
; Evaluation took:
; 0.0 seconds of real time
; 1.9e-4 seconds of user run time
; 0.0 seconds of system run time
; 268,289 CPU cycles
; 0 page faults and
; 1,360 bytes consed.
;
14930352
CL-USER> (time (fib 100))
; Compiling LAMBDA NIL:
; In: LAMBDA NIL
; #'(LAMBDA () (FIB 100))
; Note: Return type not fixed values, so can't use known return convention:
; *
;
; Compiling Top-Level Form:
; Compilation unit finished.
; 1 note
; Evaluation took:
; 0.0 seconds of real time
; 0.001111 seconds of user run time
; 5.1e-5 seconds of system run time
; 1,692,960 CPU cycles
; 0 page faults and
; 23,528 bytes consed.
;
573147844013817084101
CL-USER>
No, the speeder-upper is not a compiler. I suppose I could have
compiled the code, but it turned out not to be necessary.
The "speed-up" call is actually a call to a memoize package from back
in the early '90s.
--
Fred Gilham ······@csl.sri.com
And so the Russian people made do on whatever ration of rice and suet
the stores were handing out to the people waiting in the interminable
lines in the dark and the snow that week; they went to sleep hungry
and malnourished but much cheered by the certainty that no greedy
capitalists were making obscene profits by actually delivering them
any chicken.
gavino wrote:
[nothing original -- shock! snipped pasted description of naive Fibonacci fn]
Dude, you can write shitty algorithms in any language.
Did you ever try PLT Scheme, by the way? Like you said
you were going to, here:
http://groups.google.com/group/comp.lang.scheme/msg/3f2979f8d6e16845
-- JK
I'm on chapter 4, it is really cool.
That is pasted from the cpan module !!!
Why do people think I am plagarizing lol
The point is he is correcting perl function that repeats itself, I
don't think lisp does this does it?
I am pretty sure haskell would avoid this with lazy evaluation?
but maybe not
maybe this is smart to cache the results of a function in a table
gavino wrote:
> maybe this is smart to cache the results of a function in a table
Where did you study computer science? Wasn't memoization covered in one
of the core algorithms courses? I learned about it in CPSC 320, at UBC.
(message (Hello 'gavino)
(you :wrote :on '(8 Dec 2006 15:32:17 -0800))
(
g> The point is he is correcting perl function that repeats itself, I
g> don't think lisp does this does it?
g> I am pretty sure haskell would avoid this with lazy evaluation?
no, you can code ineffective Fib both in lisp and haskell.
actually i've thought that Haskell can somehow automagically optimize it,
but not -- it does exactly what's written, so you'll have to optmize it
explicitly (implement fibs as a lazy list)
)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
"People who lust for the Feel of keys on their fingertips (c) Inity")
gavino wrote:
> If you call the function again with the same arguments, memoize jumps
> in and gives you the value out of the table, instead of letting the
> function compute the value all over again.
Sounds to me like a sorry substitute for dynamic programming
http://en.wikipedia.org/wiki/Dynamic_programming
Something interesting somewhat related to memoizing...
http://common-lisp.net/project/computed-class/
Features/Status
Computed CLOS slots
Capturable computed lexical variables with clet
Standalone cells with public reader and writer api (called
computed-state-value) for accessing the computed state when using in
advances user specific scenarios.
Memoizer-like defcfun that keeps a memoize cache of a side-effect-free
defun. Functions defined by defcfun automatically drop and recalculate
memoize entries when any cell is invalidated that was read while
calculating the memoize entry in question.
levy
Here's a piece of code from Peter Norvig's PAIP. I hope that works for
you.
;;; Usage:
;;; 1. define a function fn
;;; 2. (memoize 'fn [:key ... :test])
(defun memo (fn name key test)
"Return a memo-function of fn."
(let ((table (make-hash-table :test test)))
(setf (get name 'memo) table) ; use p-list to store the hash
table, so that it could be cleared.
#'(lambda (&rest args)
(let ((k (funcall key args)))
(multiple-value-bind (value found?)
(gethash k table)
(if found?
value
(setf (gethash k table) (apply fn args))))))))
;;; any combination of arguments as the key can be memoized.
;;; The default is to memoize only the first argument.
;;; If you want to use all the arguments, specify INDENTITY as the key.
(defun memoize (fn-name &key (key #'first) (test #'eql))
"Replace fn-name's global definition with a memoized version."
(setf (symbol-function fn-name)
(memo (symbol-function fn-name) fn-name key test)))
(defun clear-memoize (fn-name)
"Clear the hash table from a memo function."
(let ((table (get fn-name 'memo)))
(when table (clrhash table))))
==========================================
Here's the test result.
CL-USER> (time (fib 35))
Evaluation took:
0.784 seconds of real time
0.782312 seconds of user run time
5.44e-4 seconds of system run time
0 calls to %EVAL
0 page faults and
0 bytes consed.
14930352
CL-USER> (memoize 'fib)
#<CLOSURE (LAMBDA (&REST ARGS)) {11A92AA5}>
CL-USER> (time (fib 35))
Evaluation took:
0.0 seconds of real time
4.4e-5 seconds of user run time
2.e-6 seconds of system run time
0 calls to %EVAL
0 page faults and
0 bytes consed.
14930352
PS. The code seems not working with compiled function in AllegroCL. I
haven't figured out why.
> (defun memoize (fn-name &key (key #'first) (test #'eql))
BTW, If you want to memoize on several arguments, be sure to change the
test function to #'equal or your own function. If you forget to do
that, nothing will be memoized and the hash table will grow infinitely
because every time the function is called, its arguments are (almost)
recognized as different keys (by using default test function eql).
The another problem is that the stack might be exhausted when solving
complex recursive problems. (ackermann 3 11) and (ackermann 4 4) will
tell the difference.
Pebblestone wrote:
> PS. The code seems not working with compiled function in AllegroCL. I
> haven't figured out why.
Probably because the compiler does tail call optimization, which
removes the calls that the memoizer would use to retrieve the already
computed values.
Usually there's a way to turn this off, but I don't know what it is
for ACL.
--
Fred Gilham ······@csl.sri.com
I wish I could get the product I sell to become a human right. Then
people would be forced to pay for it and use it. The only drawback is
that, like schoolteachers, I probably would wind up actually doing
something else.
Fred Gilham <······@snapdragon.csl.sri.com> writes:
> Probably because the compiler does tail call optimization, which
> removes the calls that the memoizer would use to retrieve the already
> computed values.
>
> Usually there's a way to turn this off, but I don't know what it is
> for ACL.
As for every ANSI CL: (declaim (notinline fib))
Nicolas