Dlaczego sortowanie listy k pytonów krotek jest szybsze, gdy jawnie podaję klucz jako pierwszy element?

Question

Sortowanie listy krotek (klawisze słownika, pary wartości, w których klucz jest losowym ciągiem znaków) jest szybsze, gdy nie określam jawnie, że klucz powinien zostać użyty (edycja: dodano operator.itemgetter (0) z comment przez @Chepner i klucz wersja jest teraz szybsze):

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)) 

daje:

0.575334150664 
0.579534521128 
0.523808984422 (the itemgetter version!) 

Jeśli jednak utworzyć niestandardowy obiekt przechodzący key=lambda x: x[0] wyraźnie do sorted czyni go szybciej:

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)) 

Daje:

4.65625458083 
1.87191002252 
1.78853626684 

Czy to prawidłowo? Wydaje się, że drugi element krotki jest używany w drugim przypadku, ale czy klucze nie powinny się równać?

Uwaga: odkomentowanie metodę porównawczą daje gorsze wyniki, ale nadal czasy są w jednej połowie:

8.11941771831 
5.29207000173 
5.25420037046 

jak oczekiwano wybudowany w (address comparison) jest szybsze.

EDIT: oto profilowania wynika z mojego oryginalnego kodu, który wywołał pytanie - bez klucza metody:

  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} 

i oto wyniki, kiedy określenie klucza:

  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} 

Podobno jest to metoda __cmp__, a nie __eq__, która jest nazywana (edycja, ponieważ ta klasa definiuje __cmp__, ale nie __eq__, patrz: here dla celu rozdzielenia równości i porównania).

W kodzie tutaj metoda jest rzeczywiście wywoływana (8605 razy), jak widać przez dodanie debug prints (patrz comments).

Różnica jest taka, jak podano w odpowiedzi @chepner. Ostatnią rzeczą, której nie jestem do końca jasny, jest: , dlaczego są tymi wymaganymi krotnościami równości (IOW, dlaczego musimy wywołać eq i nie nazywamy bezpośrednio cmp).

FINAL EDIT: Poprosiłem ten ostatni punkt tutaj: Why in comparing python tuples of objects is __eq__ and then __cmp__ called? - okazuje się, że jest to optymalizacja, porównanie krotki za nazywa __eq__ w elementach krotka i tylko zadzwonić CMP za nie eq elementów krotki. Jest to teraz zupełnie jasne. Myślałem, że to nazywa się bezpośrednio __cmp__ więc początkowo wydawało mi się, że podając klucz jest po prostu niepotrzebne i po odpowiedzi Chepner za ja wciąż nie gdzie równe połączenia przyjść

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

Answer 1

Istnieją dwa problemy w grze.

1. Porównując dwie wartości wbudowanych rodzaju (takie jak int) stanie w C. Porównując dwie wartości klasy z metodą __eq__ dzieje się Pythonie wielokrotne wywoływanie __eq__ narzuca znaczącą karę wykonania.

2. Funkcja przekazywana z key jest wywoływana raz dla każdego elementu element, a nie raz dla porównania. Oznacza to, że lambda x: x[0] jest wywoływany raz, aby utworzyć listę instancji A do porównania. Bez wartości key należy wykonać porównanie krotek O (n lg n), z których każde wymaga wywołania do A.__eq__ w celu porównania pierwszego elementu każdej krotki.

Pierwszy wyjaśnia, dlaczego twoja pierwsza para wyników ma mniej niż sekundę, a druga zajmuje kilka sekund. Drugi wyjaśnia, dlaczego używanie key jest szybsze, niezależnie od porównywanych wartości.