Message105603
On Wed, May 12, 2010 at 4:50 AM, Mark Dickinson wrote:
..
> (4) I wonder whether the recursion in factorial_part_product slows things down; it might be interesting to compare with an iterative version (but still one that clumps together small pieces rather than doing lots of small*big multiplies). It seems possible that the cost of the recursive calls is insignificant compared to the cost of the various Py* calls, though.
I am attaching a little study of three different part_product
implementations in python: the recursive one, straight product, and
not-recursive binary division:
$ ./python.exe -m timeit -s "import factorial3 as fm;
fm.partial_product = fm.partial_product; f = fm.factorial " "f(10000)"
10 loops, best of 3: 66.1 msec per loop
$ ./python.exe -m timeit -s "import factorial3 as fm;
fm.partial_product = fm.partial_product1; f = fm.factorial "
"f(10000)"
10 loops, best of 3: 67.6 msec per loop
$ ./python.exe -m timeit -s "import factorial3 as fm;
fm.partial_product = fm.partial_product2; f = fm.factorial "
"f(10000)"
10 loops, best of 3: 43.4 msec per loop
The last one seems to b a clear winner, but I am not certain where the
gain comes from - no recursion or first by last instead of ith by
(i+1)st multiplication. Also python recursion overhead is probably
different from C. |
|
Date |
User |
Action |
Args |
2010-05-12 19:24:16 | belopolsky | set | recipients:
+ belopolsky, rhettinger, mark.dickinson, draghuram, stutzbach |
2010-05-12 19:24:14 | belopolsky | link | issue8692 messages |
2010-05-12 19:24:13 | belopolsky | create | |
|