Perché è più rapido ordinare un elenco python di tuple quando fornisco esplicitamente la chiave come primo elemento?

Question

L'ordinamento di una lista di tuple (chiavi del dizionario, coppie di valori in cui la chiave è una stringa casuale) è più veloce quando non si specifica esplicitamente che la chiave debba essere utilizzata (modifica: aggiunto operator.itemgetter (0) da comment da @Chepner e la versione chiave è ora più veloce):!

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

Dà:

0.575334150664 
0.579534521128 
0.523808984422 (the itemgetter version!) 

Se però ho creare un oggetto personalizzato passando il key=lambda x: x[0] esplicitamente sorted rende più veloce:

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

Dà:

4.65625458083 
1.87191002252 
1.78853626684 

È questo prevede? Sembra che il secondo elemento della tupla sia usato nel secondo caso, ma le chiavi non dovrebbero essere confrontate in modo ineguale?

Nota: decommentando il metodo di confronto dà risultati peggiori, ma ancora i tempi sono a metà:

8.11941771831 
5.29207000173 
5.25420037046 

come previsto costruito nel (address comparison) è più veloce.

EDIT: ecco i profilatura risultati dal mio codice originale che ha attivato la questione - senza il metodo chiave:

  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} 

ed ecco i risultati, quando ho specificare la chiave:

  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} 

Apparentemente è il __cmp__ e non è il metodo __eq__ che viene chiamato (modifica causa che la classe definisce __cmp__ ma non __eq__, vedere here per l'ordine di risoluzione di uguale e confronto).

Nel codice qui il metodo __eq__ viene effettivamente chiamato (8605 volte) come visto aggiungendo debug prints (vedere comments).

Quindi la differenza è come indicato nella risposta di @chepner. L'ultima cosa su cui non sono del tutto chiaro è perché le chiamate di uguaglianza tuple sono necessarie (IOW perché dobbiamo chiamare eq e non chiamiamo cmp direttamente).

montaggio finale: ho chiesto questo ultimo punto qui: Why in comparing python tuples of objects is __eq__ and then __cmp__ called? - scopre che è un'ottimizzazione, confronto di tuple chiama __eq__ negli elementi tuple, e chiamare solo CMP non per eq elementi tuple. Quindi questo è ora perfettamente chiaro. Ho pensato che chiama direttamente __cmp__ quindi inizialmente mi sembrava che specifica la chiave è solo non necessari e dopo la risposta di Chepner ero ancora non arrivare dove le chiamate uguali vengono in

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

Answer 1

Ci sono due problemi in gioco.

1. Confrontando due valori di tipi built-in (come int) avviene in C. Confrontando due valori di una classe con un metodo __eq__ accade in Python; ripetutamente chiamando __eq__ impone una penalità significativa delle prestazioni.

2. La funzione passata con key viene chiamata una volta per elemento, anziché una volta per confronto. Ciò significa che lambda x: x[0] viene chiamato una volta per creare un elenco di istanze A da confrontare. Senza key, è necessario effettuare confronti di tupla O (n lg n), ognuno dei quali richiede una chiamata a A.__eq__ per confrontare il primo elemento di ogni tupla.

Il primo spiega perché la prima coppia di risultati è inferiore a un secondo mentre la seconda impiega diversi secondi. Il secondo spiega perché l'utilizzo di key è più veloce indipendentemente dai valori confrontati.