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 指出的，在第一种情况下，sort 方法是在已经排好序的数据上工作，而在第二种情况下，sorted 则是在新的数据上反复进行排序。

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

"""
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

好的，.sort() 方法是用来直接对列表进行排序的，而 sorted() 则是创建一个新的排序列表。所以如果你的列表很大，性能差异的一部分是因为要复制数据。

不过，性能差异看起来比我预期的要大。也许 list.sort() 有一些特别的优化，而 sorted() 不能利用这些优化。比如，list 类内部已经有一个合适大小的 Py_Object*[] 数组，所以它可能能更高效地进行交换。

编辑：Alex 和 Anurag 说得对，性能差异是因为你在测试时不小心对一个已经排好序的列表进行了排序。不过，正如 Alex 的基准测试所示，list.sort() 比 sorted() 快大约 2%，这也很合理，因为复制数据会带来额外的开销。

Answer 2

因为 list.sort 是在原地排序，也就是说它会直接对原来的列表进行排序。所以第一次调用时，它会对列表进行排序，但下次调用时，你其实是在对已经排好序的列表再进行排序。

比如你可以试试这个，你会发现结果是一样的。在 timeit 的例子中，大部分时间都花在了复制上，而 sorted 还会多做一次复制。

import time
import random
test_list1=random.sample(xrange(1000),1000)
test_list2=random.sample(xrange(1000),1000)

s=time.time()
for i in range(100):
    test_list1.sort()
print time.time()-s

s=time.time()
for i in range(100):
    test_list2=sorted(test_list2)
print time.time()-s

Answer 3

你的测量错误在于：在你第一次调用 test_list1.sort() 之后，这个列表对象已经被排序了——而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 之间的区别！-)