Message404429
Divide-and-conquer approach works pretty well for larger n.
For results slightly out of the 64-bit range:
$ ./python -m pyperf timeit -s 'from math import comb' 'comb(63, 31)'
Mean +- std dev: 2.80 us +- 0.14 us -> 388 ns +- 19 ns: 7.22x faster
$ ./python -m pyperf timeit -s 'from math import comb' 'comb(111, 15)'
Mean +- std dev: 1.24 us +- 0.06 us -> 215 ns +- 18 ns: 5.76x faster
$ ./python -m pyperf timeit -s 'from math import comb' 'comb(1450, 7)'
Mean +- std dev: 654 ns +- 45 ns -> 178 ns +- 13 ns: 3.67x faster
$ ./python -m pyperf timeit -s 'from math import comb' 'comb(3329023, 3)'
Mean +- std dev: 276 ns +- 15 ns -> 175 ns +- 11 ns: 1.58x faster
For very large n:
$ ./python -m pyperf timeit 'from math import comb' 'comb(2**100, 2**10)'
Mean +- std dev: 26.2 ms +- 1.7 ms -> 3.21 ms +- 0.20 ms: 8.16x faster
$ ./python -m pyperf timeit 'from math import comb' 'comb(2**1000, 2**10)'
Mean +- std dev: 704 ms +- 15 ms -> 103 ms +- 5 ms: 6.85x faster
And it is faster than using factorial:
$ ./python -m pyperf timeit -s 'from math import comb' 'comb(100_000, 50_000)'
Mean +- std dev: 1.61 sec +- 0.02 sec -> 177 ms +- 9 ms: 9.12x faster
$ ./python -m pyperf timeit -s 'from math import factorial as fact' 'fact(100_000) // (fact(50_000)*fact(50_000))'
Mean +- std dev: 507 ms +- 20 ms
math.perm() can benefit from reusing the same code:
$ ./python -m pyperf timeit -s 'from math import perm' 'perm(63, 31)'
Mean +- std dev: 1.35 us +- 0.07 us -> 1.18 us +- 0.06 us: 1.15x faster
$ ./python -m pyperf timeit -s 'from math import perm' 'perm(111, 15)'
Mean +- std dev: 601 ns +- 35 ns -> 563 ns +- 28 ns: 1.07x faster
$ ./python -m pyperf timeit -s 'from math import perm' 'perm(2**100, 2**10)'
Mean +- std dev: 5.96 ms +- 0.29 ms -> 2.32 ms +- 0.12 ms: 2.57x faster
$ ./python -m pyperf timeit -s 'from math import perm' 'perm(2**1000, 2**10)'
Mean +- std dev: 486 ms +- 14 ms -> 95.7 ms +- 4.2 ms: 5.08x faster
$ ./python -m pyperf timeit -s 'from math import perm' 'perm(100_000, 50_000)'
Mean +- std dev: 639 ms +- 23 ms -> 66.6 ms +- 3.2 ms: 9.60x faster
Even in worst cases it is almost as fast as factorial:
$ ./python -m pyperf timeit -s 'from math import perm' 'perm(100_000, 100_000)'
Mean +- std dev: 2.55 sec +- 0.02 sec -> 187 ms +- 8 ms: 13.66x faster
$ ./python -m pyperf timeit -s 'from math import factorial' 'factorial(100_000)'
Mean +- std dev: 142 ms +- 7 ms |
|
Date |
User |
Action |
Args |
2021-10-20 11:47:48 | serhiy.storchaka | set | recipients:
+ serhiy.storchaka, tim.peters, rhettinger, mark.dickinson, PedanticHacker, mcognetta, pablogsal |
2021-10-20 11:47:48 | serhiy.storchaka | set | messageid: <1634730468.86.0.407730927351.issue37295@roundup.psfhosted.org> |
2021-10-20 11:47:48 | serhiy.storchaka | link | issue37295 messages |
2021-10-20 11:47:48 | serhiy.storchaka | create | |
|