Angenommen, ich habe ein Wörterbuch
%Vor% Gibt es eine Datenstruktur, so dass, wenn ich das Schlüssel-Wert-Paar 3:5 hinzufüge, es so in das Wörterbuch eingegeben werden muss, dass die Schlüssel in sortierter Reihenfolge sind? d. h.
Ich bin mir der collections.OrderedDict() bewusst, aber das hält die Schlüssel nur in der Reihenfolge, in der sie hinzugefügt wurden (was für mich zur Zeit nicht ausreicht).
Ich möchte nicht ein normales Wörterbuch dic = {} verwenden müssen, dann muss sorted(dic)[0] den kleinsten Schlüssel verwenden. Ich hätte lieber sorted_dict[0] type function.
Der Grund dafür ist, dass ich, wenn ich ein normales Wörterbuch verwende, die Sortierung mehrmals aufrufen muss, da ich fortlaufend Paare zu meinem Wörterbuch hinzufüge.
EDIT: Ich hätte erwähnen sollen, es ist nicht nur die kleinste und größte Taste, die mir wichtig ist, ich muss dieses Wörterbuch auch in regelmäßigen Abständen drucken ...
Wenn Sie beabsichtigen, Schlüssel kontinuierlich aus dem Wörterbuch hinzuzufügen und zu entfernen, möchten Sie wirklich etwas, das eine geeignete Datenstruktur für das Problem verwendet - nicht eine Hash-Tabelle (oder eine Hash-Tabelle plus eine Liste wie bei SortedOrderedDict ). Typ Rezepte), aber ein ausgewogener Baum (oder ein Äquivalent, wie eine Skip-Liste).
Wenn Sie sich PyPI ansehen, finden Sie eine Reihe von Optionen. Meine Empfehlung wäre blist . Obwohl seine Datenstruktur nicht ganz so optimal ist wie einige der anderen (weil ein B + Tree viel breiter ist als ein Binärbaum), ist es wahrscheinlich gut genug für fast jeden Anwendungsfall, in den Sie hineingeraten werden. Und es hat eine vollständige und gut getestete Schnittstelle, einschließlich gut getesteter Leistungsgarantien. Und es wird von anderen ernsthaften Projekten verwendet.
Wenn Sie sich mit einem der seltenen Fälle befassen, in denen die Baumperformance wirklich kritisch ist, sollten Sie sich die verschiedenen Rot-Schwarz-Baum-, Splay-Tree-, Skilllisten-, usw. Implementierungen ansehen. Ich habe bintrees zuvor verwendet, was eine großartige Oberfläche hat (zB können Sie auf die Schlüssel zugreifen) und Werte nach Index, und sogar schneiden Sie den Baum, sowie die Behandlung wie ein dict , und der Autor hat gedacht und vermieden alle möglichen Unklarheiten), aber ich habe nicht ernsthaft Leistung getestet es.
Oder, wenn Ihre Schlüssel und Werte wirklich alle kleinen ganzen Zahlen sind, sollten Sie in Betracht ziehen, Cython zu verwenden, um ein C ++ map<int, int> in einer Pythonic-Schnittstelle einzubinden. (Es ist nicht ganz möglich, eine vollständige -Schnittstelle über C ++ map bereitzustellen, aber Sie benötigen diese sowieso nicht.) Alternativ können Sie auch eine der Implementierungen wie bintrees.FastRBTree to ändern Speichern und vergleichen Sie long anstelle von PyObject* .
Wenn Sie andererseits das Wörterbuch auf einmal erstellen und dann verwenden, gibt es eine viel einfachere Antwort. Sortieren Sie es und fügen Sie es in OrderedDict ein. Dann brauchst du nichts außerhalb der stdlib.
Aus einem Kommentar zu einer anderen Antwort sagen Sie: "Ich habe keine Berechtigung, neue Module zu installieren ..."
Stellen Sie zuerst sicher, dass das wirklich stimmt. Sie haben wahrscheinlich tun die Berechtigung, Module in einem Benutzer-Site-Packages-Verzeichnis zu installieren. Oder, wenn virtualenv installiert ist und / oder Sie verwenden 3.3 mit eingebautem venv , noch besser, haben Sie wahrscheinlich die Berechtigung, ein venv zu erstellen und Module darin zu installieren.
Wenn ja, kopieren Sie die Dateien von blist / bintrees / was auch immer in Ihr Projekt.
Das Problem, auf das Sie stoßen könnten, ist, dass die meisten dieser Pakete C-Erweiterungsmodule enthalten, was bedeutet, dass Sie in der Lage sein müssen, sie zu erstellen (naja, build_ext -i sie). Wenn auf Ihrem System die Python-Dev-Dateien und eine Compiler-Tool-Kette nicht installiert sind, können Sie das nicht tun. In diesem Fall suchen Sie nach der besten reinen Python-Lösung. bintrees kommt mit einer reinen Python-Implementierung, die mit der normalen C-Erweiterung-Implementierung identisch ist, außer langsamer. Es ist natürlich immer noch O (log N), nur der konstante Faktor ist viel höher. Wenn N groß genug ist, ist es immer noch ein großer Gewinn; wenn nicht, kann es nicht sein.
Wenn ein Teil davon vernünftig klingt, Sie aber Hilfe benötigen, um ein benutzerdefiniertes Site-Package oder virtuelles env einzurichten oder ein Modul direkt in Ihr Projekt zu kopieren oder Erweiterungen direkt zu erstellen, usw. sollte wahrscheinlich nach vorhandenen Fragen suchen und eine neue Frage stellen, wenn Sie keine finden können (nur deshalb, weil die Leute, die Experten für Installationsprobleme sind, nicht unbedingt Experten für Datenstrukturen sind und vielleicht gar nicht Lesen Sie diese Frage).
Probieren Sie dieses Rezept - Ссылка
ausDie Schlüssel werden mit dem Halbierung -Modul sortiert.
Mehr als ein Jahr zu spät zur Party, aber ich wollte das Modul sortedcontainers vorschlagen. Wie blist und bintrees bietet es einen SortedDict -Datentyp, der die Schlüssel in sortierter Reihenfolge verwaltet. Anders als diese Module ist es in pure-Python geschrieben und ist tatsächlich schneller. SortedDict unterstützt auch die Indizierung. Nach oben schaut das Min / Max tatsächlich in O (1) Zeit.
Da es pure-Python ist, sollte die Installation mit pip ein Kinderspiel sein:
%Vor%Dann können Sie einfach das SortedDict
importieren %Vor%Wenn Sie Probleme haben, Dinge mit pip zu installieren oder Dateien, die kompiliert werden müssen, nicht kopieren können, ziehen Sie einfach die Dateien sortedlist.py und sorteddict.py aus dem Depot. Der gesamte Code ist open source auf github .
Das sortedcontainers-Modul bietet auch einen Leistungsvergleich mit den beliebtesten Vorschlägen, die miteinander verglichen werden.
Tags und Links python dictionary key sorted