Python sortierte Container
v2.1.0 JOSS
Sorted Containers ist eine Apache2-lizenzierte Bibliothek für sortierte Sammlungen, die in reinem Python geschrieben und so schnell wie C-Erweiterungen ist.
Die Standardbibliothek von Python ist großartig, bis Sie einen sortierten Sammlungstyp benötigen. Viele werden bestätigen, dass man ohne eine wirklich weit kommen kann, aber sobald Sie wirklich eine sortierte Liste, ein sortiertes Diktat oder eine sortierte Menge benötigen , werden Sie mit einem Dutzend verschiedener Implementierungen konfrontiert, von denen die meisten C-Erweiterungen ohne umfangreiche Dokumentation und Benchmarking verwenden.
Mit Python können wir es besser machen. Und wir können es in reinem Python machen!
> >> from sortedcontainers import SortedList
> >> sl = SortedList ([ 'e' , 'a' , 'c' , 'd' , 'b' ])
> >> sl
SortedList ([ 'a' , 'b' , 'c' , 'd' , 'e' ])
> >> sl *= 10_000_000
> >> sl . count ( 'c' )
10000000
> >> sl [ - 3 :]
[ 'e' , 'e' , 'e' ]
> >> from sortedcontainers import SortedDict
> >> sd = SortedDict ({ 'c' : - 3 , 'a' : 1 , 'b' : 2 })
> >> sd
SortedDict ({ 'a' : 1 , 'b' : 2 , 'c' : - 3 })
> >> sd . popitem ( index = - 1 )
( 'c' , - 3 )
> >> from sortedcontainers import SortedSet
> >> ss = SortedSet ( 'abracadabra' )
> >> ss
SortedSet ([ 'a' , 'b' , 'c' , 'd' , 'r' ])
> >> ss . bisect_left ( 'c' )
2Alle oben gezeigten Vorgänge laufen schneller als die lineare Zeit ab. Die obige Demo benötigt zum Ausführen außerdem fast ein Gigabyte Speicher. Wenn die sortierte Liste mit zehn Millionen multipliziert wird, werden jeweils zehn Millionen Verweise auf „a“ bis „e“ gespeichert. Jede Referenz benötigt acht Bytes im sortierten Container. Das ist ziemlich schwer zu schlagen, da es sich um die Kosten eines Zeigers auf jedes Objekt handelt. Es ist außerdem 66 % weniger Overhead als eine typische Binärbaumimplementierung (z. B. Red-Black Tree, AVL-Tree, AA-Tree, Splay-Tree, Treap usw.), bei der jeder Knoten auch zwei Zeiger auf untergeordnete Knoten speichern muss.
Sorted Containers nimmt Ihnen die gesamte Arbeit aus sortierten Python-Sammlungen ab und vereinfacht so die Bereitstellung und Nutzung von Python. Es ist nicht erforderlich, einen C-Compiler zu installieren oder benutzerdefinierte Erweiterungen vorab zu erstellen und zu verteilen. Leistung ist eine Funktion und Tests decken 100 % mit Unit-Tests und stundenlangem Stress ab.
Alex Martelli , Fellow der Python Software Foundation
„Gute Sache! ... Mir gefällt die einfache, effektive Implementierungsidee, die sortierten Container in kleinere „Fragmente“ aufzuteilen, um die O(N)-Einfügekosten zu vermeiden.“
Jeff Knupp , Autor von Writing Idiomatic Python und Python Trainer
„Dieser letzte Teil, „schnell wie C-Erweiterungen“, war schwer zu glauben. Ich bräuchte eine Art Leistungsvergleich, um überzeugt zu sein, dass das wahr ist. Der Autor nimmt dies in die Dokumente auf. Das ist es.“
Kevin Samuel , Python- und Django-Trainer
Ich bin ziemlich erstaunt, nicht nur von der Codequalität (er ist unglaublich lesbar und hat mehr Kommentare als Code, wow), sondern auch von der tatsächlichen Menge an Arbeit, die Sie in Dinge stecken, die kein Code sind: Dokumentation, Benchmarking, Implementierungserklärungen. Sogar das Git-Protokoll ist sauber und die Unit-Tests laufen sofort auf Python 2 und 3.
Mark Summerfield , ein kurzes Plädoyer für Python Sorted Collections
In der Standardbibliothek „Batterien enthalten“ von Python scheint eine Batterie zu fehlen. Und das Argument, dass „wir es noch nie zuvor hatten“, hat sich nicht mehr bewährt. Es ist an der Zeit, dass Python eine vollständige Palette standardmäßiger Sammlungsklassen anbietet, einschließlich sortierter Klassen.
Sorted Containers wird in beliebten Open-Source-Projekten verwendet, wie zum Beispiel: Zipline, eine algorithmische Handelsbibliothek von Quantopian; Angr, eine binäre Analyseplattform der UC Santa Barbara; Trio, eine asynchrone I/O-Bibliothek; und Dask Distributed, eine verteilte Berechnungsbibliothek, die von Continuum Analytics unterstützt wird.
Die Installation von Sorted Containers ist mit pip ganz einfach:
$ pip sortierte Container installieren
Mit der integrierten Hilfefunktion von Python können Sie im Interpreter auf die Dokumentation zugreifen. Die Hilfe funktioniert für Module, Klassen und Methoden in Sorted Containers.
> >> import sortedcontainers
> >> help ( sortedcontainers )
> >> from sortedcontainers import SortedDict
> >> help ( SortedDict )
> >> help ( SortedDict . popitem )Die vollständige Dokumentation für Sorted Containers ist unter http://www.grantjenks.com/docs/sortedcontainers/ verfügbar.
Das Benutzerhandbuch bietet eine Einführung in Sorted Containers sowie ausführliche Leistungsvergleiche und -analysen.
Der Community-Leitfaden bietet Informationen zur Entwicklung von Sorted Containers sowie Details zu Support, Implementierung und Verlauf.
Die API-Dokumentation bietet Informationen zu bestimmten Funktionen, Klassen und Modulen im Sorted Containers-Paket.
Copyright 2014-2024 Grant Jenks
Lizenziert unter der Apache-Lizenz, Version 2.0 (die „Lizenz“); Sie dürfen diese Datei nur in Übereinstimmung mit der Lizenz verwenden. Eine Kopie der Lizenz erhalten Sie unter
http://www.apache.org/licenses/LICENSE-2.0
Sofern nicht durch geltendes Recht vorgeschrieben oder schriftlich vereinbart, wird die im Rahmen der Lizenz vertriebene Software „WIE BESEHEN“ und OHNE GEWÄHRLEISTUNGEN ODER BEDINGUNGEN JEGLICHER ART, weder ausdrücklich noch stillschweigend, vertrieben. Die spezifische Sprache, die die Berechtigungen und Einschränkungen im Rahmen der Lizenz regelt, finden Sie in der Lizenz.
