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 -- http://mail.python.org/mailman/listinfo/python-list
