Ablehnungsbescheid

Abgelehnt auf Grundlage des weisen Rats von Raymond Hettinger [4]

Nachdem ich mir den Quellcode angesehen habe, glaube ich, dass dies fast keine Chance hat, list() zu ersetzen. Es gibt zu viel Wert in einer einfachen C-API, geringem Speicherbedarf für kleine Listen, guter Leistung in gängigen Anwendungsfällen und einer leicht verständlichen Leistung. Der BList-Implementierung fehlen diese Tugenden und sie tauscht ein wenig Leistung in gängigen Fällen gegen viel bessere Leistung in unüblichen Fällen. Als Py3.0 PEP glaube ich, dass sie abgelehnt werden kann.

Je nach Erfolg als Drittanbietermodul hat sie immer noch eine Chance auf Aufnahme in das collections-Modul. Das wesentliche Kriterium dafür ist, ob sie für einige reale Anwendungsfälle eine überlegene Wahl ist. Ich habe meinen eigenen Code durchgesehen und keine Fälle gefunden, in denen BList einer regulären Liste vorzuziehen gewesen wäre. Diese Überprüfung unterliegt jedoch einer Selektionsverzerrung, da sie nicht widerspiegelt, was ich geschrieben hätte, wenn BList verfügbar gewesen wäre. Daher beabsichtige ich, nach ein paar Monaten comp.lang.python nach Erfolgsgeschichten mit BList abzufragen. Wenn diese existieren, habe ich kein Problem mit der Aufnahme in das collections-Modul. Schließlich ist die Lernkurve nahezu null – die einzige Kosten sind der Aufwand durch Unentschlossenheit über die am besten geeignete Datenstruktur für eine gegebene Aufgabe.

Zusammenfassung

Der häufigste Fall für Listenoperationen betrifft kleine Listen. Die aktuelle arraybasierte Listenimplementierung ist für kleine Listen aufgrund der starken Lokalität der Referenz und der geringen Häufigkeit von Speicherallokationsoperationen gut geeignet. Eine Einfügung und Löschung von Elementen in einem Array dauert jedoch O(n) Zeit, was problematisch werden kann, wenn die Liste groß wird.

Dieses PEP führt einen neuen Datentyp, die BList, ein, der Array-ähnliche und Baum-ähnliche Aspekte aufweist. Sie weist die gleiche gute Leistung für kleine Listen wie die bestehende arraybasierte Implementierung auf, bietet aber eine überlegene asymptotische Leistung für die meisten Operationen. Dieses PEP schlägt vor, die beiden sich gegenseitig ausschließenden Vorschläge zur Aufnahme des BList-Typs in Python zu ersetzen

1. fügen Sie es dem collections-Modul hinzu, oder
2. Ersetzen Sie den bestehenden list-Typ

Motivation

Die BList entstand aus der Frustration, intuitive Algorithmen neu schreiben zu müssen, die für kleine Eingaben gut funktionierten, aber für große Eingaben O(n**2) Zeit beanspruchten, aufgrund des zugrunde liegenden O(n)-Verhaltens von arraybasierten Listen. Der in Python 2.4 eingeführte deque-Typ löste das häufigste Problem der Notwendigkeit einer schnellen FIFO-Warteschlange. Der deque-Typ hilft jedoch nicht, wenn wir wiederholt Elemente aus der Mitte einer langen Liste einfügen oder löschen müssen.

Eine breite Palette von Datenstrukturen bietet eine gute asymptotische Leistung für Einfügungen und Löschungen, aber sie haben entweder eine Leistung von O(n) für andere Operationen (z. B. verkettete Listen) oder eine unterlegene Leistung für kleine Listen (z. B. Binärbäume und Skip-Listen).

Der in diesem PEP vorgeschlagene BList-Typ basiert auf den Prinzipien von B+-Bäumen, die Array-ähnliche und Baum-ähnliche Aspekte aufweisen. Die BList bietet eine array-ähnliche Leistung für kleine Listen, während sie O(log n) asymptotische Leistung für alle Einfüge- und Löschoperationen bietet. Zusätzlich implementiert die BList intern Copy-on-Write, sodass selbst Operationen wie getslice O(log n) Zeit beanspruchen. Die folgende Tabelle vergleicht die asymptotische Leistung der aktuellen arraybasierten Listenimplementierung mit der asymptotischen Leistung der BList.

Ein umfangreicher empirischer Vergleich der arraybasierten Liste von Python und der BList ist verfügbar unter [2].

Kompromisse bei Anwendungsfällen

Die BList bietet für viele, aber nicht alle, Operationen eine überlegene Leistung. Die Wahl des richtigen Datentyps für einen bestimmten Anwendungsfall hängt davon ab, welche Operationen verwendet werden. Die Wahl des richtigen Datentyps als eingebaute Funktion hängt von der Abwägung der Bedeutung verschiedener Anwendungsfälle und der Größenordnung der Leistungsunterschiede ab.

Für die gängigen Anwendungsfälle von kleinen Listen weisen die arraybasierte Liste und die BList ähnliche Leistungseigenschaften auf.

Für den etwas weniger häufigen Fall von großen Listen gibt es zwei gängige Anwendungsfälle, bei denen die bestehende arraybasierte Liste die bestehende BList-Referenzimplementierung übertrifft. Diese sind

1. Ein großer LIFO-Stack, bei dem viele .append()- und .pop(-1)-Operationen durchgeführt werden. Jede Operation ist O(1) für eine arraybasierte Liste, aber O(log n) für die BList.
2. Eine große Liste, deren Größe sich nicht ändert. Die Aufrufe von getitem und setitem sind O(1) für eine arraybasierte Liste, aber O(log n) für die BList.

In Leistungstests mit einer Liste von 10.000 Elementen zeigte die BList für diese beiden Anwendungsfälle eine Erhöhung der Ausführungszeit um 50 % bzw. 5 %.

Die Leistung für den LIFO-Anwendungsfall könnte durch Caching eines Zeigers auf das rechteste Blatt im Wurzelknoten auf O(n) Zeit verbessert werden. Für Listen, die ihre Größe nicht ändern, könnte der gängige Fall des sequenziellen Zugriffs ebenfalls durch Caching im Wurzelknoten auf O(n) Zeit verbessert werden. Die Leistung dieser Ansätze wurde jedoch empirisch nicht getestet.

Viele Operationen zeigen eine enorme Geschwindigkeitssteigerung (O(n) auf O(log n)), wenn von der arraybasierten Liste auf BLists umgeschaltet wird. In Leistungstests mit einer Liste von 10.000 Elementen benötigen Operationen wie getslice, setslice sowie FIFO-artige Einfüge- und Löschvorgänge bei einer BList nur 1 % der Zeit, die für arraybasierte Listen benötigt wird.

Angesichts der großen Leistungssteigerungen für viele Operationen werden die geringen Leistungskosten für einige Operationen für viele (aber nicht alle) Anwendungen lohnenswert sein.

Implementierung

Die BList basiert auf der B+-Baum-Datenstruktur. Die BList ist ein breiter, buschiger Baum, in dem jeder Knoten ein Array mit bis zu 128 Zeigern auf seine Kinder enthält. Wenn der Knoten ein Blatt ist, sind seine Kinder die vom Benutzer in die Liste platzierten Objekte. Wenn der Knoten kein Blatt ist, sind seine Kinder andere BList-Knoten, die für den Benutzer nicht sichtbar sind. Wenn die Liste nur wenige Elemente enthält, werden sie alle Kinder eines einzelnen Knotens sein, der sowohl die Wurzel als auch ein Blatt ist. Da ein Knoten wenig mehr als ein Array von Zeigern ist, funktionieren kleine Listen praktisch genauso wie eine arraybasierte Datentyp und weisen die gleichen guten Leistungseigenschaften auf.

Die BList unterhält einige Invarianten, um eine gute asymptotische Leistung (O(log n)) unabhängig von der Sequenz der Einfüge- und Löschoperationen zu gewährleisten. Die wichtigsten Invarianten sind:

1. Jeder Knoten hat höchstens 128 Kinder.
2. Jeder Nicht-Wurzelknoten hat mindestens 64 Kinder.
3. Der Wurzelknoten hat mindestens 2 Kinder, es sei denn, die Liste enthält weniger als 2 Elemente.
4. Der Baum ist von gleichmäßiger Tiefe.

Wenn eine Einfügung dazu führen würde, dass ein Knoten 128 Kinder überschreitet, spaltet der Knoten einen Geschwisterknoten ab und überträgt die Hälfte seiner Kinder an den Geschwisterknoten. Der Geschwisterknoten wird in das Elternteil des Knotens eingefügt. Wenn der Knoten der Wurzelknoten ist (und somit kein Elternteil hat), wird ein neues Elternteil erstellt und die Tiefe des Baumes um eins erhöht.

Wenn eine Löschung dazu führen würde, dass ein Knoten weniger als 64 Kinder hat, verschiebt der Knoten Elemente von einem seiner Geschwisterknoten, falls möglich. Wenn beide Geschwisterknoten ebenfalls nur 64 Kinder haben, werden zwei der Knoten zusammengeführt und der leere Knoten aus seinem Elternteil entfernt. Wenn die Wurzel auf nur ein Kind reduziert wird, wird ihr einziges Kind zur neuen Wurzel (d. h. die Tiefe des Baumes wird um eins verringert).

Neben baumartiger asymptotischer Leistung und arrayähnlicher Leistung bei kleinen Listen unterstützt die BList transparentes **Copy-on-Write**. Wenn ein Nicht-Wurzelknoten kopiert werden muss (als Teil von getslice, copy, setslice usw.), wird der Knoten zwischen mehreren Eltern geteilt, anstatt kopiert zu werden. Wenn er später geändert werden muss, wird er zu diesem Zeitpunkt kopiert. Dies geschieht vollständig im Hintergrund; aus Sicht des Benutzers verhält sich die BList wie eine normale Python-Liste.

Speicherverbrauch

Im schlimmsten Fall haben die Blattknoten einer BList nur 64 Kinder, anstatt volle 128, was bedeutet, dass der Speicherverbrauch etwa doppelt so hoch ist wie bei einer best-case-Array-Implementierung. Nicht-Blattknoten verbrauchen nur einen vernachlässigbaren zusätzlichen Speicher, da es mindestens 63 Mal mehr Blattknoten als Nicht-Blattknoten gibt.

Die bestehende arraybasierte Listenimplementierung muss beim Hinzufügen und Entfernen von Elementen wachsen und schrumpfen. Um effizient zu sein, wächst und schrumpft sie nur, wenn die Liste exponentiell gewachsen oder geschrumpft ist. Im schlimmsten Fall verbraucht sie ebenfalls doppelt so viel Speicher wie im besten Fall.

Zusammenfassend lässt sich sagen, dass der Speicherbedarf der BList nicht wesentlich anders ist als bei der bestehenden arraybasierten Implementierung.

Abwärtskompatibilität

Wenn die BList dem collections-Modul hinzugefügt wird, gibt es keine Probleme mit der Abwärtskompatibilität. Dieser Abschnitt konzentriert sich auf die Option, die bestehende arraybasierte Liste durch die BList zu ersetzen. Für Benutzer des Python-Interpreters hat eine BList eine identische Schnittstelle zur aktuellen Listenimplementierung. Für praktisch alle Operationen ist das Verhalten identisch, abgesehen von der Ausführungsgeschwindigkeit.

Für die C-API hat die BList eine andere Schnittstelle als die bestehende Listenimplementierung. Aufgrund ihrer komplexeren Struktur eignet sich die BList nicht gut für direkte Inspektion und Manipulation von externen Quellen. Glücklicherweise definiert die bestehende Listenimplementierung eine API von Funktionen und Makros zum Zugriff auf Daten aus Listenobjekten. Google Code Search legt nahe, dass die Mehrheit der Drittanbietermodule die gut definierte API verwendet und nicht direkt auf die Struktur der Liste zugreift. Die folgende Tabelle fasst die Suchanfragen und Ergebnisse zusammen:

Dies kann auf zwei Arten erreicht werden:

1. Definieren Sie die verschiedenen Zugriffsfunktionen und Makros in listobject.h neu, um stattdessen auf eine BList zuzugreifen. Die Schnittstelle wäre unverändert. Die Funktionen können leicht neu definiert werden. Die Makros erfordern etwas mehr Sorgfalt und würden bei großen Listen auf Funktionsaufrufe zurückgreifen müssen.

   Die Makros müssten ihre Argumente mehr als einmal auswerten, was ein Problem darstellen könnte, wenn die Argumente Nebeneffekte haben. Eine Google Code Search nach „PyList_GET_ITEM([^)]+(“ fand nur eine Handvoll Fälle, in denen dies vorkommt, daher scheint die Auswirkung gering zu sein.

   Die wenigen Erweiterungsmodule, die die undokumentierte Struktur der Liste direkt verwenden, anstatt die API zu verwenden, würden brechen. Der Kerncode selbst verwendet die Zugriffs-Makros recht konsistent und sollte einfach zu portieren sein.

2. Deprizieren Sie den bestehenden list-Typ, aber behalten Sie ihn bei. Erweiterungsmodule, die den neuen BList-Typ verwenden möchten, müssen dies explizit tun. Die C-Schnittstelle der BList kann so geändert werden, dass sie mit der bestehenden PyList-Schnittstelle übereinstimmt, sodass ein einfacher Suchen-Ersetzen-Vorgang für 99 % der Modulautoren ausreichend ist.

   Bestehende Module würden weiterhin ohne Änderungen kompiliert und funktionieren, aber sie müssten bewusst (aber geringfügig) Aufwand betreiben, um auf die BList zu migrieren.

   Der Nachteil dieses Ansatzes ist, dass das Mischen von Modulen, die BLists verwenden, und arraybasierte Listen zu Verlangsamungen führen kann, wenn häufig Konvertierungen erforderlich sind.

Referenzimplementierung

Eine Referenzimplementierung der BList ist für CPython unter [1] verfügbar.

Das Quellpaket enthält auch eine reine Python-Implementierung, die ursprünglich als Prototyp für die CPython-Version entwickelt wurde. Natürlich ist die reine Python-Version eher langsam und die asymptotischen Verbesserungen kommen erst zum Tragen, wenn die Liste ziemlich groß ist.

Beim Kompilieren mit Py_DEBUG prüft die C-Implementierung die BList-Invarianten beim Eintritt und Austritt aus den meisten Funktionen.

Ein umfangreicher Satz von Testfällen ist ebenfalls im Quellpaket enthalten. Die Testfälle umfassen die bestehenden Python-Sequenz- und Listen-Testfälle als Teilmenge. Wenn der Interpreter mit Py_DEBUG erstellt wird, überprüfen die Testfälle auch auf Referenzlecks.

Diskussion

Dieser Vorschlag wurde kurz auf der Python-3000-Mailingliste diskutiert [3]. Obwohl eine Reihe von Leuten den Vorschlag befürworteten, gab es auch einige Einwände. Nachfolgend werden die von den Poster der Diskussion beobachteten Vor- und Nachteile zusammengefasst.

Allgemeine Kommentare

• Vorteil: Wird die arraybasierte Liste in den meisten Fällen übertreffen
• Vorteil: „Ich habe Varianten davon implementiert … ein paar Mal“
• Nachteil: Begehrlichkeit und Leistung in tatsächlichen Anwendungen sind nicht bewiesen

Kommentare zur Aufnahme von BList in das collections-Modul

• Vorteil: Die Anpassung an die list-API reduziert die Lernkurve auf nahezu null
• Vorteil: Nützlich für fortgeschrittene Benutzer; wird Anfänger nicht behindern
• Nachteil: Die Vermehrung von Datentypen erschwert die Auswahl für Entwickler.

Kommentare zum Ersetzen der arraybasierten Liste durch die BList

• Nachteil: Auswirkungen auf Erweiterungsmodule (behandelt in Abwärtskompatibilität)
• Nachteil: Die Anwendungsfälle, bei denen BLists langsamer sind, sind wichtig (siehe Kompromisse bei Anwendungsfällen, wie diese möglicherweise angegangen werden können).
• Nachteil: Der arraybasierte Listen-Code ist einfach und leicht zu warten

Um die Begehrlichkeit und Leistung in tatsächlichen Anwendungen zu bewerten, schlug Raymond Hettinger vor, die BList als Erweiterungsmodul freizugeben (jetzt verfügbar unter [1]). Wenn es sich als nützlich erweist, würde es seiner Meinung nach ein starker Kandidat für die Aufnahme in 2.6 als Teil des collections-Moduls sein. Wenn es weit verbreitet ist, könnte es in Betracht gezogen werden, die arraybasierte Liste zu ersetzen, aber nicht anderweitig.

Guido van Rossum bemerkte, dass er sich gegen die Vermehrung von Datentypen aussprach, aber die arraybasierte Liste ersetzen würde, wenn die Abwärtskompatibilität gewährleistet wäre und die Leistung der BList einheitlich besser wäre.

Laufende Aufgaben

• Reduzieren Sie den Speicherbedarf von kleinen Listen
• Implementieren Sie TimSort für BLists, damit die best-case-Sortierung O(n) statt O(log n) ist.
• Implementieren Sie __reversed__
• Cachen Sie einen Zeiger in der Wurzel auf das rechteste Blatt, um LIFO-Operationen O(n)-Zeit zu geben.

Referenzen

Urheberrecht

Dieses Dokument wurde gemeinfrei erklärt.