Hat Python eine sortierte Liste?

128

Womit ich eine Struktur meine mit:

  • O (log n) Komplexität für x.push()Operationen
  • O (log n) Komplexität, um ein Element zu finden
  • O (n) zu berechnende Komplexität, list(x)die sortiert wird

Ich hatte auch eine verwandte Frage zur Leistung, list(...).insert(...)die jetzt hier ist .

ilya n.
quelle
memcpyist immer noch eine O (n) -Operation. Ich bin nicht sicher, wie Python Listen genau implementiert , aber ich wette, dass sie im zusammenhängenden Speicher gespeichert werden (sicherlich nicht als verknüpfte Liste). Wenn dies tatsächlich der Fall ist, hat die Einfügung, mit bisectder Sie demonstrieren, die Komplexität O (n) .
Stephan202
2
Leider nicht out of the box. Aber Grant Jenkins Bibliothek mit sortierten Containern ist ausgezeichnet. stackoverflow.com/a/22616929/284795
Colonel Panic

Antworten:

52

Die Standard-Python-Liste ist in keiner Form sortiert. Das Standard- Heapq- Modul kann verwendet werden, um O (log n) an eine vorhandene Liste anzuhängen und die kleinste in O (log n) zu entfernen, ist jedoch keine sortierte Liste in Ihrer Definition.

Es gibt verschiedene Implementierungen von ausgeglichenen Bäumen für Python, die Ihren Anforderungen entsprechen, z. B. rbtree , RBTree oder pyavl .

Martin v. Löwis
quelle
1
+1 für rbtree, es funktioniert sehr gut (enthält aber nativen Code; nicht reines Python, vielleicht nicht so einfach bereitzustellen)
Will
12
sortedcontainers ist Pure-Python und Fast-as-C (wie rbtree) mit einem Leistungsvergleich.
GrantJ
"ist keine sortierte Liste in Ihrer Definition." Wie?
Colonel Panic
4
Mit heapq kann nur das kleinste Element gefunden werden. Das OP fragte nach einer Struktur, die jedes Element in O (log n) finden kann, was Heaps nicht sind.
Martin v. Löwis
70

Gibt es einen bestimmten Grund für Ihre Big-O-Anforderungen? Oder willst du nur, dass es schnell geht? Das Sortedcontainer- Modul ist rein Python und schnell (wie bei Fast-as-C-Implementierungen wie blist und rbtree).

Der Leistungsvergleich zeigt, dass die Benchmarks schneller oder gleich dem sortierten Listentyp von blist sind. Beachten Sie auch, dass rbtree, RBTree und PyAVL sortierte Diktat- und Set-Typen bereitstellen, jedoch keinen sortierten Listentyp haben.

Wenn Leistung eine Voraussetzung ist, denken Sie immer an einen Benchmark. Ein Modul, das die Behauptung begründet, mit Big-O-Notation schnell zu sein, sollte verdächtig sein, bis es auch Benchmark-Vergleiche zeigt.

Haftungsausschluss: Ich bin der Autor des Python sortedcontainers-Moduls.


Installation:

pip install sortedcontainers

Verwendung:

>>> from sortedcontainers import SortedList
>>> l = SortedList()
>>> l.update([0, 4, 1, 3, 2])
>>> l.index(3)
3
>>> l.add(5)
>>> l[-1]
5
GrantJ
quelle
4
In der Tat habe ich sortierte Container mit bisect verglichen: 0.0845024989976für SortedList.add () vs 0.596589182518für bisect.insort (), also einen Geschwindigkeitsunterschied von 7x! Und ich erwarte, dass die Geschwindigkeitslücke mit der Listenlänge zunimmt, da die Sortiereinfügungssortierung für sortierte Container in O (log n) funktioniert, während bisect.insort () in O (n).
gaborous
1
@gaborous, weil Bisect immer noch eine Liste verwendet, so dass die Einfügung bleibtO(n)
njzk2
34

Obwohl ich die "großen O" -Geschwindigkeiten grundlegender Python-Listenoperationen noch nie überprüft habe, ist das bisectStandardmodul in diesem Zusammenhang wahrscheinlich auch erwähnenswert:

import bisect
L = [0, 100]

bisect.insort(L, 50)
bisect.insort(L, 20)
bisect.insort(L, 21)

print L
## [0, 20, 21, 50, 100]

i = bisect.bisect(L, 20)
print L[i-1], L[i]
## 20, 21

PS. Ah, sorry, bisectwird in der genannten Frage erwähnt. Trotzdem denke ich, dass es nicht viel schaden wird, wenn diese Informationen hier sein werden.

PPS. Und CPython-Listen sind eigentlich Arrays (nicht etwa Skiplists oder so). Nun, ich denke, sie müssen etwas Einfaches sein, aber für mich ist der Name ein bisschen irreführend.


Wenn ich mich nicht irre, wären die Halbierungs- / Listengeschwindigkeiten wahrscheinlich:

  • für einen Push (): O (n) für den schlimmsten Fall;
  • für eine Suche: Wenn wir die Geschwindigkeit der Array-Indizierung als O (1) betrachten, sollte die Suche eine O (log (n)) -Operation sein;
  • für die Listenerstellung: O (n) sollte die Geschwindigkeit des Kopierens der Liste sein, andernfalls ist es O (1) für dieselbe Liste)

Upd. Lassen Sie mich nach einer Diskussion in den Kommentaren hier die folgenden SO-Fragen verknüpfen: Wie wird die Python-Liste implementiert und wie hoch ist die Laufzeitkomplexität der Python- Listenfunktionen ?

ジ ョ ー ジ
quelle
push () sollte in O (log n) sein, da die Liste bereits sortiert ist.
Estani
1
Vielleicht hätte ich "für eine Einfügung op" sagen sollen . Jedenfalls war das vor ungefähr einem Jahr, also kann ich jetzt leicht Dinge durcheinander bringen oder etwas verpassen
ョ ー ジ
Sie können jederzeit einen Wert in eine sortierte Liste in O (log n) einfügen, siehe binäre Suche. push () ist als Einfügeoperation definiert.
Estani
2
Wahr. Während das Finden der Einfügeposition tatsächlich O (log n) ops erfordern würde, hängt die tatsächliche Einfügung (dh das Hinzufügen des Elements zur Datenstruktur) wahrscheinlich von dieser Struktur ab (denken Sie daran, ein Element in ein sortiertes Array einzufügen). Und da Python-Listen tatsächlich Arrays sind , kann dies O (n) dauern. Aufgrund der Größenbeschränkung für die Kommentare werde ich zwei verwandte SO-Fragen aus dem Text der Antwort verknüpfen (siehe oben).
ョ ー ジ
Gutes Argument. Mir war nicht bekannt, wo die Liste in Python als Arrays behandelt wurde.
Estani
7
import bisect

class sortedlist(list):
    '''just a list but with an insort (insert into sorted position)'''
    def insort(self, x):
        bisect.insort(self, x)
Dave31415
quelle
Die implizite Einfügung () in bisect.insort () ist O (n)
j314erre
6

Obwohl es (noch) keine benutzerdefinierte Suchfunktion bietet, kann das heapqModul Ihren Anforderungen entsprechen. Es implementiert eine Heap-Warteschlange mithilfe einer regulären Liste. Sie müssten Ihren eigenen effizienten Mitgliedschaftstest schreiben, der die interne Struktur der Warteschlange nutzt (dies kann in O (log n) erfolgen , würde ich sagen ...). Es gibt einen Nachteil: Das Extrahieren einer sortierten Liste hat die Komplexität O (n log n) .

Stephan202
quelle
Es ist schön, aber schwer zu halbieren.
ilya n.
3
Wie kann es einen O (log n) Mitgliedschaftstest in einem Heap geben? Wenn Sie nach dem Wert x suchen, können Sie aufhören, nach einem Zweig zu suchen, wenn Sie etwas Größeres als x finden. Bei einem zufälligen Wert von x ist es jedoch zu 50% wahrscheinlich, dass sich ein Blatt befindet, und Sie können wahrscheinlich nicht viel beschneiden.
Märkte
1

Ich würde die biscectoder sortedcontainersModule verwenden. Ich bin nicht wirklich erfahren, aber ich denke, das heapqModul funktioniert. Es enthält aHeap Queue

Slass33
quelle
0

Es ist möglicherweise nicht schwierig, eine eigene Sortierliste in Python zu implementieren. Unten finden Sie einen Proof of Concept:

import bisect

class sortlist:
    def __init__(self, list):
        self.list = list
        self.sort()
    def sort(self):
        l = []
        for i in range(len(self.list)):
            bisect.insort(l, self.list[i])
        self.list = l
        self.len = i
    def insert(self, value):
        bisect.insort(self.list, value)
        self.len += 1
    def show(self):
        print self.list
    def search(self,value):
        left = bisect.bisect_left(self.list, value)
        if abs(self.list[min([left,self.len-1])] - value) >= abs(self.list[left-1] - value):
            return self.list[left-1]
        else:
            return self.list[left]

list = [101, 3, 10, 14, 23, 86, 44, 45, 45, 50, 66, 95, 17, 77, 79, 84, 85, 91, 73]
slist = sortlist(list)
slist.show()
slist.insert(99)
slist.show()
print slist.search(100000000)
print slist.search(0)
print slist.search(56.7)

========= Ergebnisse ============

[3, 10, 14, 17, 23, 44, 45, 45, 50, 66, 73, 77, 79, 84, 85, 86, 91, 95, 101]

[3, 10, 14, 17, 23, 44, 45, 45, 50, 66, 73, 77, 79, 84, 85, 86, 91, 95, 99, 101]

101

3

50

Ventilator
quelle