[Newbies] Re: Beginners Digest, Vol 18, Issue 2
bert at freudenbergs.de
Wed Oct 3 15:03:59 UTC 2007
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
>>>> this method
>>>> to Integer,
>>>> (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):
> ^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
>>>> 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
> ^ 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:
Hmm, this is better - don't need to initialize with zeroes:
^ self fibMemoizeIn: (Array new: self)
self <= 1 ifTrue: [^ self].
(anArray at: self) ifNotNilDo: [:fib | ^ fib].
^ anArray at: self
put: (self - 1 fibMemoizeIn: anArray) + (self - 2 fibMemoizeIn:
But note that the iterative method is still faster.
- Bert -
More information about the Beginners