Wie hoch ist die zeitliche Komplexität der einzelnen Python-Set-Operationen in Big O- Notation?
Ich verwende Pythons Set-Typ für eine Operation für eine große Anzahl von Elementen. Ich möchte wissen, wie sich die Größe des Satzes auf die Leistung der einzelnen Vorgänge auswirkt. Fügen Sie beispielsweise hinzu und testen Sie die Mitgliedschaft:
myset = set()
myset.add('foo')
'foo' in myset
Durch das Googeln wurden keine Ressourcen gefunden, aber es erscheint vernünftig, dass die zeitliche Komplexität für die Set-Implementierung von Python sorgfältig abgewogen worden wäre.
Wenn es vorhanden ist , wird ein Link zu so etwas wie das wäre toll. Wenn da draußen nichts dergleichen ist, können wir es vielleicht herausfinden?
Zusätzliche Punkte zum Ermitteln der zeitlichen Komplexität aller festgelegten Operationen.
quelle
Antworten:
Laut Python-Wiki: Zeitkomplexität wird set als Hash-Tabelle implementiert . Sie können also erwarten, im O (1) -Durchschnitt nachzuschlagen / einzufügen / zu löschen . Wenn der Ladefaktor Ihrer Hash-Tabelle nicht zu hoch ist, treten Kollisionen und O (n) auf.
PS Aus irgendeinem Grund beanspruchen sie O (n) für einen Löschvorgang, der wie ein Fehlertyp aussieht.
PPS Dies gilt für CPython, Pypy ist eine andere Geschichte .
quelle
Der Vorgang
insollte unabhängig von der Größe des Behälters sein, d. H. O (1) - bei optimaler Hash-Funktion. Dies sollte für Python-Strings nahezu zutreffen. Das Hashing von Strings ist immer wichtig, Python sollte dort clever sein und daher können Sie nahezu optimale Ergebnisse erwarten.quelle
Die anderen Antworten sprechen nicht von zwei entscheidenden Operationen an Mengen: Gewerkschaften und Kreuzungen. Im schlimmsten Fall nimmt die Vereinigung O (n + m) an, während die Kreuzung O (min (x, y)) annimmt, vorausgesetzt, es gibt nicht viele Elemente in den Mengen mit demselben Hash. Eine Liste der zeitlichen Komplexitäten gängiger Operationen finden Sie hier: https://wiki.python.org/moin/TimeComplexity
quelle