Da OrderedDict die Reihenfolge der Einfügung eines Artikels beibehalten muss, frage ich mich, was ist die Leistung von get/set/popitem in Python 2.7? Habe bisher keine offiziellen Dokumente gefunden. Ich schätze get ist O(1), set ist O(logN) und popitem ist O(1).set, get und popitem Leistung von OrderedDict
Hier ist die documentation.
Ich habe gerade die Implementation of python Orderedlist object from Python mercurial repository überprüft. In den Kommentaren von odictobject.c Datei haben sie angegeben: One invariant of Python's OrderedDict is that it preserves time complexity of dict's methods, particularly the O(1) operations.
Danke Kun, wähle für deine Antwort. Ich habe den Code-Repo für die Logik ihrer Implementierung gelesen und ein wenig verwirrt wegen ihrer Logik der "popitem" -Implementierung. Ich frage mich, wie es mit 'O (1)' umgesetzt wird? Normalerweise sollte es einen Haufen oder eine andere ähnliche Datenstruktur geben, um die Einfügereihenfolge beizubehalten, so dass der Pop vom letzten oder vom ersten, immer das richtige Element finden kann? –
(Forts.) Von der Code-Implementierung sehe ich nicht, dass sie Heap oder andere Datenstrukturen verwenden, also denke ich, dass Sie richtig sind, sie verwenden 'O (1)' Implementierung, und wenn Sie ein bisschen mehr klären könnten Sie erreichen die Performance mit 'O (1)', es wird großartig. :) –
Hallo Kun, wenn du mir bei meiner obigen Frage raten könntest, wird es klasse sein. Vielen Dank. –
@Kun, danke und stimmen auf. Ich habe einige Dokumente und Diskussionen vor der Anfrage online gestellt. In der Diskussion, die Sie erwähnten, scheint die Schlussfolgerung gesetzt zu sein/get/popitem sind alle "O (1)". Aber ich finde kein offizielles Dokument, in dem erwähnt wird, dass sie wirklich "O (1)" sind. BTW, wenn Sie meinen Beitrag lesen, ist meine Frage, wo ist das offizielle Dokument für die Zeit Komplexität für OrderedDict. :) Bitte zögern Sie nicht, mich zu korrigieren, wenn ich etwas falsch gelesen habe. –