为什么Python的“sorted()”比“复制，然后.sort()”慢？

Question

这是我运行的代码：

import timeit

print timeit.Timer('''a = sorted(x)''', '''x = [(2, 'bla'), (4, 'boo'), (3, 4), (1, 2) , (0, 1), (4, 3), (2, 1) , (0, 0)]''').timeit(number = 1000)
print timeit.Timer('''a=x[:];a.sort()''', '''x = [(2, 'bla'), (4, 'boo'), (3, 4), (1, 2) , (0, 1), (4, 3), (2, 1) , (0, 0)]''').timeit(number = 1000)

以下是结果:

0.00259663215837
0.00207390190177

我想了解为什么使用.sort()比sorted()快，即使两者都复制列表？

注意：我正在运行Python 2.7在一个2.53Ghz的i5上，带有Win7。

- TimY

---

建议您多次尝试使用更大的列表进行严格测试。 - Andrew Gorcester

@AndrewGorcester 我同意你的建议，购买更大的列表，但为什么要多次购买呢？1000个不足以获得合理的统计准确性吗？ - robert

抱歉，我之前不熟悉timeit模块，刚刚才意识到它被重复执行了1000次，就在你回复的同时。这应该足够多的重复次数了。 - Andrew Gorcester

Answer 1

你正在关注的差异微小，对于更长的列表完全消失了。只需将x的定义添加* 1000，在我的机器上得到以下结果：

2.74775004387
2.7489669323

我猜测你感觉sorted()速度稍慢的原因是：sorted()需要使用一些通用代码将任何可迭代对象复制到列表中，而直接复制列表可以假设源也是一个列表。CPython使用的排序代码实际上对list.sort()和sorted()都是相同的，所以不会导致差异。 编辑:当前开发版本的sorted()的源代码进行了道德等效的操作。

a = list(x)
a.sort()

实际上，使用这段代码而不是您的第二个版本，对于任何列表大小都能消除任何显著的速度差异。

- Sven Marnach

---

在我的机器上运行的结果支持你的答案。 - jfs

是的 - list.sort 可以处理已知大小的列表，并在该大小内交换元素，而 sorted() 则必须处理未知大小和通用可迭代对象，因此可能需要在构建过程中分配内存（如果不连续则可能强制执行 memcpy），但这应该是最小化的，正如您所述。复制一个列表非常简单，因为这只是一个简单的 malloc/memcpy 操作（以及创建新 PyObject*）。 - Jon Clements

Answer 2

支持@Sven Marnach的回答：

对于小列表，有一个小差异：

$ python2.7 -mtimeit -s "x = [(2, 'bla'), (4, 'boo'), (3, 4), (1, 2) , (0, 1), (4, 3), (2, 1) , (0, 0)]; s=sorted" "a=s(x)"
1000000 loops, best of 3: 1.87 usec per loop

$ python2.7 -mtimeit -s "x = [(2, 'bla'), (4, 'boo'), (3, 4), (1, 2) , (0, 1), (4, 3), (2, 1) , (0, 0)]" "a=x[:];a.sort()"
1000000 loops, best of 3: 1.66 usec per loop

当列表较大时，差异会消失 * 1000：

$ python2.7 -mtimeit -s "x = [(2, 'bla'), (4, 'boo'), (3, 4), (1, 2) , (0, 1), (4, 3), (2, 1) , (0, 0)]*1000; s=sorted" "a=s(x)"
100 loops, best of 3: 3.42 msec per loop

$ python2.7 -mtimeit -s "x = [(2, 'bla'), (4, 'boo'), (3, 4), (1, 2) , (0, 1), (4, 3), (2, 1) , (0, 0)]*1000" "a=x[:];a.sort()"
100 loops, best of 3: 3.48 msec per loop

- jfs