"Hen Hanna" asked:
> so... for a few days i've been revising this Code (in Gauche / Lisp /
> Scheme) to make it run faster.. and last night i could improve it enough
> to give me the result i wantedin 72 minutes or so (on my slow PC at
> home).
> ( Maybe... within a few months, i'll write the same program in Python
> to see if it runs 10 or 20 times faster. )
> this was the first time i've used Caching (memoization). - instead of
> calculating (at run-time)Factorial(x) and Combination(x,y) millions
> of times, i made 2 tables in advance...A simple Table-lookup
> (Vector-ref in Scheme) seems 100 -- 1000 times faster.
> One thought i had was... Maybe Python's Factorial(x) and Combination(x,y)
> (in Numpy ?) are already so fast that... i don't have to do the Caching
> (memoization) ???
Memoization will generally be very fast -- since it is essentially a
table-lookup. If it uses a hash-table (which is common for dictionaries), it
would be close to a constant-time access for any entry; otherwise, if it uses
some tree structure, it might be logarithmic in the number of entries in the
tree.
But that fast access comes at a price of storage -- linear with respect to the
number of items stored (versus no memory cost incurred when not memoizing).
What effect this has when you call these functions "millions of times" depends
very much one how many of those calls are on the same values.If all of the
calls have different arguments, memoization would not find it in the table yet,
and would have to recompute as normal -- and you would end up with no time
savings, but a considerable memory allocation for all of those newly-cached
values that you never retrieve. The big wins come from asking the same
questions repeatedly.
Now, as far as Python's functionality, I would not expect it to do any
memoization for you. It certainly could not predict what arguments would
provide, but it still could still have a reasonable implementation without
memoization. Your Factorial(x) and Combination(x,y) would both require a time
linear with respect to the value of x, with no memory cost incurred.
But if you were to spend most of your application asking the same questions, I
would not expect these functions to do any caching or memoization, since I
would expect very few applications would have enough calls to these functions
to make it worthwhile.So calling these functions, you can expect a linear
time for each function call, and if you expect to frequently repeat arguments,
then you should add your own memoization for an amortized linear time.
And fortunately, Python makes memoization very easy, by using a dictionary as a
default value. I've done that often for classroom purposes for cases where it
makes a big difference (recursive Fibonacci accelerates from exponential time
to linear time). And the process is straightforward enough that you could
even define a decorator that could be applied to any function you choose. I
don't have an example handy just because I never took the time to write one.
Roger Christman
Pennsylvania State University
--
https://mail.python.org/mailman/listinfo/python-list
