Steven D'Aprano wrote:
> On Mon, 08 Jan 2007 13:55:40 +0100, Peter Otten wrote:
>
>>> The precise results depend on the version of Python you're running, the
>>> amount of memory you have, other processes running, and the details of
>>> what's in the list you are trying to sort. But as my test shows, sort
>>> has some overhead that makes it a trivial amount slower for sufficiently
>>> small lists, but for everything else you're highly unlikely to beat it.
>>
>> Try again with tN.timeit(1) and a second list that is random.shuffle()d
>> and copied to L before each measurement. list.sort() treats already
>> sorted lists specially.
>
> Or, simply shuffle the list itself. Why copy it?
To feed the same data to every algorithm. This is an act of fairness, though
with negligable impact on the benchmark results, I suspect :-)
> In my tests, sorting still wins, and by roughly the same factor.
> One optimization that might shift the balance would be to remove the
> list copying in the non-sort code (list_of_lists[1:]). That's going to be
> very time consuming for big lists.
With the tweak that you suggest above the loop wins for 100 items on my
machine...
N loop iloop max sort
1 0.000008 0.000019 0.000012 0.000010
10 0.000008 0.000008 0.000009 0.000013
100 0.000095 0.000037 0.000028 0.000088
1000 0.000374 0.000341 0.001304 0.001204
5000 0.001930 0.001719 0.001212 0.007062
if you can trust the timings for small values of N.
The script to generate this table has become somewhat baroque :-)
import random
import timeit
timers = []
def bench(f):
t = timeit.Timer("getlongest(L)", "from __main__ import %s as
getlongest, L, items; L[:] = items" % f.__name__)
t.name = f.__name__.split("_")[-1]
t.function = f
timers.append(t)
return f
@bench
def getlongest_loop(lists):
longest_list = lists[0]
longest_length = len(longest_list)
for a_list in lists[1:]:
a_length = len(a_list)
if a_length > longest_length:
longest_list, longest_length = a_list, a_length
return longest_list
@bench
def getlongest_iloop(lists):
lists = iter(lists)
longest_list = lists.next()
longest_length = len(longest_list)
for a_list in lists:
a_length = len(a_list)
if a_length > longest_length:
longest_list, longest_length = a_list, a_length
return longest_list
@bench
def getlongest_max(lists):
return max(lists, key=len)
@bench
def getlongest_sort(lists):
lists.sort(key=len)
return lists[-1]
def make_list_of_lists(length):
lol = [[None]*i for i in xrange(length)]
random.shuffle(lol)
return lol
def measure(N):
print "%10d" % N,
for t in timers:
print "%10.6f" % t.timeit(1),
print
if __name__ == "__main__":
import sys
if "--test" in sys.argv:
L = make_list_of_lists(100)
expected = [None]*99
for t in timers:
assert t.function(L[:]) == expected
raise SystemExit
L = []
print "N".rjust(10),
print " ".join(t.name.rjust(10) for t in timers)
for N in [1, 10, 100, 1000, 5000]:
items = make_list_of_lists(N)
measure(N)
Peter
--
http://mail.python.org/mailman/listinfo/python-list
