"Hen Hanna" <henhanna@gmail.com> 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 wanted in 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
> 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 wanted in 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
