One thing I did not address in my previous e-mail was the memory usage of the implementations. It is clear that the very heart of memoization involves a tradeoff between calculation time and memory use. The efficiency of memory use depends on the pattern of usage.
The functions memoizing results in a list use O(n) memory to store a single result for input value n. To store m values n_1...n_m takes not O(n*m) space, however, but max(n_1, ..., n_m). The stateful approach, using, say, a hash table, takes O(m) space to store m values, which is less than max(n_1, ..., n_m), unless n_m = m, in which case they are equal. It turns out in the case of the Fibonacci function that, since all input values less than the highest input value must be processed in order to compute the result, so it is no less (asymptotically) memory-efficient than the stateful version. The memoizing list has some overhead, but so does a hash table. The trie approach takes O(log n) space to store a single result. For m values n_1...n_m it takes close to O(log n_1 + ... + log n_m) for very sparse values, up to a limit of O(n_m) when all the slots for the smaller values are filled in. But, let us not forget that the stateful approach has the chance to free the memory once it's no longer needed. The declarative approach can allow the memory to be garbage-collected as soon as the references to the memoized function can be dropped. But the stateful version can choose to just memoize, say, the results for the last 100 distinct input values. Regards, Lyle Kopnicky
_________________________________________________________________________________ mozart-users mailing list [email protected] http://www.mozart-oz.org/mailman/listinfo/mozart-users
