[Haskell-cafe] function result caching

[Robert Dockins]

On Friday 13 October 2006 16:15, Ketil Malde wrote:
> "Silviu Gheorghe" <ghesil.lists at gmail.com> writes:
> > slowFunctionCacheList= [slowFunction (i) | i <-[0..5000000]]
> > and use "slowFunctionCacheList !! i" instead of "slowFunction (i)"
> >
> > i am still curious about a better method (and a general one)
>
> Not much different in principle, but better in practice - you could
> use an array rather than a list.  O(1) lookups should make things (a
> lot) faster.

Well, this is true only if the range of the domain function is small and 
fairly dense.  He said it was large and sparsely populated.  

With 5000000 elements, you're looking at allocating about 20Mb of memory _just 
to hold pointers to closures_ and then allocating and filling out 5000000 
closures, all before you get down to doing any real work!  That's just not 
going to be very fast.  You're going to take a HUGE constant runtime and 
space penalty for that O(1) lookup.

Little-endian patricia trees are probably the right way to go here (which I 
think has been mentioned already).  You get O(log n) lookup and good behavior 
for a sparse and/or infinite domain because only the parts of the tree that 
are explored get unfolded.


> -k

-- 
Rob Dockins

Talk softly and drive a Sherman tank.
Laugh hard, it's a long way to the bank.
       -- TMBG