当我明确地将键作为第一个元素提供时,为什么要更快地排序元组的python列表？

当我没有明确指定应该使用密钥时,对元组列表(字典键,密钥是随机字符串的值对)进行排序更快(编辑:在@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

正如预期的那样(地址比较)更快.

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

         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 :1()
        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()
      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 :1()
        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()
      291    0.000    0.000    0.000    0.000 __init__.py:6533()
      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__方法而不是调用的方法(编辑因为类定义__cmp__但不是__eq__,请参阅此处查看等于和比较的分辨率顺序).

在这里的代码中,__eq__确实调用了方法(8605次),如添加调试打印所示(参见注释).

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

最后编辑:我在这里问最后一点:为什么在比较对象的python元组是__eq__然后调用__cmp__？- 事实证明它是一个优化,元组__eq__在元组元素中的比较调用,并且只调用cmp而不是eq元组元素.所以现在这一点非常清楚.我认为它是直接调用的,__cmp__所以最初在我看来,指定密钥是不必要的,在Chepner的回答之后,我仍然没有得到相同的呼叫进入的地方.

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

有两个问题在起作用.

比较内置类型的两个值(例如int)在C中进行比较.将一个类的两个值与一个__eq__方法进行比较在Python中进行; 反复呼叫会__eq__造成重大的性能损失.

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

第一个解释了为什么你的第一对结果不到一秒,而第二对结果需要几秒钟.第二个解释了key无论所比较的值如何,使用速度更快的原因.