Wie kommt Schlüssel in dictionary.keys() langsamer als Schlüssel im Wörterbuch?

Question

Beim Lesen Python 101 von Michael Driscoll Ich habe zu seiner Erklärung auf der Überprüfung, ob ein Schlüssel in einem Wörterbuch vorhanden ist. Ich habe es auf meinem Rechner mit einem Wörterbuchschlüssel 'a'-'z' enthalten, wobei der Wert ihrer Ordnung ist, und eine Funktion, die Zeit auf das Abrufen der Schlüssel 't' (nahm sie zufällig)

Hier ist meine Funktion misst:

def f(d, flag): 
start_time = time.time() 
if flag: 
    print("t" in d) 
else: 
    print("t" in d.keys()) 
print("--- %s seconds ---" % (time.time() - start_time)) 

Und hier sind die Ergebnisse:

>>> f(dict,True) 
True 
--- 0.03937530517578125 seconds --- 

>>> f(dict,False) 
True 
--- 0.05114388465881348 seconds --- 

ABER, ich kann es immer noch nicht bekommen. Ich dachte, dass key in dict.keys() Iteration auf viel kleinere Sammlung ergeben würde, die schneller sein wird. Gibt es etwas Besonderes in der Implementierung von in oder keys(), die dies verursacht?

Answer 1

dictionary.keys() Mit langsamer, weil es tut mehr Arbeit:

• Es fügt ein Attribut Lookup; dictionary.keys
• Er fügt einen Methodenaufruf (keys()) hinzu, der erfordert, dass der aktuelle Aufrufrahmen auf den Stapel geschoben und anschließend wieder aufgerufen wird.
• Für den Rückgabewert (eine Dictionary-View) muss ein weiteres Objekt erstellt werden. Es ist ein leichtes Objekt, aber Sie müssen immer noch Speicher für den Heap reservieren.

All dies ist erforderlich, weil ein Containment-Test gegen das Wörterbuch und der Wörterbuch Blick auf die Taste Test genau die gleichen. Containment-Test direkt in einem Wörterbuch enthält nicht die Werte, die Sie für die Schlüssel nur testen, in beiden Fällen.

Vom dict() object documentation:

key in d
Return True wenn d einen Schlüssel Schlüssel hat, sonst False.

Beachten Sie, dass die Verwendung von Walk-Clock-Zeit keine gute Möglichkeit ist, Leistungsunterschiede zu testen. Verwenden Sie stattdessen die timeit module, die den leistungsstärksten Timer auswählt, deaktiviert den GC, um eine Quelle von Skew zu beseitigen, und wiederholt den Test mehrmals, um den System-Skew zu minimieren.

Sie können den Zeitunterschied reproduzieren, indem Sie die oben genannten zusätzlichen Schritte separat testen (indem Sie die Erstellung von Aufrufen und Objekten zu einem kombinieren). Standardmäßig timeit.timet() die Test 1 Million mal wiederholt und gibt die Gesamtzeit:

>>> import timeit 
>>> from string import ascii_lowercase 
>>> d = {l: i for i, l in enumerate(ascii_lowercase)} 
>>> 't' in d 
True 
>>> timeit.timeit('d.keys', globals={'d': d}) 
0.0439452639548108 
>>> timeit.timeit('keys()', globals={'keys': d.keys}) 
0.06267352704890072 

So lediglich Nachschlagen der .keys Attribut 1 Million mal dauert bereits 44 Millisekunden, während die Methode aufrufen (ohne Attribut-Lookup) steuert weitere 63ms .Beiden Methoden haben einige Overhead auf der Suche nach dem globalen Namen jedoch nach oben:

>>> timeit.timeit('d', globals={'d': d}) 
0.027833244064822793 

So würde man es erwartet ein 107 zu sein - 28 == 79ms (grob) Unterschied zwischen den beiden Methoden.

Und in der Tat, die Zeitdifferenz zwischen 't' in d und 't' in d.keys() verwendet, ist ungefähr so ​​viel:

>>> timeit.timeit('"t" in d.keys()', globals={'d': d}) 
0.11647015693597496 
>>> timeit.timeit('"t" in d', globals={'d': d}) 
0.0370339349610731 

116 - 37 79 Millisekunden ist, wie vorhergesagt.