Ich baue ein sehr großes Wörterbuch und führe viele Überprüfungen durch, um zu sehen, ob ein Schlüssel in der Struktur ist und dann, wenn er einzigartig ist, oder um einen Zähler zu erhöhen, wenn er identisch ist.
Python verwendet eine Hash-Datenstruktur , um Wörterbücher zu speichern (nicht zu verwechseln mit einer kryptographischen Hash-Funktion). Lookups sind O (1), aber wenn die Hash-Tabelle voll ist, muss sie aufgeräumt werden, was sehr teuer ist.
Meine Frage ist, wäre es besser, einen AVL-Baum für die binäre Suche zu verwenden oder ist eine Hashtabelle gut genug?
Der einzige Weg, um sicher zu sein, wäre, beides zu implementieren und zu überprüfen, aber meine informierte Vermutung ist, dass das Wörterbuch schneller sein wird, weil ein binärer Suchbaum O (log (n)) zum Suchen und Einfügen und I gekostet hat denke, dass außer in den pessimalsten Situationen (wie massiven Hash-Kollisionen) die O (1) -Lookup-Tabelle der Hash-Tabelle die gelegentliche Größenänderung überwiegen wird.
Wenn Sie sich die Python-Wörterbuchimplementierung ansehen, Du wirst das sehen:
PyDict_MINSIZE ); (Die " HINWEISE ZUR OPTIMIERUNG VON WÖRTERBÜCHERN " sind lesenswert auch.)
Wenn also Ihr Wörterbuch 1.000.000 Einträge hat, glaube ich, dass es elfmal skaliert wird (8 → 32 → 128 → 512 → 2048 → 8192 → 32768 → 131072 → 262144 → 524288 → 1048576 → 2097152) zu einem Preis von 2.009.768 zusätzliche Einfügungen während der Größenänderung Dies scheint wahrscheinlich viel weniger als die Kosten für das Rebalancing bei 1.000.000 Einfügungen in einen AVL-Baum zu sein.
Wie groß ist das Verhältnis von Gegenständen zu Einzelstücken? Wie hoch ist die erwartete Anzahl eindeutiger Artikel?
Wenn ein Hash-Bucket gefüllt wird, dann sollte die Erweiterung nur eine Angelegenheit der Neuzuordnung von Speicher sein, nicht erneutes Aufladen.
Das Testen eines Zähldiktes sollte sehr schnell und einfach sein.
Beachten Sie auch die seit python 2.7 verfügbare Counter-Klasse Ссылка http://svn.python.org/view?view=rev&revision=68559
Python-Wörterbücher sind stark optimiert. Python führt verschiedene Spezialfalloptimierungen durch, die von den Python-Entwicklern in der CPython-Wörterbuchimplementierung berücksichtigt werden.
Das Buch " Beautiful Code " diskutiert das alles.
Das achtzehnte Kapitel ist Python's Dictionary Implementation: Alle Dinge für alle Menschen von Adrew Kuchling
Es ist viel besser, es zu verwenden, als zu versuchen, die handgefertigte benutzerdefinierte Implementierung zu erreichen, die all diese Optimierungen replizieren muss, um in der Nähe der CPython-Hauptimplementierung von Dictionary-Lookups zu sein.
Sie müssten Ihre eigenen Datenstrukturen in C implementieren, um eine vernünftige Chance zu haben, die eingebauten Strukturen zu übertreffen.
Sie können auch einen Teil des Overheads vermeiden, indem Sie get verwenden und vermeiden, vorhandene Elemente zweimal zu finden.
Oder collections.Counter, wenn Sie Python 2.7 + verwenden.
Die Verwendung eines Diktats ist O (1). Wenn das Diktat wächst, ist manchmal eine Neuzuweisung erforderlich, aber das amortisiert sich O (1)
Wenn Ihr anderer Algorithmus O (log n), die einfache dict wird immer es schlagen, wie der Datensatz größer wird.
Wenn Sie irgendeine Art von Baum verwenden, würde ich irgendwo dort eine O (log n) -Komponente erwarten.
Eine Hashtabelle ist nicht nur gut genug, sie ist besser
Tags und Links python algorithm performance data-structures