[Haskell-cafe] function result caching
robdockins at fastmail.fm
Fri Oct 13 16:35:12 EDT 2006
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.
Talk softly and drive a Sherman tank.
Laugh hard, it's a long way to the bank.
More information about the Haskell-Cafe