On Jan 26, 2006, at 4:18 PM, Dave Howell wrote:

>
> On Jan 26, 2006, at 12:59, John Carter wrote:
>
>> OK, so this trick cannot be used everywhere.
>>
>> Suppose @@memo is a brand spanking new empty Hash object.
>>
>> What does @@memo["pink"] return?
>>
>> By default it returns nil.
>>
>> But you can make it return whatever you damn well feel like.
>>
>> @@memo = Hash.new{|hash,key| hash[key] = Car.new(key)}
>>
>> @@memo["pink"]
>>
>> Will say, oo, I have no "pink" element,  I better go off and make  
>> one then, fortunately I have a block on my "new" so I know how to  
>> do that.
>>
>> ps.
>>
>> If everybody in your country had a pink car, what would you have?
>
> Ha ha. Except that if everybody in my country had a Car.create_car 
> ("pink") car, then the entire country would have exactly one car. I  
> can't figure out what it's good for; any example I can think of in  
> my head is just a complicated way of doing something simple. Either  
> "well, I'll just keep the object around in the first place," or  
> "no, I would have to have my very OWN pink car, not be FlexCar-ing  
> it with other parts of the program"
>
>

Often memoization is used to speed up functions that are  
referentially transparent

( Referentially transparent means that
given a function f, a == b implies that f(a) == f(b). In other words,  
if you call the function with the same argument, more than once  
you'll always get back the same answer. def f(x); x +1; end is  
referentially transparent. Well, unless someone has been playing with  
Integer#+. IO#gets for instance is not.)

when they take a long time to process. One example is computing the  
fibonacci sequence (an equally silly example as the car.). If you use  
memoization, all of a sudden the naive recursive implementation isn't  
nearly as bad.

since f(0 or 1) = 1
     and f(x) = f(x - 1) + f(x - 2)
you'll notice that f(x) = f(x - 2) + f(x - 3) + f(x - 2). Since we  
are memoizing, it only computes f(x-2) once, the second time it needs  
f(x-2) its an O(1) hash lookup, and so on. Normally of course  
recursive fibonacci is O(2**n).