列表上的 Python sort() 方法与内置 sorted() 函数

Question

我知道 __builtin__ sorted() 函数适用于任何可迭代对象。但是有人可以解释 anylist.sort() 与 sorted(anylist) 之间的巨大(10 倍)性能差异吗？另外，请指出我是否在测量方式上做错了什么。

"""
Example Output:
$ python list_sort_timeit.py 
Using sort method: 20.0662879944
Using sorted builin method: 259.009809017
"""

import random
import timeit

print 'Using sort method:',
x = min(timeit.Timer("test_list1.sort()","import random;test_list1=random.sample(xrange(1000),1000)").repeat())
print x

print 'Using sorted builin method:',
x =  min(timeit.Timer("sorted(test_list2)","import random;test_list2=random.sample(xrange(1000),1000)").repeat())
print x

---

正如标题所说，我对比较 list.sort() 和 sorted(list) 很感兴趣。上面的代码片段显示了一些有趣的东西，python 的排序函数对于已经排序的数据表现得非常好。正如 Anurag 所指出的，在第一种情况下，排序方法正在处理已经排序的数据，而在第二次排序中，它正在处理新的数据以一次又一次地工作。

所以我写了这个来测试，是的，它们非常接近。

"""
Example Output:
$ python list_sort_timeit.py 
Using sort method: 19.0166599751
Using sorted builin method: 23.203567028
"""

import random
import timeit

print 'Using sort method:',
x = min(timeit.Timer("test_list1.sort()","import random;test_list1=random.sample(xrange(1000),1000);test_list1.sort()").repeat())
print x

print 'Using sorted builin method:',
x =  min(timeit.Timer("sorted(test_list2)","import random;test_list2=random.sample(xrange(1000),1000);test_list2.sort()").repeat())
print x

哦，我看到 Alex Martelli 回复了，因为我正在输入这个......(我将离开编辑，因为它可能有用)。

Answer 1

您的测量错误如下:在您第一次调用 test_list1.sort() 后，该列表对象 IS 已排序 - 并且 Python 的排序，即 timsort ，在已经排序的列表中快得快!!!这是使用 timeit 时最常见的错误——不经意间产生副作用而没有考虑到它们。

这是一组很好的测量，最好使用命令行中的 timeit:

$ python -mtimeit -s'import random; x=range(1000); random.shuffle(x)' '
y=list(x); y.sort()'
1000 loops, best of 3: 452 usec per loop
$ python -mtimeit -s'import random; x=range(1000); random.shuffle(x)' '
x.sort()'
10000 loops, best of 3: 37.4 usec per loop
$ python -mtimeit -s'import random; x=range(1000); random.shuffle(x)' '
sorted(x)'
1000 loops, best of 3: 462 usec per loop

如您所见，y.sort() 和 sorted(x) 并驾齐驱，但 x.sort() 感谢副作用获得超过一个数量级的优势 - 只是因为您的测量错误:这并没有告诉您 sort 与 sorted 本身的任何关系! -)