Python-Wörterbuchschlüssel. "In" Komplexität

Question

Schnelle Frage hauptsächlich meine Neugier auf das Thema zu befriedigen.

Ich schreibe einige große Python-Programme mit einem SQlite-Datenbank-Backend und werde in Zukunft mit einer großen Anzahl von Datensätzen umgehen, also muss ich so viel wie möglich optimieren.

Für ein paar Funktionen, suche ich Schlüssel in einem Wörterbuch. Ich habe das "in" -Schlüsselwort für das Prototyping verwendet und wollte später diese Suchvorgänge optimieren, da ich weiß, dass das "in" -Schlüsselwort im Allgemeinen O (n) ist (dies bedeutet nur, dass Python über eine ganze Liste iteriert und vergleicht jedes Element). Aber, wie ein Python dict im Grunde nur eine Hash-Karte ist die Python-Interpreter intelligent genug, um zu interpretieren:

if(key in dict.keys()): 
    ...code... 

zu:

if(dict[key] != None): 
    ...code... 

Es ist im Grunde die gleiche Operation, aber die Spitze wäre O (n) und der Boden wäre O (1).

Es ist einfach für mich, die untere Version in meinem Code zu verwenden, aber dann war ich nur neugierig und dachte, ich würde fragen.

Answer 1

Zuerst wird key in d.keys() Ihnen garantiert den gleichen Wert wie key in d für jedes dict d geben.

Und der in Betrieb auf einem dict oder dict_keys Objekt, das Sie von Aufrufen keys() auf sie zurück (in 3.x) ist nicht O (N), ist es O (1).

Es gibt keine wirkliche "Optimierung"; Es ist nur so, dass die Verwendung des Hashs die naheliegende Methode ist, in einer Hash-Tabelle zu implementieren, genauso wie es der offensichtliche Weg ist, __getitem__ zu implementieren.

---

Sie können fragen, wo das garantiert ist.

Nun, ist es nicht. Mapping Types definiert dict als im Grunde eine Hash-Tabelle Implementierung von collections.abc.Mapping. Es gibt nichts, was jemanden davon abhält, eine Hashtabellenimplementierung eines Mappings zu erstellen, aber dennoch O (N) -Suchen durchzuführen. Aber es wäre zusätzliche Arbeit, um solch eine schlechte Implementierung zu machen, also warum sollten sie?

Wenn Sie wirklich es sich selbst beweisen müssen, Sie jede Implementierung kümmern uns um Sie testen (mit einem Profiler oder durch irgendeine Art mit einem benutzerdefinierten __hash__ und __eq__ verwenden, Anrufe oder ... anmeldet), oder lesen Sie die Quelle .

---

In 2.x, mögen Sie nicht keys nennen, denn das ist ein list des Schlüssels erzeugt, anstelle ein KeysView. Sie könnten iterkeys verwenden, aber das könnte einen Iterator oder etwas anderes erzeugen, das nicht O (1) ist. Verwenden Sie also das Diktat selbst als Sequenz.

Auch in 3.x möchten Sie nicht keys anrufen, weil es nicht nötig ist. Iterating ein dict, überprüft seine , und im Allgemeinen zu behandeln, wie eine Sequenz ist immer gleichbedeutend mit der gleichen Sache zu seinen Schlüsseln, also warum stören?(Und natürlich bauen die trivialen KeyView, und den Zugriff darauf, fügen Sie ein paar Nanosekunden zu Ihrer Laufzeit und ein paar Tastenanschläge für Ihr Programm.)

(Es ist nicht ganz klar, dass die Verwendung von Sequenz-Operationen für/und d in 2.x. Abgesehen von Leistungsproblemen sind sie sind gleichbedeutend in jeder CPython, Jython, IronPython und PyPy-Implementierung, aber es scheint nicht irgendwo angegeben, wie es in 3.x ist . Und es spielt keine Rolle, nur key in d verwenden)

---

Während wir sind. Beachten Sie, dass dies:

if(dict[key] != None): 

... wird nicht funktionieren. Wenn die key nicht in der dict ist, erhöht dies KeyError, nicht zurück None.

Sie sollten auch nie None mit == oder != überprüfen; Verwenden Sie immer is.

Sie können dies mit einem try -oder einfacher tun tun if dict.get(key, None) is not None tun. Aber auch dafür gibt es keinen Grund. Das wird auch keine Fälle behandeln, in denen None ein vollkommen gültiger Gegenstand ist. Wenn das der Fall ist, müssen Sie etwas wie sentinel = object(); if dict.get(key, sentinel) is not sentinel: tun.

---

Also, das Richtige zu schreiben:

if key in d: 

---

Allgemeiner dies nicht wahr ist:

I know the "in" keyword is generally O(n) (as this just translates to python iterating over an entire list and comparing each element

Der in Betreiber, wie die meisten anderen Betreiber, ist nur ein Aufruf an eine -Methode (oder das Äquivalent für eine C/Java/.NET/RPython-Built-in). list implementiert es durch Iterieren der Liste und Vergleichen jedes Elements; dict implementiert es durch Hashing den Wert und Nachschlagen des Hash; blist.blist implementiert es durch einen B + Baum zu Fuß; usw. Es könnte also O (n), O (1), O (log n) oder etwas völlig anderes sein.

Answer 2

In Python 2 dict.keys() erstellt die ganze Liste der Schlüssel zuerst, deshalb ist es ein O(N) Betrieb, während key in dict ist ein O(1) Betrieb.

if(dict[key] != None) wird KeyError auslösen, wenn Schlüssel nicht im Diktat gefunden wird, so ist es nicht gleichbedeutend mit dem ersten Code.

Python 2 Ergebnisse:

>>> dic = dict.fromkeys(range(10**5)) 
>>> %timeit 10000 in dic 
1000000 loops, best of 3: 170 ns per loop 
>>> %timeit 10000 in dic.keys() 
100 loops, best of 3: 4.98 ms per loop 
>>> %timeit 10000 in dic.iterkeys() 
1000 loops, best of 3: 402 us per loop 
>>> %timeit 10000 in dic.viewkeys() 
1000000 loops, best of 3: 457 ns per loop 

In Python 3 dict.keys() gibt eine Ansicht Objekt, das als 2 Python ziemlich schneller ist keys() aber immer noch langsamer einfache normale key in dict:

Python 3 Ergebnisse:

>>> dic = dict.fromkeys(range(10**5)) 
>>> %timeit 10000 in dic 
1000000 loops, best of 3: 295 ns per loop 
>>> %timeit 10000 in dic.keys() 
1000000 loops, best of 3: 475 ns per loop 

Nur verwenden:

if key in dict: 
    #code 

Answer 3

Der richtige Weg, dies zu tun, würde

if key in dict: 
    do stuff 

die in Operator ist O (1) für die Wörterbücher und Sätze in Python sein.

Answer 4

Der In-Operator für dict hat die durchschnittliche Komplexität von O (1). Ausführliche Informationen zur Zeitkomplexität anderer dict() -Methoden finden Sie unter link.