Leistung der Liste (...). Einfügen (...)

Question

Ich dachte über die folgende Frage über die Architektur des Computers nach. Angenommen ich in Python

from bisect import bisect 
index = bisect(x, a)  # O(log n) (also, shouldn't it be a standard list function?) 
x.insert(index, a)  # O(1) + memcpy() 

die log n nimmt, plus, wenn ich es richtig verstanden hat, ein Speicherkopiervorgang für x[index:]. Jetzt habe ich kürzlich gelesen, dass der Flaschenhals normalerweise in der Kommunikation zwischen Prozessor und Speicher liegt, so dass die Speicherkopie durch RAM recht schnell erledigt werden kann. So funktioniert das?

Answer 1

Python ist eine Sprache. Multiple implementations exist, und sie können verschiedene Implementierungen für Listen haben. Ohne den Code einer tatsächlichen Implementierung zu sehen, können Sie also nicht sicher sein, wie Listen implementiert sind und wie sie sich unter bestimmten Umständen verhalten.

Meine Wette wäre, dass die Referenzen auf die Objekte in einer Liste im zusammenhängenden Speicher (sicherlich nicht als eine verknüpfte Liste ...) gespeichert werden. Wenn dies tatsächlich der Fall ist, bewirkt das Einfügen unter Verwendung von x.insert, dass alle Elemente hinter dem eingefügten Element verschoben werden. Dies kann effizient durch die Hardware erfolgen, aber die Komplexität wäre immer noch O (n).

Für kleine Listen der bisect Betrieb kann mehr Zeit in Anspruch nehmen als x.insert, obwohl der ehemalige O (log n) ist während letztere O (n) ist. Bei langen Listen würde ich jedoch vermuten, dass x.insert der Engpass ist. In solchen Fällen müssen Sie eine andere Datenstruktur verwenden.

Answer 2

CPython-Listen sind zusammenhängende Arrays. Welches der O (log n) Halbierung und O (n) Einfügung dominiert Ihr Leistungsprofil hängt von der Größe Ihrer Liste und auch die konstanten Faktoren innerhalb der O(). Insbesondere kann die Vergleichsfunktion, die durch die Halbierung aufgerufen wird, in Abhängigkeit vom Typ der Objekte in der Liste teuer sein.

Wenn Sie potenziell große veränderbare sortierte Sequenzen halten müssen, ist das lineare Array, das dem Pythons-Listentyp zugrunde liegt, keine gute Wahl. Abhängig von Ihren Anforderungen können Haufen, Bäume oder Skip-Listen angebracht sein.

Answer 3

Verwenden Sie die blist module, wenn Sie eine Liste mit einer besseren Einfügeleistung benötigen.