Python中list的sort()方法和内置的sorted()函数的区别

Question

我知道__builtin__ sorted()函数适用于任何可迭代对象。但是有人能解释一下为什么anylist.sort()和sorted(anylist)之间会有这么大（10倍）的性能差异吗？如果我测量的方式有误，请指出来。

"""
示例输出：
$ python list_sort_timeit.py 
使用sort方法：20.0662879944
使用排序内置方法：259.009809017
"""
import random
import timeit

print '使用sort方法：',
x = min(timeit.Timer("test_list1.sort()", "import random;test_list1=random.sample(xrange(1000),1000)").repeat())
print x

print '使用排序内置方法：',
x =  min(timeit.Timer("sorted(test_list2)", "import random;test_list2=random.sample(xrange(1000),1000)").repeat())
print x

---

如标题所述，我想比较list.sort()和sorted(list)。上面的片段显示了一个有趣的事实，Python的sort函数对已经排序的数据表现非常好。正如Anurag所指出的，在第一个情况中，sort方法处理的是已经排序的数据，而在第二个情况中，sorted方法在新的数据上工作，需要重复进行排序。

因此，我编写了这个测试脚本，并且发现它们非常接近。

"""
示例输出：
$ python list_sort_timeit.py 
使用sort方法：19.0166599751
使用排序内置方法：23.203567028
"""
import random
import timeit

print '使用sort方法：',
x = min(timeit.Timer("test_list1.sort()", "import random;test_list1=random.sample(xrange(1000),1000);test_list1.sort()").repeat())
print x

print '使用排序内置方法：',
x =  min(timeit.Timer("sorted(test_list2)", "import random;test_list2=random.sample(xrange(1000),1000);test_list2.sort()").repeat())
print x

哦，我看到Alex Martelli正在回答，正如我打字时一样...（我会保留编辑，因为它可能很有用）。

- Senthil Kumaran

---

顺便说一下，既然这是一个有合法答案的问题，它可能不应该成为社区维基。 - Daniel Pryden

好的，我会记住的，丹尼尔。这是一个很好的指示。 - Senthil Kumaran

Answer 1

您的测量误差如下：在第一次调用 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本身有何区别！-)

- Alex Martelli

---

谢谢Alex！你能解释一下为什么原地排序所需的时间略少于sorted()返回的列表吗？Daniel提到了复制，但我们还没有复制任何东西，对吧？我假设由sorted()生成的已排序列表是一个内存操作，当它返回时，会分配一个新的列表对象。 - Senthil Kumaran

@Senthil：列表中的对象不应该被复制，但是列表本身是需要的（例如，y = sorted(x) 后，你有了 x 和 y 两个副本）。因此，至少 sorted() 调用需要一个 malloc(n * sizeof(PyObject *)) 并且需要将 n 指针从第一个列表复制到新列表中。我猜测，复制这些 n 指针弥补了 Alex 基准测试显示的大约2% 的时间差异。 - Daniel Pryden

我还比较了在迭代器上使用list.sort()和sorted()的结果，看起来是等效的： python -mtimeit -s 'import random; [random.random() for x in xrange(1000)].sort()': 100000000 loops, best of 3: 0.00899 usec per loop 和 python -mtimeit -s 'import random; sorted(random.random() for x in xrange(1000))': 100000000 loops, best of 3: 0.00891 usec per loop。 - dtheodor

@SenthilKumaran：在性能上没有实际差异；每次运行时，值被以不同的方式进行“shuffle”（每次Python启动时都会重新种子化“random”），因此数据在每次运行时的顺序是不同的（Python的TimSort利用现有的排序，因此不同的随机输入可能会产生有意义的差异）。如果使其保持一致（在设置中在random.shuffle之前调用random.seed(1)，使得x在每次运行时都相同），差异将降低到大约1微秒，这似乎是由于CPython C级别参数解析和字节码调度中的次要实现细节。 - ShadowRanger

oops. fixed: list().sort(): $ python -mtimeit -s 'import random' -s 'i = (random.random() for x in xrange(1000))' 'list(i).sort()' 1000000 次循环，3 次中的最佳值：每个循环 0.549 微秒 sorted(): $ python -mtimeit -s 'import random' -s 'i = (random.random() for x in xrange(1000))' 'sorted(i)' 1000000 次循环，3 次中的最佳值：每个循环 0.603 微秒 - dtheodor

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

- Anurag Uniyal

---

是的，你说得对。我确实知道[].sort()的就地排序，但不知怎么的一直在看这两者实现的算法有何区别（这点一直困扰着我）。看起来[].sort()在已经排序好的列表中表现得非常好。顺便说一句，出于很多原因[1]，我更喜欢使用timeit来展示示例代码片段，而不是time.time。使用timeit单独执行时结果是相同的。http://diveintopython.org/performance_tuning/timeit.html - Senthil Kumaran

Answer 3

.sort()方法会就地对列表进行排序，而sorted()则会创建一个新列表。因此，如果你有一个大列表，性能差异的一部分将归因于复制。

尽管如此，数量级差异似乎比我预期的要大。也许list.sort()具有sorted()无法利用的某些特定优化。例如，由于list类已经拥有内部大小正确的Py_Object*[]数组，因此它可以更有效地执行交换操作。

编辑：Alex和Anurag是对的，数量级差异是由于在测试用例中意外对已排序的列表进行了排序。但是，正如Alex的基准测试所显示的那样，list.sort()大约比sorted()快2％，这是由于复制开销造成的。

- Daniel Pryden

---

那是一个有用的指针。我刚开始挖掘并尝试理解原地排序和返回操作之间差异的原因。我已经在Alex的回复上发表了评论。谢谢。 - Senthil Kumaran