Ich muss fortlaufend Zahlen zu einer vorsortierten Liste hinzufügen:
%Vor%Jede Iteration ist kurz, aber wenn die angegebene numberList Zehntausende von Werten enthält, wird diese Methode langsamer. Gibt es eine effizientere Funktion, die eine Liste intakt lässt und herausfindet, welcher Index eine neue Zahl einfügen soll, um die richtige Reihenfolge der Zahlen zu erhalten? Alles, was ich selbst geschrieben habe, dauert länger als .sort ()
Siehe die native bisect.insort (), die das Einfügen von Sortierungen in Listen implementiert. Dies sollte perfekt zu Ihren Bedürfnissen seit den Komplexität ist höchstens O (n) und O (n ^ 2) im schlechtesten Fall anstelle von O (nlogn) mit Ihrer aktuellen Lösung (nach dem Einfügen).
Es gibt jedoch schnellere Alternativen zum Erstellen einer sortierten Datenstruktur, z. B. Skip-Listen und binäre Suchbäume, die eine Einfügung mit der Komplexität O (log n) bestenfalls und O (n) schlimmstenfalls oder sogar bessere B-Bäume ermöglichen, Rot-Schwarz-Bäume , Splay-Bäume und AVL-Bäume, die alle eine Komplexität O (log n) sowohl im besten als auch im schlechtesten Fall haben. Mehr Informationen über die Komplexität all dieser Lösungen und andere finden Sie in dem großen BigO CheatSheet von Eric Rowell. Beachten Sie jedoch, dass Sie bei all diesen Lösungen ein Modul eines Drittanbieters installieren müssen. Im Allgemeinen müssen sie mit einem C-Compiler kompiliert werden.
Allerdings gibt es ein reines Python-Modul namens sortedcontainers , das angeblich genauso schnell oder schneller ist als C kompilierte Python-Erweiterungen von Implementierungen von AVL-Bäumen und B-Bäumen ( Benchmark hier verfügbar ).
Ich habe ein paar Lösungen verglichen, um zu sehen, welches die schnellste Art ist, eine Insertion durchzuführen:
%Vor%Hier ist der Code, den ich verwendet habe:
%Vor%Die Ergebnisse zeigen also, dass die sortedcontainers tatsächlich fast 7x schneller sind als bisect (und ich erwarte, dass die Geschwindigkeitslücke mit der Listengröße zunimmt, da die Komplexität um eine Größenordnung unterschiedlich ist).
Was noch überraschender ist, ist, dass die Skip-Liste langsamer als halbiert ist, aber es ist wahrscheinlich nicht so optimiert wie halbiert, was in C implementiert ist und einige Optimierungstricks verwenden kann (beachten Sie, dass das Modul skiplist.py das war) schnellste Pure-Python-Skip-Liste Ich konnte finden, das Pyskip-Modul ist viel langsamer).
Beachten Sie auch: Wenn Sie komplexere Strukturen als Listen verwenden müssen, bietet das sortainedcontainers-Modul SortedList, SortedListWithKey, SortedDict und SortedSet (während bisect nur für Listen funktioniert). Vielleicht interessiert Sie auch dieser etwas verwandten Benchmark und dies Komplexitäts-Cheatsheet verschiedener Python-Operationen .
Sie können die Funktion bisect.insort() verwenden, um Werte in bereits sortierte Werte einzufügen Liste:
Beachten Sie, dass dies noch einige Zeit dauern wird, da die restlichen Elemente nach dem Einfügepunkt alle um einen Schritt nach oben verschoben werden müssen. Vielleicht möchten Sie darüber nachdenken, die Liste stattdessen als verkettete Liste zu implementieren.
Wenn Sie jedoch die Liste sortiert halten, um immer die kleinste oder größte Zahl erhalten zu können, sollten Sie die heapq Modul stattdessen; Ein Heap wird nicht in einer streng sortierten Reihenfolge gehalten, sondern ist sehr effizient, um Ihnen entweder den kleinsten oder den größten Wert jederzeit sehr schnell zu geben.
Tags und Links python python-2.7 sorting