Почему сортировка списка кортежей Python выполняется быстрее, если я явно указываю ключ в качестве первого элемента?

Сортировка списка кортежей (ключи словаря, пары значений, где ключ является случайной строкой) выполняется быстрее, если я явно не указываю, что следует использовать ключ (изменить: добавлен оператор.itemgetter (0) из комментарий @Chepner, и ключевая версия теперь работает быстрее!):

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 <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__ (изменить, потому что этот класс определяет __cmp__, но не __eq__, см. здесь для порядка разрешения равных и сравните).

В приведенном здесь коде метод __eq__ действительно вызывается (8605 раз), что видно по добавлению отладочных отпечатков ( см. комментарии).

Итак, разница указана в ответе @chepner. Последнее, что мне не совсем понятно, - это зачем эти вызовы равенства кортежей (IOW, почему нам нужно вызывать eq, а мы не вызываем cmp напрямую).

ОКОНЧАТЕЛЬНОЕ РЕДАКТИРОВАНИЕ: Я задал этот последний вопрос здесь: Почему при сравнении кортежей объектов python вызывается __eq__, а затем __cmp__ ? - оказывается, это оптимизация, сравнение кортежей вызывает __eq__ в элементах кортежа и вызывает cmp только для элементов кортежа, а не eq. Итак, теперь это совершенно ясно. Я думал, что он вызывает напрямую __cmp__, поэтому сначала мне показалось, что указывать ключ просто не нужно, и после ответа Чепнера я все еще не понимал, откуда приходят равные вызовы.

Смысл: https://gist.github.com/Utumno/f3d25e0fe4bd0f43ceb9178a60181a53