[Newbies] Re: Beginners Digest, Vol 18, Issue 2

[Bert Freudenberg]

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 -