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
_______________________________________________
Beginners mailing list
Beginners@lists.squeakfoundation.org
http://lists.squeakfoundation.org/mailman/listinfo/beginners
