Re: [Haskell-cafe] function result caching

On Friday 13 October 2006 16:15, Ketil Malde wrote:

"Silviu Gheorghe" 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