URL: https://linuxfr.org/users/guillaum/journaux/coherence-des-fonctions-de-tri Title: Cohérence des fonctions de tri Authors: Guillaum Date: 2016年11月29日T12:47:45+01:00 License: CC By-SA Tags: Score: 29 Nous allons discuter d'un point très simple, l’implémentation de la fonction `max` dans de nombreux langages. Nous allons voir que cette fonction est plus complexe qu'il n'y parait et que son implémentation différente entre de nombreux langages peut poser quelques problèmes. # Introduction Que se passe-t-il quand on calcule le minimum ou le maximum de deux éléments identiques ? Dit autrement, soit `x = max(a, b)` si `a == b`, quelle est la valeur de `x`, `a` ou `b` ? L’intérêt peut sembler limité, mais il a ses applications quand on commence à calculer des minimums / maximums en utilisant une fonction de comparaison, comme il est possible dans de nombreux langages de programmation. Dit autrement, en supposant que l'on ait une fonction `max(a, b, key)` implémentée comme ceci en python : ```python def min(a, b, key): if key(a) < key(b): return b if key(a)> key(b): return a if key(a) == key(b): return ???? # a ou b ? ``` Le choix de renvoyer `a` ou `b` peut être important, comme je vais vous le montrer dans l'étude de cas qui suit. # Petit problème Soit une liste `l` contenant `N` valeurs et des fonctions de pondération sur ces valeurs `getWeightA` et `getWeightB`. Le poids `A` ne dépend que d'une valeur alors que le poids `B` dépend aussi d'un paramètre qui change régulièrement. De nombreuses fois `P`, je veux pouvoir récupérer un élément dans la liste, celui qui a le plus grand poids `B` et en cas d'égalités, celui qui a le plus grand poids `A`. Une première solution (en python) serait : ```python for _ in range(P): param = ... def k(e): return (getWeightB(e, param), getWeightA(e)) item = max(l, key=k) ``` Cependant cette solution réalise `N * P` appels à `getWeightA` et `getWeightB`. Les appels à `getWeightA` étant indépendants de `param`, on aimerait éviter de calculer ceux-là à chaque itération. D'autant que dans mon cas, il s'agit d'une fonction de complexité importante ;) Une seconde solution, mettant en cache la valeur de poids `A` serait la suivante : ```python # calcul du cache l = [(k, getWeightA(k)) for k in l] # ... for _ in range(P): param = ... def k(e): return (getWeightB(e[0], param), e[1]) item = max(l, key=k)[0] ``` Cette solution a l'avantage de ne faire que `N` appels à `getWeightA` qu'une fois lors de l'initialisation, puis `N * P` appels à `getWeightB`. Elle est donc potentiellement plus efficace, mais consomme plus de mémoire. Je vous propose une dernière solution, qui permettra de lancer le débat et l'observation qui font l’intérêt de ce journal : ```python # transformation de la liste (*) l = list(sorted(l, key=getWeightA, reverse=True)) # ... for _ in range(P): param = ... def k(e): return getWeightB(e, param) # récuperation du max (**) item = max(l, key=k) ``` Cette solution utilise deux astuces. En premier lieu `(*)`nous trions en sens inverse la liste initiale selon le poids `A`. Grâce à la [Schwartzian transform](https://en.wikipedia.org/wiki/Schwartzian_transform) utilisée par python dans la fonction `sorted`, ce tri est réalisé en `O(N log N)` avec seulement `N` appels à `getWeightA`. Cette fonction prend un peu de mémoire pour son initialisation, mais cette mémoire sera libérée avant la boucle. La seconde astuce `(**)` apparaît plus loin, où on cherche le maximum selon le poids `B`. Cette recherche du maximum prend en compte le poids `A` de façon simple, en renvoyant le *premier* maximum selon le poids `B`. Comme la liste est déjà triée inversement selon le poids `A`, ce premier maximum selon `B` est aussi le maximum selon `A` pour toutes les valeurs équivalentes de `B`. On obtient donc un algorithme à la complexité équivalente au précédant, mais consommant moins de mémoire, si on omet l'initialisation en `O(N log N)`, on suppose que `P> log N`. J'ai souvent utilisé cette astuce dans ma vie de développeur, et hier soir, j'ai utilisé de nouveau cette astuce et je me suis planté. Pourquoi ? À cause de la supposition que la fonction `max` renvoie le *premier* maximum. Ce n'est pas (toujours) documenté / normalisé, donc c'est susceptible de changer, d’être aléatoire ou incohérent entre différent langages / librairies. C'est ce que nous allons observer. # Observation En python (CPython 3.5.2) : ```python>>> l = [("hello", 10), ("this", 10), ("is", 10), ("the", 10), ("end", 10), ("of", 10), ("the", 10), ("world", 10)]>>> key = lambda x : x[1]>>> min(l, key=key) ('hello', 10)>>> max(l, key=key) ('hello', 10) ``` Ici les fonctions `min` et `max` renvoient le minimum de la liste `l`, en utilisant le second élément de chaque tuple. Toutes ces clés sont identiques, donc le résultat est arbitraire. Ici l’implémentation renvoie le premier de la liste dans les deux cas. Des essais d’implémentation Ruby et C++ donnent le même comportement. Comparons maintenant avec Haskell (GHC 8.0.1) : ```haskell>>> import Data.List>>> import Data.Ord>>> l = [("hello", 10), ("this", 10), ("is", 10), ("the", 10), ("end", 10), ("of", 10), ("the", 10), ("world", 10)]>>> key = comparing snd>>> minimumBy key l ("hello",10)>>>> maximumBy key l ("world",10) ``` Ici on observe quelque chose de différent, parmi toutes les valeurs possibles, le minimum est la première et le maximum est la dernière. Donc l'astuce discutée plus haut n'est pas valable (directement) en Haskell, ce qui m'a valu hier quelques heures de debug. # Documentation Que disent les documentations pour l'usage de `max(a, b)` si `a == b` ? - [C++](http://en.cppreference.com/w/cpp/algorithm/max) confirme que cela renvoie `a` - [Haskell](https://www.haskell.org/onlinereport/standard-prelude.html) L'horreur à trouver, mais confirme que cela renvoie `b` - [Python](https://docs.python.org/2/library/functions.html#min) ne dit rien (l'implémentation dit `a`) - [Rust](https://doc.rust-lang.org/std/cmp/fn.max.html) confirme que cela renvoie `b` - [Ruby](http://ruby-doc.org/core-2.3.3/Enumerable.html#method-i-min) ne dit rien (l'implémentation dit `a`) On vois donc que certains langages font des choix différents. # Discussion Alors des deux comportements, lequel est le meilleur ? En toute logique, si on prend le premier élément d'une liste triée, c'est censé être la même chose que le minimum de la liste (et réciproquement pour le maximum). C'est comme cela qu'est implémenté le [[Tri par sélection]]. Haskell, Rust, confirment cela : ```haskell>>> minimumBy key l == head (sortBy key l) True>>> maximumBy key l == last (sortBy key l) True ``` Cependant Python, C++, Ruby, se "trompent" : ```python>>> min(l, key=key) == list(sorted(l, key=key))[0] True>>> max(l, key=key) == list(sorted(l, key=key))[-1] False ``` # Conclusion Les langages de programmation ont une sémantique différente en ce qui concerne le tri et le comportement de la fonction `max`. Personnellement je préfère la sémantique implémentée entre autres dans Haskell puisque c'est la seule qui garantit que certaines lois fondamentales sont conservées. Au final ce n'est pas forcement grave, mais il ne faut pas écrire d'algorithme supposant une sémantique ou une autre et il faut documenter son code quand on fait ce genre de supposition. C'est ce que je n'avais pas fait, et je me suis fait avoir. Et vous, vous feriez vous avoir ? Comment votre outil gère-t-il ce cas ?

AltStyle によって変換されたページ (->オリジナル) /