This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author steven.daprano
Recipients iritkatriel, oscarbenjamin, rhettinger, steven.daprano, wolma
Date 2021-09-09.12:02:18
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1631188938.67.0.732171228397.issue20499@roundup.psfhosted.org>
In-reply-to
Content
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.
History
Date User Action Args
2021-09-09 12:02:18steven.dapranosetrecipients: + steven.daprano, rhettinger, oscarbenjamin, wolma, iritkatriel
2021-09-09 12:02:18steven.dapranosetmessageid: <1631188938.67.0.732171228397.issue20499@roundup.psfhosted.org>
2021-09-09 12:02:18steven.dapranolinkissue20499 messages
2021-09-09 12:02:18steven.dapranocreate