In diesem Text werden die Begriffe Python und CPython, die Referenzimplementierung der Sprache, synonym verwendet. Dieser Artikel befasst sich speziell mit CPython und betrifft keine andere Implementierung von Python.

Python ist eine schöne Sprache, die es einem Programmierer ermöglicht, seine Ideen in einfachen Worten auszudrücken und die Komplexität der tatsächlichen Implementierung hinter den Kulissen zu lassen.

Eines der Dinge, die es abstrahiert, ist das Sortieren.

Sie können leicht die Antwort auf die Frage „Wie wird die Sortierung in Python implementiert?“ finden. was fast immer eine andere Frage beantwortet: „Welchen Sortieralgorithmus verwendet Python?“.

Allerdings bleiben dabei oft einige interessante Implementierungsdetails zurück.

Es gibt ein Implementierungsdetail, das meiner Meinung nach nicht ausreichend besprochen wird, obwohl es vor über sieben Jahren in Python 3.7 eingeführt wurde:

sorted() und list.sort() wurden für häufige Fälle optimiert, um bis zu 40–75 % schneller zu sein. (Beigetragen von Elliot Gorokhovsky in bpo-28685.)

Aber bevor wir anfangen...

Kurze Einführung in die Sortierung in Python

Wenn Sie eine Liste in Python sortieren müssen, haben Sie zwei Möglichkeiten:

• Eine Listenmethode: list.sort(*, key=None, reverse=False), die die angegebene Liste direkt sortiert
• Eine integrierte Funktion: sorted(iterable, /, *, key=None, reverse= False), das eine sortierte Liste zurückgibt, ohne sein Argument zu ändern

Wenn Sie ein anderes integriertes Iterable sortieren müssen, können Sie nur sorted verwenden, unabhängig vom Typ des Iterables oder Generators, der als Parameter übergeben wurde.

sorted gibt immer eine Liste zurück, da list.sort intern verwendet wird.

Hier ist ein grobes Äquivalent der sortierten C-Implementierung von CPython, die in reinem Python neu geschrieben wurde:

def sorted(iterable: Iterable[Any], key=None, reverse=False):
    new_list = list(iterable)
    new_list.sort(key=key, reverse=reverse)
    return new_list

Ja, so einfach ist das.

Wie Python das Sortieren beschleunigt

Wie es in Pythons interner Dokumentation zum Sortieren heißt:

Manchmal ist es möglich, das langsamere, generische PyObject_RichCompareBool durch schnellere typspezifische Vergleiche zu ersetzen

Und kurz gesagt kann diese Optimierung wie folgt beschrieben werden:

Wenn eine Liste homogen ist, verwendet Python eine typspezifische Vergleichsfunktion

Was ist eine homogene Liste?

Eine homogene Liste ist eine Liste, die nur Elemente eines Typs enthält.

Zum Beispiel:

homogeneous = [1, 2, 3, 4]

Andererseits ist dies keine homogene Liste:

heterogeneous = [1, "2", (3, ), {'4': 4}]

Interessanterweise heißt es im offiziellen Python-Tutorial:

Listen sind veränderbar und ihre Elemente sind normalerweise homogen und der Zugriff erfolgt durch Iteration über die Liste

Eine Randbemerkung zu Tupeln

Im selben Tutorial heißt es:

Tupel sind unveränderlich und enthalten normalerweise eine heterogene Folge von Elementen

Wenn Sie sich also jemals fragen, wann Sie ein Tupel oder eine Liste verwenden sollten, finden Sie hier eine Faustregel:
Wenn Elemente vom gleichen Typ sind, verwenden Sie eine Liste, andernfalls verwenden Sie ein Tupel

Moment, und was ist mit Arrays?

Python implementiert ein homogenes Array-Containerobjekt für numerische Werte.

Ab Python 3.12 implementieren Arrays jedoch keine eigene Sortiermethode.

Die einzige Möglichkeit, sie zu sortieren, ist die Verwendung von „sorted“, das intern eine Liste aus dem Array erstellt und dabei alle typbezogenen Informationen löscht.

Warum hilft die Verwendung einer typspezifischen Vergleichsfunktion?

Vergleiche in Python sind kostspielig, da Python verschiedene Prüfungen durchführt, bevor ein tatsächlicher Vergleich durchgeführt wird.

Hier ist eine vereinfachte Erklärung dessen, was unter der Haube passiert, wenn Sie zwei Werte in Python vergleichen:

• Python prüft, ob die an die Vergleichsfunktion übergebenen Werte nicht NULL sind
• Wenn Werte unterschiedlichen Typs sind, der rechte Operand jedoch ein Untertyp des linken Operanden ist, verwendet Python die Vergleichsfunktion des rechten Operanden, jedoch umgekehrt (z. B. wird verwendet)
• Wenn die Werte vom gleichen Typ oder von unterschiedlichen Typen sind, aber keiner ein Untertyp des anderen ist:
  • Python wird zuerst die Vergleichsfunktion des linken Operanden ausprobieren
  • Wenn dies fehlschlägt, wird die Vergleichsfunktion des rechten Operanden versucht, jedoch umgekehrt.
  • Wenn auch dies fehlschlägt und der Vergleich auf Gleichheit oder Ungleichheit ausgerichtet ist, wird ein Identitätsvergleich zurückgegeben (True für Werte, die auf dasselbe Objekt im Speicher verweisen)
  • Andernfalls wird TypeError ausgelöst

Darüber hinaus implementieren die eigenen Vergleichsfunktionen jedes Typs zusätzliche Prüfungen.

Beim Vergleichen von Zeichenfolgen prüft Python beispielsweise, ob die Zeichenfolgenzeichen mehr als ein Byte Speicher beanspruchen, und beim Float-Vergleich wird ein Paar Floats und ein Float und ein Int unterschiedlich verglichen.

Eine ausführlichere Erklärung und ein Diagramm finden Sie hier: Hinzufügen datenbewusster Sortieroptimierungen zu CPython

Bevor diese Optimierung eingeführt wurde, musste Python jedes Mal, wenn zwei Werte während der Sortierung verglichen wurden, all diese verschiedenen typspezifischen und nichttypspezifischen Prüfungen durchführen.

Überprüfen Sie die Typen der Listenelemente im Voraus

Es gibt keinen magischen Weg, um herauszufinden, ob alle Elemente einer Liste vom gleichen Typ sind, außer die Liste zu durchlaufen und jedes Element zu überprüfen.

Python macht fast genau das – es prüft die Arten von Sortierschlüsseln, die von der an list.sort übergebenen oder als Parameter sortierten Schlüsselfunktion generiert werden

Erstellen einer Liste von Schlüsseln

Wenn eine Schlüsselfunktion bereitgestellt wird, verwendet Python diese, um eine Liste von Schlüsseln zu erstellen, andernfalls verwendet es die eigenen Werte der Liste als Sortierschlüssel.

Vereinfacht ausgedrückt kann die Schlüsselkonstruktion als folgender Python-Code ausgedrückt werden.

if key is None:
    keys = list_items
else:
    keys = [key(list_item) for list_item in list_item]

Beachten Sie, dass in CPython intern verwendete Schlüssel ein C-Array von CPython-Objektreferenzen und keine Python-Liste sind

Sobald die Schlüssel erstellt sind, überprüft Python ihre Typen.

Überprüfen des Schlüsseltyps

Bei der Überprüfung der Schlüsseltypen versucht der Sortieralgorithmus von Python festzustellen, ob alle Elemente im Schlüsselarray entweder str, int, float oder tuple sind oder einfach vom gleichen Typ sind, mit einigen Einschränkungen für Basistypen.

Es ist erwähnenswert, dass die Überprüfung der Schlüsseltypen im Vorfeld etwas mehr Arbeit mit sich bringt. Python tut dies, weil es sich normalerweise auszahlt, indem es die eigentliche Sortierung beschleunigt, insbesondere bei längeren Listen.

int-Einschränkungen

int sollte kein eine Bignum sein

Das bedeutet praktisch, dass die Ganzzahl kleiner als 2^30 - 1 sein sollte, damit diese Optimierung funktioniert (dies kann je nach Plattform variieren)

Als Randbemerkung gibt es hier einen großartigen Artikel, der erklärt, wie Python mit großen Ganzzahlen umgeht: # Wie Python superlange Ganzzahlen implementiert?

str-Einschränkungen

Alle Zeichen einer Zeichenfolge sollten weniger als 1 Byte Speicher beanspruchen, was bedeutet, dass sie durch ganzzahlige Werte im Bereich von 0-255 dargestellt werden sollten

In der Praxis bedeutet dies, dass Zeichenfolgen nur aus lateinischen Zeichen, Leerzeichen und einigen Sonderzeichen bestehen sollten, die in der ASCII-Tabelle enthalten sind.

Float-Einschränkungen

Es gibt keine Einschränkungen für Floats, damit diese Optimierung funktioniert.

Tupel-Einschränkungen

• Nur der Typ des ersten Elements wird geprüft
• Dieses Element selbst sollte selbst kein Tupel sein
• Wenn alle Tupel denselben Typ für ihr erstes Element haben, wird die Vergleichsoptimierung auf sie angewendet
• Alle anderen Elemente werden wie gewohnt verglichen

Wie kann ich dieses Wissen anwenden?

Zunächst einmal: Ist es nicht faszinierend, das zu wissen?

Zweitens könnte die Erwähnung dieses Wissens eine nette Geste in einem Python-Entwicklerinterview sein.

Was die tatsächliche Codeentwicklung betrifft, kann Ihnen das Verständnis dieser Optimierung dabei helfen, die Sortierleistung zu verbessern.

Optimieren Sie, indem Sie die Art der Werte mit Bedacht auswählen

Laut dem Benchmark in der PR, die diese Optimierung eingeführt hat, ist das Sortieren einer Liste, die nur aus Floats besteht, und nicht einer Liste von Floats mit auch nur einer einzigen Ganzzahl am Ende, fast doppelt so schnell.

Wenn es also Zeit für eine Optimierung ist, transformieren Sie eine Liste wie diese

floats_and_int = [1.0, -1.0, -0.5, 3]

In eine Liste, die so aussieht

just_floats = [1.0, -1.0, -0.5, 3.0] # note that 3.0 is a float now

könnte die Leistung verbessern.

Optimieren Sie durch die Verwendung von Schlüsseln für Objektlisten

Während die Sortieroptimierung von Python gut mit integrierten Typen funktioniert, ist es wichtig zu verstehen, wie sie mit benutzerdefinierten Klassen interagiert.

Beim Sortieren von Objekten benutzerdefinierter Klassen verlässt sich Python auf die von Ihnen definierten Vergleichsmethoden, z. B. __lt__ (kleiner als) oder __gt__ (größer als).

Die typspezifische Optimierung gilt jedoch nicht für benutzerdefinierte Klassen.
Python verwendet für diese Objekte immer die allgemeine Vergleichsmethode.

Hier ist ein Beispiel:

class MyClass:
    def __init__(self, value): 
        self.value = value 

    def __lt__(self, other): 
        return self.value 



In diesem Fall verwendet Python die Methode __lt__ für Vergleiche, profitiert jedoch nicht von der typspezifischen Optimierung. Die Sortierung funktioniert weiterhin korrekt, ist jedoch möglicherweise nicht so schnell wie die Sortierung integrierter Typen.

Wenn die Leistung beim Sortieren benutzerdefinierter Objekte entscheidend ist, sollten Sie die Verwendung einer Schlüsselfunktion in Betracht ziehen, die einen integrierten Typ zurückgibt:



sorted_list = sorted(my_list, key=lambda x: x.value)





  
  
  Nachwort


Vorzeitige Optimierung, insbesondere in Python, ist böse. 

Sie sollten Ihre gesamte Anwendung nicht auf der Grundlage spezifischer Optimierungen in CPython entwerfen, aber es ist gut, sich dieser Optimierungen bewusst zu sein: Wenn Sie Ihre Tools gut kennen, können Sie ein erfahrenerer Entwickler werden. 

Wenn Sie Optimierungen wie diese im Auge behalten, können Sie sie nutzen, wenn die Situation es erfordert, insbesondere wenn die Leistung kritisch wird: 

Stellen Sie sich ein Szenario vor, in dem Ihre Sortierung auf Zeitstempeln basiert: Die Verwendung einer homogenen Liste von Ganzzahlen (Unix-Zeitstempel) anstelle von Datetime-Objekten könnte diese Optimierung effektiv nutzen.

Es ist jedoch wichtig zu bedenken, dass die Lesbarkeit und Wartbarkeit des Codes Vorrang vor solchen Optimierungen haben sollte. 

Während es wichtig ist, über diese Details auf niedriger Ebene Bescheid zu wissen, ist es genauso wichtig, Pythons Abstraktionen auf hoher Ebene zu schätzen, die es zu einer so produktiven Sprache machen.

Python ist eine erstaunliche Sprache, und die Erforschung ihrer Tiefen kann Ihnen helfen, sie besser zu verstehen und ein besserer Python-Programmierer zu werden.