On Fri, 2006-10-13 at 01:27 +0300, Silviu Gheorghe wrote:
it does, thank you very much for the quick answer, unfortunately as I understand it, it doesn't work well on ints :(
for just now i created a list
slowFunctionCacheList= [slowFunction (i) | i <-[0..5000000]] and use "slowFunctionCacheList !! i" instead of "slowFunction (i)"
it helped alot (i mean i stoped the program after "3 hours still working" and got the result in 2 minutes :))
i am still curious about a better method (and a general one), because this is ugly, and it only works on ints as i see it.
I can describe a method that's uglier, faster, and more general; is that better or not? You're using an infinite list to store your cached results. (Well, your list is actually finite, but an infinite list would work just as well.) Instead of using an infinite list, you can use an infinite binary tree, with a cached result at every node. Construct a binary tree with the following property: Consider the path from the root to a node, where left branches are called "0" and right branches are called "1". This sequence of 0's and 1's is the binary expansion of the key whose cached value is stored at that node (with the least-significant-bit at the root of the tree). (Actually constructing this tree, and looking things up in it, is left as an exercise for the reader; but it isn't very hard.) This generalizes to any kind of key that can be uniquely serialized into bits; looking up the corresponding value then takes O(# of bits in the key) extra time and space, which is far better than the O(2^(# of bits in the key)) that an infinite list would use. Carl Witty