why memoizing is faster

[Steven D'Aprano]

On Sat, 26 Mar 2011 10:25:31 -0700, eryksun () wrote about Fibonacci 
function:

> That's true. If you need more than double precision, obviously it's time
> to defer to the experts. Here's an O(n) algorithm:
> 
> http://www.gnu.org/software/gmp/manual/html_node/Fibonacci-Numbers-
Algorithm.html


We should always prefer a well-tested, well-profiled and tuned algorithm 
for one we just made up ourselves :)

The GMP algorithm is tuned to use a small cache of (I estimate) a few 
hundred KB, and then uses bit-twiddling to generate higher numbers. That 
would be unacceptably slow in pure Python, but should be acceptable in C.

But again, notice that they are trading off time for space: they care 
more about keeping the memory footprint small than about being fast (a 
luxury you can have when programming in C, where even slow things tend to 
be fast).

[...]
> I was just shocked to see 200 MB of memory used up like chump change,

But it is chump change :)

Seriously, your point is a very good one. If writing a function that uses 
a cache, the right thing to do is to have some sort of strategy for 
dealing with the cache and preventing it from becoming unbounded in size. 
The re module has a very simple-minded strategy: when the number of items 
in the cache hits 100, delete the lot. There are far more sophisticated 
strategies possible, and also an even more simple one: document the cache 
as part of your user interface, and leave it to the caller to manage it.

But having said that, don't be scared of throwing memory at a problem to 
make it fast, especially in a language like Python.


-- 
Steven