On Oct 3, 2007, at 16:49 , Bert Freudenberg wrote:
On Oct 3, 2007, at 15:55 , Mark Smithfield wrote:
I want to apply smalltalk to fibonacci numbers. I
add
this method
to Integer,
fib:
(self = 0) ifTrue: (^0)
(self = 1) ifTrue: (^1)
^ (self - 1 fib) + (self - 2 fib).
This is not Smalltalk. Blocks need square brackets, and unary
messages bind more closely that binary messages (a.k.a. operators):
fib
^self <= 1
ifTrue: [self]
ifFalse: [(self - 1) fib + (self - 2) fib]
Next, I would like to memoize this method,
(because of
the enormous performance gains). I do not see how
to
memo-ize things in smalltalk. Can somebody help me
see the necessary
shift in thinking?
I don't see why memoization would be different in
Smalltalk. Or why it
would specifically have to be, rather. You might
create a Fibonacci class
that contained an array or somesuch and cached the
numbers that had
already been called. (Slowly taking up more and more
space over time.)
So. You would have an array called Fibs or Primes, and
just stack up a collection of Primes that would hang
around?
fibMemo
^ self fibMemoizeIn: (Array new: self withAll: 0)
fibMemoizeIn: anArray
| fib |
self <= 1 ifTrue: [^self].
(fib := anArray at: self) > 0 ifTrue: [^ fib].
^ anArray at: self
put: (self - 1 fibMemoizeIn: anArray) + (self - 2 fibMemoizeIn:
anArray)
Hmm, this is better - don't need to initialize with zeroes:
fibMemo
^ self fibMemoizeIn: (Array new: self)
fibMemoizeIn: anArray
self <= 1 ifTrue: [^ self].
(anArray at: self) ifNotNilDo: [:fib | ^ fib].
^ anArray at: self
put: (self - 1 fibMemoizeIn: anArray) + (self - 2 fibMemoizeIn:
anArray)
But note that the iterative method is still faster.
- Bert -
_______________________________________________
Beginners mailing list
Beginners@lists.squeakfoundation.org
http://lists.squeakfoundation.org/mailman/listinfo/beginners
