Message404208
Microbenchmarks:
$ ./python -m pyperf timeit -s 'from math import comb' '[comb(n, k) for n in range(63) for k in range(n+1)]'
Mean +- std dev: 1.57 ms +- 0.07 ms -> 209 us +- 11 us: 7.53x faster
$ ./python -m pyperf timeit -s 'from math import comb' 'comb(62, 31)'
Mean +- std dev: 2.95 us +- 0.14 us -> 296 ns +- 11 ns: 9.99x faster
$ ./python -m pyperf timeit -s 'from math import comb' 'comb(110, 15)'
Mean +- std dev: 1.33 us +- 0.06 us -> 95.8 ns +- 3.1 ns: 13.86x faster
$ ./python -m pyperf timeit -s 'from math import comb' 'comb(1449, 7)'
Mean +- std dev: 689 ns +- 33 ns -> 59.0 ns +- 3.2 ns: 11.69x faster
$ ./python -m pyperf timeit -s 'from math import comb' 'comb(3329022, 3)'
Mean +- std dev: 308 ns +- 19 ns -> 57.2 ns +- 4.2 ns: 5.39x faster
Now I want to try to optimize for larger arguments. Perhaps using recursive formula C(n, k) = C(n, j)*C(n-j, k-j)//C(k, j) where j=k//2 could help. |
|
Date |
User |
Action |
Args |
2021-10-18 18:49:26 | serhiy.storchaka | set | recipients:
+ serhiy.storchaka, tim.peters, rhettinger, mark.dickinson, PedanticHacker, mcognetta, pablogsal |
2021-10-18 18:49:26 | serhiy.storchaka | set | messageid: <1634582966.04.0.182201022595.issue37295@roundup.psfhosted.org> |
2021-10-18 18:49:26 | serhiy.storchaka | link | issue37295 messages |
2021-10-18 18:49:25 | serhiy.storchaka | create | |
|