Wie wird set () implementiert?

151

Ich habe Leute sagen sehen, dass setObjekte in Python eine O (1) -Mitgliedschaftsprüfung haben. Wie werden sie intern implementiert, um dies zu ermöglichen? Welche Art von Datenstruktur wird verwendet? Welche weiteren Auswirkungen hat diese Implementierung?

Jede Antwort hier war wirklich aufschlussreich, aber ich kann nur eine akzeptieren, also werde ich mit der nächsten Antwort auf meine ursprüngliche Frage fortfahren. Vielen Dank für die Info!

Daenyth
quelle

Antworten:

139

Nach diesem Thread :

In der Tat werden CPythons Sets als Wörterbücher mit Dummy-Werten implementiert (die Schlüssel sind die Mitglieder des Sets), wobei einige Optimierungen diesen Mangel an Werten ausnutzen

Grundsätzlich setverwendet a eine Hashtabelle als zugrunde liegende Datenstruktur. Dies erklärt die Überprüfung der O (1) -Mitgliedschaft, da das Nachschlagen eines Elements in einer Hashtabelle im Durchschnitt eine O (1) -Operation ist.

Wenn Sie so geneigt sind, können Sie sogar den CPython-Quellcode nach Set durchsuchen , das laut Achim Domma hauptsächlich aus der dictImplementierung ausgeschnitten und eingefügt wird .

Justin Ethier
quelle
18
IIRC, die ursprüngliche setImplementierung tatsächlich war dict mit Dummy - Werten, und es wurde später optimiert.
dan04
1
Ist groß O nicht der schlimmste Fall? Wenn Sie eine Instanz finden, in der die Zeit O (n) ist, dann ist es O (n). Ich verstehe im Moment nichts aus all diesen Tutorials.
Claudiu Creanga
4
Nein, der durchschnittliche Fall ist O (1), aber der schlechteste Fall ist O (N) für die Suche nach Hash-Tabellen.
Justin Ethier
4
@ClaudiuCreanga Dies ist ein alter Kommentar, aber nur zur Verdeutlichung: Die Big-O-Notation gibt Ihnen Obergrenzen für die Wachstumsrate der Dinge an, aber Sie können das Wachstum der durchschnittlichen Fallleistung nach oben und das Wachstum des Worst-Case separat nach oben begrenzen Performance.
Kirk Boyer
78

Wenn Leute sagen, dass Sets eine O (1) -Mitgliedschaftsprüfung haben, sprechen sie über den Durchschnittsfall . Im schlimmsten Fall (wenn alle Hash-Werte kollidieren) ist die Überprüfung der Mitgliedschaft O (n). Informationen zur zeitlichen Komplexität finden Sie im Python-Wiki .

Der Wikipedia-Artikel besagt, dass die beste Zeitkomplexität für eine Hash-Tabelle, deren Größe nicht geändert wird, ist O(1 + k/n). Dieses Ergebnis gilt nicht direkt für Python-Sets, da Python-Sets eine Hash-Tabelle verwenden, deren Größe geändert wird.

Ein wenig weiter im Wikipedia-Artikel heißt es, dass für den Durchschnittsfall und unter der Annahme einer einfachen einheitlichen Hashing-Funktion die zeitliche Komplexität dort ist O(1/(1-k/n)), wo k/nsie durch eine Konstante begrenzt werden kann c<1.

Big-O bezieht sich nur auf asymptotisches Verhalten als n → ∞. Da k / n durch eine Konstante begrenzt werden kann, ist c <1, unabhängig von n ,

O(1/(1-k/n))ist nicht größer als O(1/(1-c))das entspricht O(constant)= O(1).

Unter der Annahme eines einheitlichen einfachen Hashing ist die Überprüfung der Mitgliedschaft für Python-Sets im DurchschnittO(1) .

unutbu
quelle
14

Ich denke, es ist ein häufiger Fehler, setLookup (oder Hashtable für diese Angelegenheit) sind nicht O (1).
aus der Wikipedia

Im einfachsten Modell ist die Hash-Funktion vollständig nicht angegeben und die Größe der Tabelle wird nicht geändert. Für die bestmögliche Auswahl der Hash-Funktion weist eine Tabelle der Größe n mit offener Adressierung keine Kollisionen auf und enthält bis zu n Elemente mit einem einzigen Vergleich für eine erfolgreiche Suche. Eine Tabelle der Größe n mit Verkettung und k Schlüsseln hat das Minimum von max (0, kn) Kollisionen und O (1 + k / n) Vergleiche zur Suche. Für die schlechteste Wahl der Hash-Funktion verursacht jede Einfügung eine Kollision, und Hash-Tabellen degenerieren zur linearen Suche, wobei Ω (k) amortisierte Vergleiche pro Einfügung und bis zu k Vergleiche für eine erfolgreiche Suche vorliegen.

Verwandte: Ist eine Java-Hashmap wirklich O (1)?

Shay Erlichmen
quelle
4
Sie benötigen jedoch eine konstante Zeit, um nach Elementen zu suchen: python -m timeit -s "s = set (Bereich (10))" "5 in s" 10000000-Schleifen, am besten 3: 0,0642 usec pro Schleife <--> python - m timeit -s "s = set (Bereich (10000000))" "5 in s" 10000000 Schleifen, am besten 3: 0,0634 usec pro Schleife ... und das ist die größte Menge, die keine MemoryErrors auslöst
Jochen Ritzel
2
@ THC4k Alles, was Sie bewiesen haben, ist, dass das Nachschlagen von X in konstanter Zeit erfolgt, aber dies bedeutet nicht, dass die Zeit zum Nachschlagen von X + Y dieselbe Zeit in Anspruch nimmt, um die es bei O (1) geht.
Shay Erlichmen
3
@intuited: Das tut es, aber der obige Testlauf beweist nicht, dass Sie "5" nachschlagen können, während Sie "485398" oder eine andere Zahl nachschlagen können, die sich möglicherweise in einem schrecklichen Kollisionsraum befindet. Es geht nicht darum, dasselbe Element in einem Hash unterschiedlicher Größe zur gleichen Zeit nachzuschlagen (tatsächlich ist dies überhaupt nicht erforderlich), sondern darum, ob Sie in der aktuellen Tabelle in der gleichen Zeit auf jeden Eintrag zugreifen können - Dies ist für Hash-Tabellen grundsätzlich unmöglich, da es im Allgemeinen immer zu Kollisionen kommt.
Nick Bastin
3
Mit anderen Worten, die Zeit für eine Suche hängt von der Anzahl der gespeicherten Werte ab, da dies die Wahrscheinlichkeit von Kollisionen erhöht.
Intuitiert
3
@intuited: nein, das ist falsch. Wenn sich die Anzahl der gespeicherten Werte erhöht, erhöht Python automatisch die Größe der Hashtabelle und die Kollisionsrate bleibt ungefähr konstant. Unter der Annahme eines gleichmäßig verteilten O (1) -Hash-Algorithmus wird die Hashtabellensuche O (1) amortisiert . Vielleicht möchten Sie die Videopräsentation "The Mighty Dictionary" python.mirocommunity.org/video/1591/…
Lie Ryan
13

Wir haben alle einen einfachen Zugang zur Quelle , wo der vorhergehende Kommentar set_lookkey()lautet:

/* set object implementation
 Written and maintained by Raymond D. Hettinger <[email protected]>
 Derived from Lib/sets.py and Objects/dictobject.c.
 The basic lookup function used by all operations.
 This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
 The initial probe index is computed as hash mod the table size.
 Subsequent probe indices are computed as explained in Objects/dictobject.c.
 To improve cache locality, each probe inspects a series of consecutive
 nearby entries before moving on to probes elsewhere in memory.  This leaves
 us with a hybrid of linear probing and open addressing.  The linear probing
 reduces the cost of hash collisions because consecutive memory accesses
 tend to be much cheaper than scattered probes.  After LINEAR_PROBES steps,
 we then use open addressing with the upper bits from the hash value.  This
 helps break-up long chains of collisions.
 All arithmetic on hash should ignore overflow.
 Unlike the dictionary implementation, the lookkey function can return
 NULL if the rich comparison returns an error.
*/


...
#ifndef LINEAR_PROBES
#define LINEAR_PROBES 9
#endif

/* This must be >= 1 */
#define PERTURB_SHIFT 5

static setentry *
set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash)  
{
...
Gimel
quelle
2
Diese Antwort würde von der Hervorhebung der C- Syntax profitieren . Das Hervorheben der Python-Syntax des Kommentars sieht wirklich schlecht aus.
user202729
In Bezug auf den Kommentar "Dies führt zu einer Mischung aus linearer Prüfung und offener Adressierung" ist die lineare Prüfung nicht eine Art Kollisionsauflösung bei offener Adressierung, wie in en.wikipedia.org/wiki/Open_addressing beschrieben ? Daher ist die lineare Prüfung ein Subtyp der offenen Adressierung, und der Kommentar macht keinen Sinn.
Alan Evangelista
2

Um den Unterschied zwischen set'sund etwas stärker hervorzuheben dict's, hier ein Auszug aus den setobject.cKommentaren, in denen der Hauptunterschied zwischen Sätzen und Diktaten verdeutlicht wird.

Anwendungsfälle für Sets unterscheiden sich erheblich von Wörterbüchern, in denen nachgeschlagene Schlüssel mit größerer Wahrscheinlichkeit vorhanden sind. Im Gegensatz dazu geht es bei Sets hauptsächlich um Mitgliedschaftstests, bei denen das Vorhandensein eines Elements nicht im Voraus bekannt ist. Dementsprechend muss die Set-Implementierung sowohl für den gefundenen als auch für den nicht gefundenen Fall optimiert werden.

Quelle auf Github

user1767754
quelle