3 ms·
There is one. The author's implementation of `combinations` runs in quadratic time making copies of lists on each iteration. I replaced that for `itertools.comb
by pedrovhb 4y ago
There is one. The author's implementation of `combinations` runs in quadratic time making copies of lists on each iteration. I replaced that for `itertools.combinations`, which uses an iterator, and found a pretty big difference:
~/p/not_that_slow python3.11 modified.py 5000000
-0.169075164
0.183753791
Time: 6.335 s
~/p/not_that_slow python3.11 main.py 5000000
-0.169075164
-0.169083134
Time: 48.515 s
Other than this, the only modification I made is to include a `print` statement at the end to show the time taken.
EDIT: That is not actually equivalent, my bad. The iterator is consumed and the execution ends early, I didn't realize the algorith iterated over it multiple times.