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

Question

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

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

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

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

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

FINAL EDIT: Я задал этот последний пункт здесь: Why in comparing python tuples of objects is __eq__ and then __cmp__ called? - оказывается, это оптимизация, сравнение кортежа вызывает в элементах кортежа __eq__ и вызывать только для CMP не эк кортежей элементов. Так что теперь это совершенно ясно. Я думал, что это называется непосредственно __cmp__ так изначально мне казалось, что задание ключа просто не нужно, и после ответа Chepner, я все еще не получаю, где равные звонки приходят в

Gist:. 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 быстрее, независимо от сравниваемых значений.