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

Сортировка списка кортежей (словарные ключи, пары значений, где ключ является случайной строкой) быстрее, если я не укажу явным образом, что ключ должен использоваться ( редактировать: добавлен оператор .itemgetter(0) от comment от @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

Как и ожидалось, построено в (сравнение адресов) быстрее.

EDIT: вот результаты профилирования моего исходного кода, вызвавшего вопрос - без ключевого метода:

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

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

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

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

Gist: https://gist.github.com/Utumno/f3d25e0fe4bd0f43ceb9178a60181a53

Ответ 1