Alternative zu Pythons .Sort() (für in eine große Liste einfügen und halten es sortiert)

Question

Ich muss ständig Zahlen addieren zu einer vorsortierten Liste:

for num in numberList: 
    list.append(num) 
    list.sort() 

Jede Iteration kurz ist, aber wenn die gegebene numberList enthält Zehntausende von Werten, die diese Methode verlangsamt. 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 versucht habe, selbst zu schreiben dauert länger als .sort()

Answer 1

Siehe die native bisect.insort(), die Insertion Sortierung auf Listen implementiert, sollte dies perfekt Ihre Bedürfnisse seit der complexity is O(n) at best and O(n^2) at worst anstelle von O (nlogn) mit Ihrem aktuelle Lösung (Umsortierung nach dem Einfügen).

Es gibt jedoch schnellere Alternativen zum Aufbau einer sortierten Datenstruktur wie Skip Lists und binäre Suchbäume, die eine Einfügung mit der Komplexität O (log n) bestenfalls und O (n) schlimmstenfalls oder sogar besser B- ermöglichen. Bäume, Red-Black trees, Splay-Bäume und AVL-Bäume, die alle eine Komplexität O (log n) sowohl im besten als auch im schlechtesten Fall aufweisen. Mehr Informationen über die Komplexität all dieser Lösungen und andere finden Sie in der großen BigO CheatSheet von Eric Rowell. Beachten Sie jedoch, dass bei all diesen Lösungen die Installation eines Drittanbietermoduls erforderlich ist und diese im Allgemeinen mit einem C-Compiler kompiliert werden müssen.

Es gibt jedoch ein reines Python-Modul namens sortedcontainers, das behauptet, so schnell oder schneller zu sein wie C kompilierte Python-Erweiterungen von Implementierungen von AVL-Bäumen und B-Bäumen (benchmark available here).

ich ein paar Lösungen gebenchmarkt zu sehen, welche die schnellste ist eine Insertionsort zu tun:

sortedcontainers: 0.0860911591881 
bisect: 0.665865982912 
skiplist: 1.49330501066 
sort_insert: 17.4167637739 

der Code, den ich zum Benchmark verwendet Ist hier:

from timeit import Timer 
setup = """ 
L = list(range(10000)) + list(range(10100, 30000)) 
from bisect import insort 

def sort_insert(L, x): 
    L.append(x) 
    L.sort() 

from lib.skiplist import SkipList 
L2 = SkipList(allowDups=1) 
for x in L: 
    L2.insert(x) 

from lib.sortedcontainers import SortedList 
L3 = SortedList(L) 
""" 

# Using sortedcontainers.SortedList() 
t_sortedcontainers = Timer("for i in xrange(10000, 10100): L3.add(i)", setup) 
# Using bisect.insort() 
t_bisect = Timer("for i in xrange(10000, 10100): insort(L, i)", setup) 
# Using a Skip List 
t_skiplist = Timer("for i in xrange(10000, 10100): L2.insert(i)", setup) 
# Using a standard list insert and then sorting 
t_sort_insert = Timer("for i in xrange(10000, 10100): sort_insert(L, i)", setup) 

# Timing the results 
print t_sortedcontainers.timeit(number=100) 
print t_bisect.timeit(number=100) 
print t_skiplist.timeit(number=100) 
print t_sort_insert.timeit(number=100) 

So zeigen die Ergebnisse, dass die sortedcontainers ist tatsächlich fast 7x schneller als halbiert (und ich erwarte, dass die Geschwindigkeitslücke mit der Listengröße zunimmt, da die Komplexität eine Größenordnung unterschiedlich ist).

Noch überraschender ist, dass die Skip-Liste langsamer als halbiert ist, aber es ist wahrscheinlich nicht so optimiert wie halbiert, die in C implementiert ist und einige Optimierungstricks verwenden kann (beachten Sie, dass das skiplist.py-Modul war) die schnellste Pure-Python-Skip-Liste, die ich finden konnte, die pyskip module ist viel langsamer).

Ebenfalls zu beachten: Wenn Sie komplexere Strukturen als Listen verwenden müssen, bietet das sortainedcontainers-Modul SortedList, SortedListWithKey, SortedDict und SortedSet an (während bisect nur auf Listen funktioniert). Vielleicht interessiert Sie auch diese somewhat related benchmark und diese complexity cheatsheet of various Python operations.

Answer 2

können Sie die bisect.insort() function verwenden, um Werte in eine bereits sortierte Liste einzufügen:

from bisect import insort 

insort(list, num) 

Beachten Sie, dass dies noch einige Zeit dauern würde als die übrigen Elemente nach der Einfügemarke alle 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 Nummer zu erhalten, sollten Sie statt dessen die heapq module verwenden; Ein Heap wird nicht in einer streng sortierten Reihenfolge gehalten, sondern ist sehr effizient, um Ihnen entweder den kleinsten oder den größten Wert zu jeder Zeit sehr schnell zu geben.