Comment l'optimisation des comparaisons accélère le tri Python

Dans ce texte les termes Python et CPython, qui est l'implémentation de référence du langage, sont utilisés de manière interchangeable. Cet article concerne spécifiquement CPython et ne concerne aucune autre implémentation de Python.

Python est un langage magnifique qui permet à un programmeur d'exprimer ses idées en termes simples, laissant la complexité de la mise en œuvre réelle dans les coulisses.

L'une des choses qu'il résume est le tri.

Vous pouvez facilement trouver la réponse à la question « comment le tri est implémenté en Python ? » ce qui répond presque toujours à une autre question : « Quel algorithme de tri Python utilise-t-il ?

Cependant, cela laisse souvent derrière lui quelques détails d'implémentation intéressants.

Il y a un détail d'implémentation qui, à mon avis, n'est pas suffisamment discuté, même s'il a été introduit il y a plus de sept ans dans python 3.7 :

sorted() et list.sort() ont été optimisés pour les cas courants afin d'être jusqu'à 40 à 75 % plus rapides. (Contribution d'Elliot Gorokhovsky dans bpo-28685.)

Mais avant de commencer...

Brève réintroduction au tri en Python

Lorsque vous devez trier une liste en python, vous avez deux options :

• Une méthode de liste : list.sort(*, key=None, reverse=False), qui trie la liste donnée sur place
• Une fonction intégrée : sorted(iterable, /, *, key=None, reverse= False), qui renvoie une liste triée sans modifier son argument

Si vous devez trier un autre itérable intégré, vous ne pouvez utiliser que sorted quel que soit le type d'itérable ou de générateur passé en paramètre.

sorted renvoie toujours une liste car il utilise list.sort en interne.

Voici un équivalent approximatif de l'implémentation C triée de CPython réécrite en python pur :

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

Oui, c'est aussi simple que cela.

Comment Python accélère le tri

Comme le dit la documentation interne de Python pour le tri :

Il est parfois possible de remplacer des comparaisons spécifiques à un type plus rapides par le PyObject_RichCompareBool plus lent et générique

Et en bref cette optimisation peut être décrite ainsi :

Lorsqu'une liste est homogène, Python utilise une fonction de comparaison spécifique au type

Qu'est-ce qu'une liste homogène ?

Une liste homogène est une liste qui contient des éléments d'un seul type.

Par exemple :

homogeneous = [1, 2, 3, 4]

Par contre, ce n'est pas une liste homogène :

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

Fait intéressant, le tutoriel officiel de Python indique :

Les listes sont mutables et leurs éléments sont généralement homogènes et sont accessibles en itérant sur la liste

Une remarque sur les tuples

Ce même tutoriel indique :

Les tuples sont immuables et contiennent généralement une séquence hétérogène d'éléments

Donc, si jamais vous vous demandez quand utiliser un tuple ou une liste, voici une règle générale :
si les éléments sont du même type, utilisez une liste, sinon utilisez un tuple

Attendez, et qu'en est-il des tableaux ?

Python implémente un objet conteneur de tableau homogène pour les valeurs numériques.

Cependant, depuis Python 3.12, les tableaux n'implémentent pas leur propre méthode de tri.

La seule façon de les trier est d'utiliser sorted, qui crée en interne une liste à partir du tableau, effaçant ainsi toute information relative au type.

Pourquoi l'utilisation de la fonction de comparaison spécifique au type est-elle utile ?

Les comparaisons en Python sont coûteuses, car Python effectue diverses vérifications avant d'effectuer une comparaison réelle.

Voici une explication simplifiée de ce qui se passe sous le capot lorsque vous comparez deux valeurs en python :

• Python vérifie que les valeurs transmises à la fonction de comparaison ne sont pas NULL
• Si les valeurs sont de types différents, mais que l'opérande droit est un sous-type de celui de gauche, Python utilise la fonction de comparaison de l'opérande droit, mais inversée (par exemple, il utilisera < pour >)
• Si les valeurs sont du même type, ou de types différents mais qu'aucune des deux n'est un sous-type de l'autre :
  • Python va d'abord essayer la fonction de comparaison de l'opérande gauche
  • Si cela échoue, il essaiera la fonction de comparaison de l'opérande droit, mais inversée.
  • Si cela échoue également et que la comparaison concerne l'égalité ou l'inégalité, elle renverra une comparaison d'identité (Vrai pour les valeurs qui font référence au même objet en mémoire)
  • Sinon, cela génère TypeError

En plus de cela, les fonctions de comparaison propres à chaque type implémentent des vérifications supplémentaires.

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.

Vous ne devez pas concevoir l'intégralité de votre application autour d'optimisations spécifiques dans CPython, mais il est bon d'être conscient de ces optimisations : bien connaître vos outils est un moyen de devenir un développeur plus compétent.

Être attentif à de telles optimisations vous permet d'en profiter lorsque la situation l'exige, notamment lorsque les performances deviennent critiques :

Considérez un scénario dans lequel votre tri est basé sur des horodatages : l'utilisation d'une liste homogène d'entiers (horodatages Unix) au lieu d'objets datetime pourrait exploiter efficacement cette optimisation.

Cependant, il est crucial de se rappeler que la lisibilité et la maintenabilité du code doivent primer sur de telles optimisations.

Bien qu'il soit important de connaître ces détails de bas niveau, il est tout aussi important d'apprécier les abstractions de haut niveau de Python qui en font un langage si productif.

Python est un langage étonnant, et explorer ses profondeurs peut vous aider à mieux le comprendre et à devenir un meilleur programmeur Python.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!