Message401465
Regarding the call to sorted that you removed.
I just realised that this was buggy! In my testing, I found that there was a consistent speed-up by summing fractions in order of increasing denominators (small denominators first):
>>> from fractions import Fraction
>>> from timeit import Timer
>>> from random import shuffle
>>>
>>> d1 = [Fraction(1, d) for d in range(1, 1000)]
>>> d2 = d1[:]
>>> shuffle(d2)
>>>
>>> t1 = Timer('sum(d)', setup='from __main__ import d1 as d')
>>> t2 = Timer('sum(d)', setup='from __main__ import d2 as d')
>>>
>>> min(t1.repeat(number=100, repeat=7)) # small dens first
1.048042511974927
>>> min(t1.repeat(number=100, repeat=7))
1.0449080819962546
>>>
>>> min(t2.repeat(number=100, repeat=7)) # random order
1.2761094039888121
>>> min(t2.repeat(number=100, repeat=7))
1.2763739289948717
Summing larger denominators before smaller denominators is even slower:
>>> d3 = list(reversed(d1))
>>> t3 = Timer('sum(d)', setup='from __main__ import d3 as d')
>>>
>>> min(t3.repeat(number=100, repeat=7)) # large dens first
1.6581684999982826
>>> min(t3.repeat(number=100, repeat=7))
1.6580656860023737
But then I screwed up by sorting the *tuples* (num, den) which would have the effect of summing small *numerators* first, not denominators.
Thanks for catching that they way I had written it, the sort would have had at best no real performance benefit. |
|
Date |
User |
Action |
Args |
2021-09-09 12:02:18 | steven.daprano | set | recipients:
+ steven.daprano, rhettinger, oscarbenjamin, wolma, iritkatriel |
2021-09-09 12:02:18 | steven.daprano | set | messageid: <1631188938.67.0.732171228397.issue20499@roundup.psfhosted.org> |
2021-09-09 12:02:18 | steven.daprano | link | issue20499 messages |
2021-09-09 12:02:18 | steven.daprano | create | |
|