Wie die Vergleichsoptimierung die Python-Sortierung beschleunigt

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 dabei 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 gegebene 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, neu geschrieben in reinem Python:

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 der internen Dokumentation von Python zum Sortieren heißt:

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

Und kurz gesagt lässt sich diese Optimierung wie folgt beschreiben:

Wenn eine Liste homogen ist, verwendet Python die 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änderlich 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 < für > verwendet)
• Wenn die Werte vom gleichen Typ oder von unterschiedlichen Typen sind, aber keiner ein Untertyp des anderen ist:
  • Python wird zunächst die Vergleichsfunktion des linken Operanden ausprobieren
  • Wenn dies fehlschlägt, wird die Vergleichsfunktion des rechten Operanden ausprobiert, 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.

For example, when comparing strings, Python will check if the string characters take more than one byte of memory, and float comparison will compare a pair of float's and a float and an int differently.

A more detailed explanation and diagram can be found here: Adding Data-Aware Sort Optimizations to CPython

Before this optimization was introduced, Python had to execute all this various type-specific and non-type-specific checks every time two values were compared during sorting.

Checking List Element's Types in Advance

There's no magical way to know if all the elements of a list are of the same type other than to iterate over the list and check each element.

Python does almost exactly that — checking the types of sorting keys generated by key function passed to list.sort or sorted as a parameter

Constructing a List of Keys

If a key function is provided, Python uses it to construct a list of keys, otherwise it uses the list's own values as sorting keys.

In an oversimplified manner, keys construction can be expressed as the following python code.

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

Note, that keys used internally in CPython are a C array of CPython object references, and not a Python list

Once the keys are constructed, Python checks their types.

Checking Key's Type

When checking the types of keys, Python's sorting algorithm tries to determine if all elements in the keys array are either str, int, float or tuple, or simply of the same type, with some constraints for base types.

It's worth noting that checking the types of the keys adds some extra work up front. Python does this because it usually pays off by making the actual sorting faster, especially for longer lists.

int constraints

int should not be a bignum

Practically this means that for this optimization to work, integer should be less than 2^30 - 1 (this may vary depending on the platform)

As a side note, here is a great article which explains how Python handles big integers: # How python implements super long integers?

str constraints

All characters of a string should take less than 1 byte of memory, meaning that they should be represented by integer values in the range of 0-255

In practice, this means that strings should consist only of Latin characters, spaces, and some special characters found in the ASCII table.

float constraints

There are no constraints for floats in order for this optimization to work.

tuple constraints

• Only the first element's type is checked
• This element itself should not be a tuple itself
• If all tuples share the same type for their first element, the comparison optimization is applied to them
• All other elements are compared as usual

How Can I Apply This Knowledge?

First of all, isn’t it fascinating to know?

Secondly, mentioning this knowledge could be a nice touch in a Python Developer interview.

As for actual code development, understanding this optimization can help you improve sorting performance.

Optimize by Selecting the Type of Values Wisely

According to the benchmark in the PR that introduced this optimization, sorting a list that consists only of floats rather than a list of floats with even a single integer at the end is almost twice as fast.

So when it's time to optimize, transforming list like this

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

Into list that looks like this

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

might improve performance.

Optimize by Using Keys for Lists of Objects

While Python's sorting optimization works well with built-in types, it's important to understand how it interacts with custom classes.

When sorting objects of custom classes, Python relies on the comparison methods you define, such as __lt__ (less than) or __gt__ (greater than).

However, the type-specific optimization doesn't apply to custom classes.
Python will always use the general comparison method for these objects.

Here's an example:

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

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

my_list = [MyClass(3), MyClass(1), MyClass(2)] 
sorted_list = sorted(my_list)

In this case, Python will use the __lt__ method for comparisons, but it won't benefit from the type-specific optimization. The sorting will still work correctly, but it may not be as fast as sorting built-in types.

If performance is critical when sorting custom objects, consider using a key function that returns a built-in type:

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

Afterword

Premature optimization, especially in Python, is evil.

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.

Das obige ist der detaillierte Inhalt vonWie die Vergleichsoptimierung die Python-Sortierung beschleunigt. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!