Re: Re: Beginners Digest, Vol 18, Issue 2

Cacheing Fibonacci is a nice standard example for memoizing that we  
use in our Smalltalk course.

See:

https://www.iam.unibe.ch/scg/svn_repos/Lectures/Smalltalk/

The relevant lecture is 07BestPractice.ppt

We start with a naive solution:

Fibs>>at: anIndex
        self assert: anIndex >= 1.
        anIndex = 1 ifTrue: [ ^ 1 ].
        anIndex = 2 ifTrue: [ ^ 1 ].
        ^ (self at: anIndex - 1) + (self at: anIndex - 2)

Fibs new at: 35

works but is very slow.

We add a cache and slightly transform the #at: method:

Object subclass: #Fibs
        instanceVariableNames: 'fibCache'
        classVariableNames: ''
        poolDictionaries: ''
        category: 'Misc'

Fibs>>initialize
        fibCache := Dictionary new

Fibs>>fibCache
        ^ fibCache

Fibs>>lookup: anIndex
        ^ self fibCache at: anIndex ifAbsentPut: [ self at: anIndex ]

Fibs>>at: anIndex
        self assert: anIndex >= 1.
        anIndex = 1 ifTrue: [ ^ 1 ].
        anIndex = 2 ifTrue: [ ^ 1 ].
        ^ (self lookup: anIndex - 1) + (self lookup: anIndex - 2)

Note that the change to the at: method is minimal.

Now Fibs new at: 100
is linear and virtually instantaneous.

Now you can use this method from Integer in the obvious way:

fib
        ^ Fibs new at: self

1000 fib -->
434665576869374564356885276750406258025646605173717804024817290895365554 
179490518904038798400792551692959225930803226347752096896232398733224711 
61642996440906533187938298969649928516003704476137795166849228875

Oscar