On Sat, Mar 12, 2011 at 9:17 PM, Terry Reedy <tjre...@udel.edu> wrote:
> But in this case, they are much slower. To be faster, one would need > something like "key=lambda p,q:p*(lcm//q)", where lcm is the least common > multiple of of all the q's (denominators). For the example above, lcm = 700. > But for longer lists, it could be outrageously large. > You can get away with less precision. It's okay if the key function loses some information, as long as it still has enough to distinguish each pair of numbers. In other words, you just need a number that's at least as large as the largest lcm between any pair: max_denominator_sq = max(q for p, q in fraction_list) ** 2 # Strictly larger than the lcm between any pair fraction_list.sort(key=lambda p, q: p*max_denominator_sq//q) Using the above, key is 4 times faster than cmp in Python2.6: stutzbach-glaptop:~$ python2.6 -m timeit -s 'fractions = [(i, j) for i in range(100) for j in range(1, 100)]' 'sorted(fractions, cmp=lambda (p,q),(r,s): cmp(p*s, q*r))' 10 loops, best of 3: 23.3 msec per loop stutzbach-glaptop:~$ python2.6 -m timeit -s 'fractions = [(i, j) for i in range(100) for j in range(1, 100)]' 'max_denominator_sq = max(q for p, q in fractions)**2' (1,2), (3,4), (0,5), (9,100), (3,7), (2,8)'sorted(fractions, key=lambda t: t[0]*max_denominator_sq//t[1])' 100 loops, best of 3: 5.52 msec per loop with a further speed improvement in 3.2: stutzbach-glaptop:~$ ~/python/cpython-3.2/python -m timeit -s 'fractions = [(i, j) for i in range(100) for j in range(1, 100)]' 'max_denominator_sq = max(q for p, q in fractions)**2' 'sorted(fractions, key=lambda t: t[0]*max_denominator_sq//t[1])' 100 loops, best of 3: 4.89 msec per loop and more speed improvements with my experimental changes targeting 3.3 (not yet in the bug tracker): :-) stutzbach-glaptop:~$ ~/python/cpython/python -m timeit -s 'fractions = [(i, j) for i in range(100) for j in range(1, 100)]' 'max_denominator_sq = max(q for p, q in fractions)**2' 'sorted(fractions, key=lambda t: t[0]*max_denominator_sq//t[1])' 100 loops, best of 3: 3.73 msec per loop -- Daniel Stutzbach
_______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
