当我明确提供键作为第一个元素时，为什么对 python 元组列表进行排序会更快？

Question

当我没有明确指定应该使用键时，对元组列表（字典键、值对，其中键是随机字符串）进行排序会更快（编辑：由@Chepner 从添加了 operator.itemgetter(0) 并且密钥版本现在更快！）：

import timeit

setup ="""
import random
import string

random.seed('slartibartfast')
d={}
for i in range(1000):
    d[''.join(random.choice(string.ascii_uppercase) for _ in range(16))] = 0
"""
print min(timeit.Timer('for k,v in sorted(d.iteritems()): pass',
        setup=setup).repeat(7, 1000))
print min(timeit.Timer('for k,v in sorted(d.iteritems(),key=lambda x: x[0]): pass',
        setup=setup).repeat(7, 1000))
print min(timeit.Timer('for k,v in sorted(d.iteritems(),key=operator.itemgetter(0)): pass',
        setup=setup).repeat(7, 1000))

给出：

0.575334150664
0.579534521128
0.523808984422 (the itemgetter version!)

但是，如果我创建一个自定义对象，将 key=lambda x: x[0] 显式传递给 sorted 会使其更快：

setup ="""
import random
import string

random.seed('slartibartfast')
d={}

class A(object):
    def __init__(self):
        self.s = ''.join(random.choice(string.ascii_uppercase) for _ in
              range(16))
    def __hash__(self): return hash(self.s)
    def __eq__(self, other):
        return self.s == other.s
    def __ne__(self, other): return self.s != other.s
    # def __cmp__(self, other): return cmp(self.s ,other.s)

for i in range(1000):
    d[A()] = 0
"""
print min(timeit.Timer('for k,v in sorted(d.iteritems()): pass',
        setup=setup).repeat(3, 1000))
print min(timeit.Timer('for k,v in sorted(d.iteritems(),key=lambda x: x[0]): pass',
        setup=setup).repeat(3, 1000))
print min(timeit.Timer('for k,v in sorted(d.iteritems(),key=operator.itemgetter(0)): pass',
        setup=setup).repeat(3, 1000))

给出：

4.65625458083
1.87191002252
1.78853626684

这是预期的吗？似乎在第二种情况下使用了元组的第二个元素，但键不应该比较不相等吗？

注意：取消注释比较方法会得到更差的结果，但时间仍然是一半：

8.11941771831
5.29207000173
5.25420037046

正如预期的那样，内置 (address comparison) 速度更快。

编辑：这里是触发问题的我的原始代码的分析结果——没有关键方法：

         12739 function calls in 0.007 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.007    0.007 <string>:1(<module>)
        1    0.000    0.000    0.007    0.007 __init__.py:6527(_refreshOrder)
        1    0.002    0.002    0.006    0.006 {sorted}
     4050    0.003    0.000    0.004    0.000 bolt.py:1040(__cmp__) # here is the custom object
     4050    0.001    0.000    0.001    0.000 {cmp}
     4050    0.000    0.000    0.000    0.000 {isinstance}
        1    0.000    0.000    0.000    0.000 {method 'sort' of 'list' objects}
      291    0.000    0.000    0.000    0.000 __init__.py:6537(<lambda>)
      291    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 bolt.py:1240(iteritems)
        1    0.000    0.000    0.000    0.000 {method 'iteritems' of 'dict' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

这是我指定密钥时的结果：

         7027 function calls in 0.004 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.004    0.004 <string>:1(<module>)
        1    0.000    0.000    0.004    0.004 __init__.py:6527(_refreshOrder)
        1    0.001    0.001    0.003    0.003 {sorted}
     2049    0.001    0.000    0.002    0.000 bolt.py:1040(__cmp__)
     2049    0.000    0.000    0.000    0.000 {cmp}
     2049    0.000    0.000    0.000    0.000 {isinstance}
        1    0.000    0.000    0.000    0.000 {method 'sort' of 'list' objects}
      291    0.000    0.000    0.000    0.000 __init__.py:6538(<lambda>)
      291    0.000    0.000    0.000    0.000 __init__.py:6533(<lambda>)
      291    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 bolt.py:1240(iteritems)
        1    0.000    0.000    0.000    0.000 {method 'iteritems' of 'dict' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

显然调用的是 __cmp__ 而不是 __eq__ 方法（edit 因为 class 定义了 __cmp__ 但不是 __eq__，请参阅 here 以了解相等和比较的解析顺序）。

在此处的代码中 __eq__ 方法确实被调用（8605 次），如添加 debug prints (see the comments) 所示。

所以区别如@chepner 的回答所述。我不太清楚的最后一件事是 为什么 需要那些元组相等调用（IOW 为什么我们需要调用 eq 而我们不直接调用 cmp）。

最终编辑： 我在这里问了最后一点： - 原来这是一个优化，元组元素中的元组比较调用 __eq__，并且只为非 eq 元组元素调用 cmp。所以现在很清楚了。我认为它直接调用 __cmp__ 所以最初在我看来似乎不需要指定密钥并且在 Chepner 的回答之后我仍然没有得到平等调用的地方。

要点：https://gist.github.com/Utumno/f3d25e0fe4bd0f43ceb9178a60181a53

Answer 1

有两个问题在起作用。

比较内置类型的两个值（例如 int）发生在 C 中。比较 class 和 __eq__ 方法的两个值发生在 Python;重复调用 __eq__ 会严重影响性能。
通过 key 传递的函数每个元素调用一次，而不是每次比较调用一次。这意味着 lambda x: x[0] 被调用一次以构建要比较的 A 个实例的列表。如果没有key，则需要进行O(n lg n)次元组比较，每次比较都需要调用A.__eq__来比较每个元组的第一个元素。

第一个解释了为什么您的第一对结果不到一秒钟，而第二对需要几秒钟。第二个解释了为什么使用 key 更快，而不管比较的值如何。

当我明确提供键作为第一个元素时，为什么对 python 元组列表进行排序会更快？

Why is sorting a python list of tuples faster when I explicitly provide the key as the first element?

python

sorting

tuples

timeit

python-2.7