thebjorn <BjornSteinarFjeldPettersen@gmail.com> wrote:
+---------------
| Hi, perhaps someone can help me translate my Python version? I'm slowly
| learning Lisp, but I'm out of my league on translating something like
| this still :-(
|
| def fib(n): # generate the first n numbers in the fibonacci sequence
| a,b = 0,1 # pairwise assignment a <- 0, b <-1
| for i in xrange(n-1): # i gets [0,n-1)
| yield b # save state, yield b to calling context
| a,b = b,a+b # return to here from calling context
| return
|
| # sum all numbers, n, coming from the fib generator if they're even
| x = sum(n for n in fib(200000) if n%2==0)
|
| it does 100000 in ~14 secs and 200000 in ~56 secs (the length of x is
| 20899 for 100K and 41797 for 200K).
+---------------
Someone else showed you one possible translation to Lisp, but
I suspect that the following one is closer to the spirit of what
your Python code seems to be actually doing, that is, creating
a "generator". Since Common Lisp doesn't have user-visible
continuations per se, the usual idiom in CL is to make a
"function maker" which returns a closure which encapsulates
the "continuation state", which you can later call to produce
each successive element. Unlike your "fib(n)" above, the following
version does not put an arbitrary upper limit on the number of
elements returned; you control that externally in the caller.
My results with CMUCL (in 32-bit mode) on a 1.8 GHz Athlon64
were 3.18 s & 12.92 s, respectively [I included the "system time"
since CMUCL uses page-fault traps for GC], and gave the same
number of digits (20899 & 41797, resp.) for the results as yours:
> (defun make-fibber ()
(let ((a 0)
(b 1))
(lambda ()
(prog1 b
(psetf a b
b (+ a b))))))
MAKE-FIBBER
> (compile *)
; Compiling LAMBDA NIL:
; Compiling Top-Level Form:
MAKE-FIBBER
NIL
NIL
> (loop with fib = (make-fibber) ; quick test
for i below 10
collect (funcall fib))
(1 1 2 3 5 8 13 21 34 55)
> (defun sum-even-fibs (how-many)
(let ((x (loop with fib = (make-fibber)
for i below how-many
and n = (funcall fib)
when (evenp n)
sum n)))
(ceiling (log x 10))))
SUM-EVEN-FIBS
> (compile *)
; Compiling LAMBDA (HOW-MANY):
; Compiling Top-Level Form:
SUM-EVEN-FIBS
NIL
NIL
> (time (sum-even-fibs 100000))
; Compiling LAMBDA NIL:
; Compiling Top-Level Form:
; Evaluation took:
; 3.18f0 seconds of real time
; 2.5f0 seconds of user run time
; 0.67f0 seconds of system run time
; 5,724,123,132 CPU cycles
; [Run times include 0.95f0 seconds GC run time]
; 0 page faults and
; 581,748,776 bytes consed.
;
20899
-0.6777344f0
> (time (sum-even-fibs 200000))
; Compiling LAMBDA NIL:
; Compiling Top-Level Form:
; Evaluation took:
; 12.92f0 seconds of real time
; 10.33f0 seconds of user run time
; 2.59f0 seconds of system run time
; 23,287,767,118 CPU cycles
; [Run times include 4.07f0 seconds GC run time]
; 0 page faults and
; 2,320,568,856 bytes consed.
;
41797
-0.12109375f0
>
Also unlike yours [I think, as I'm not too sure about Python's
"yield" operator], the above version allows you to create multiple
independent "fib generators", and step them independently:
> (let ((fib-vec (coerce (loop for i below 3 collect (make-fibber))
'vector)))
(loop for i below 25 do
(let* ((index (random (length fib-vec)))
(fib (funcall (aref fib-vec index))))
(format t "Fibber #~d returned ~d~%" index fib))))
Fibber #2 returned 1
Fibber #1 returned 1
Fibber #1 returned 1
Fibber #2 returned 1
Fibber #0 returned 1
Fibber #2 returned 2
Fibber #0 returned 1
Fibber #2 returned 3
Fibber #2 returned 5
Fibber #1 returned 2
Fibber #1 returned 3
Fibber #2 returned 8
Fibber #1 returned 5
Fibber #0 returned 2
Fibber #0 returned 3
Fibber #2 returned 13
Fibber #0 returned 5
Fibber #0 returned 8
Fibber #2 returned 21
Fibber #1 returned 8
Fibber #0 returned 13
Fibber #0 returned 21
Fibber #0 returned 34
Fibber #2 returned 34
Fibber #1 returned 13
NIL
>
-Rob
-----
Rob Warnock <rpw3@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607