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

Question

当我没有明确指定应该使用键时，对元组列表(字典键、值对，其中键是随机字符串)进行排序会更快(编辑:添加了 operator.itemgetter (0) 来自 @Chepner 的 comment，关键版本现在更快!):

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) 的速度更快。

编辑:这里是触发问题的我的原始代码的分析结果 - 没有 key 方法:

         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}

下面是我指定 key 时的结果:

         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 因为该类定义了 __cmp__ 但不是 __eq__，请参阅 here 以了解 equal 和 compare 的解析顺序)。

在此处的代码中，__eq__ 方法确实被调用了(8605 次)，如添加 debug prints 所见(参见 comments )。

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

最终编辑: 我在这里问了最后一点:Why in comparing python tuples of objects is __eq__ and then __cmp__ called? - 事实证明这是一个优化，元组的比较在元组元素中调用 __eq__ ，并且只调用 cmp 不eq 元组元素。所以现在很清楚了。我认为它直接调用了 __cmp__ 所以最初在我看来似乎不需要指定 key 并且在 Chepner 的回答之后我仍然没有得到 equal 调用的来源。

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

Answer 1

有两个问题在起作用。

1. 比较内置类型(例如 int)的两个值发生在 C 中。使用 __eq__ 方法比较类的两个值发生在 Python 中；重复调用 __eq__ 会造成严重的性能损失。

2. 通过 key 传递的函数对每个 元素 调用一次，而不是每次比较调用一次。这意味着 lambda x: x[0] 被调用一次以构建要比较的 A 实例列表。如果没有 key，您需要进行 O(n lg n) 次元组比较，每次比较都需要调用 A.__eq__ 来比较每个元组的第一个元素。

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