Journal Cohérence des fonctions de tri

Posté par Guillaum (site web personnel) le 29 novembre 2016 à 12:47. Licence CC By‑SA.

Étiquettes : aucune

nov.

2016

Sommaire

Introduction
Petit problème
Observation
Documentation
Discussion
Conclusion

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 :

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 :

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 :

# 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 :

# 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 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) :

>>> 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) :

>>> 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++ confirme que cela renvoie a
Haskell L'horreur à trouver, mais confirme que cela renvoie b
Python ne dit rien (l'implémentation dit a)
Rust confirme que cela renvoie b
Ruby 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 :

>>> minimumBy key l == head (sortBy key l)
True
>>> maximumBy key l == last (sortBy key l)
True

Cependant Python, C++, Ruby, se "trompent" :

>>> 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 ?

# en c++ tu as des subtilité

Posté par fearan le 29 novembre 2016 à 13:17. Évalué à 6.

stable_sort te garanti de garder le même ordre si deux éléments sont identique :)

http://en.cppreference.com/w/cpp/algorithm/stable_sort

Il ne faut pas décorner les boeufs avant d'avoir semé le vent
- [^] # Re: en c++ tu as des subtilité
  
  Posté par Guillaum (site web personnel) le 29 novembre 2016 à 13:34. Évalué à 4.
  
  En effet, le tri doit être stable pour que l’égalité max(l) = last(sort(l)) soit vérifiée, mais ce n'est pas la seule condition, il faut aussi que max a b key == b si key a == key b.
  - [^] # Re: en c++ tu as des subtilité
    
    Posté par fearan le 29 novembre 2016 à 15:35. Évalué à 5.
    
    le soucis c'est que tu prends quand même un postulat de départ qui n'a pas de base mathématique, que le min ou le max te renvoient le premier ou le dernier élément d'une liste triée n'est vrai que lorsque tu as un ordre absolu. Que chaque langage ait sont propre comportement me semble logique.
    
    Si tu souhaite jouer avec il faut utiliser le rbegin() pour ton max, et begin() pour ton min.
    
    Il ne faut pas décorner les boeufs avant d'avoir semé le vent
    - [^] # Re: en c++ tu as des subtilité
      
      Posté par Guillaum (site web personnel) le 29 novembre 2016 à 16:15. Évalué à 3.
      
      le soucis c'est que tu prends quand même un postulat de départ qui n'a pas de base mathématique, que le min ou le max te renvoient le premier ou le dernier élément d'une liste triée n'est vrai que lorsque tu as un ordre absolu. Que chaque langage ait sont propre comportement me semble logique.
      
      L'ordre absolu c'est dire que quel que soit x et y dans un ensemble, on peut montrer que x <= y ou y <= x, bref on peut mettre une relation d'ordre entre deux éléments de ton ensemble, c'est le cas de mon ensemble de tuple (string, int) que j'ai présenté. La particularité de cet ensemble c'est que on peut distinguer les éléments qui sont égaux. Ainsi, une permutation de deux éléments égaux ne change rien au niveau de la relation d'ordre mais change le résultat. Et c'est là que on s'attend à un tri stable pour ne pas changer ce résultat.
      
      Mais bon, au final, le but de mon article écrit ce matin dans un moment de procrastination^W compilation était de discuter comment un petit détail aussi insignifiant que l’implémentation d'une fonction max peut totalement bouleverser un algorithme.
      - [^] # Re: en c++ tu as des subtilité
        
        Posté par fearan le 29 novembre 2016 à 16:38. Évalué à 2.
        
        pardon j'ai écrit une boulette, je pensais ordre strict, c'est ça de ne plus faire de math depuis des années, on confond les termes.
        
        Bref dans le cas d'une liste dont tous les éléments sont égaux, que min ou max me renvoient un élément aléatoire de la liste ne me choquerait pas; ça pourrait même en renvoyer un différent à chaque appel que ça ne me choquerai pas non plus; d'ailleurs avec la parallélisation des algorithmes de la stl faudra bien vérifier à ce que dit la spec (l'implémentation c'est pas suffisant) :)
        
        Il ne faut pas décorner les boeufs avant d'avoir semé le vent
        
        [^] # Re: en c++ tu as des subtilité
        
        Posté par Guillaum (site web personnel) le 29 novembre 2016 à 17:07. Évalué à 2.
        
        Bref dans le cas d'une liste dont tous les éléments sont égaux, que min ou max me renvoient un élément aléatoire de la liste ne me choquerait pas;
        
        Moi non plus, mais c'est un peu tout le point de l'étude de cas présentée, on peut écrire cet algorithme de cette façon que si on a des certitudes sur le comportement de la fonction max. Sinon il faut l'écrire autrement.
      - [^] # Re: en c++ tu as des subtilité
        
        Posté par ɹǝıʌıʃO le 29 novembre 2016 à 16:39. Évalué à 3. Dernière modification le 29 novembre 2016 à 16:40.
        
        Vous n’auriez pas quelques précisions là-dessus ? Je ne connais pas l’expression « ordre absolu » et, semble-t-il, Google non plus. Ce que tu décris correspond à ce que j’ai appris sous le nom d’ordre « total », et ~~je ne comprends pas ce que dit fearan ci-dessus~~ il a répondu le temps que j’écrive ce commentaire.
        
        [^] # Re: en c++ tu as des subtilité
        
        Posté par Guillaum (site web personnel) le 29 novembre 2016 à 17:04. Évalué à 2.
        
        On s'est tous les deux emmêler les pinceaux ;)
        
        [^] # Re: en c++ tu as des subtilité
        
        Posté par fearan le 29 novembre 2016 à 17:13. Évalué à 2.
        
        Tu as parfaitement raison, c'est moi qui n'ai pas la bonne mémoire Relation_d'ordre, mais il a compris de quoi je parlais :).
        
        ensuite on va jouer avec les subtilité ordre strict (relation infériorité strict), la on a des mauvaises blague parce que les poids sont identique mais pas les valeurs, ou dit plus précisément sa relation d'ordre est mal définie :)
        
        sa relation d'ordre est en fait le couple (poids, position dans la liste initiale); un fois cette définition faite, les fonctions min/max fonctionnent comme il le souhaite quel que soit le langage ;)
        
        Il ne faut pas décorner les boeufs avant d'avoir semé le vent
      - [^] # Mode pinaillage :-P
        
        Posté par kantien le 29 novembre 2016 à 19:23. Évalué à 7. Dernière modification le 29 novembre 2016 à 19:25.
        
        Pour être plus précis, au sens strict, ce que tu as défini sur tes structures de données n'est pas une relation d'ordre totale (on ne dit pas absolue, mais totale pour exprimer que deux éléments quelconques sont nécessairement en relation, ce qui a bien été rappelé dans un autre commentaire), mais une relation de préordre. La différence est importante, et ça a de l'impact pour ton code et tes exemples, une relation d'ordre est antisymétrique : si x <= y et y <= x alors x = y. Ce qui n'est pas le cas de ta relation : elle est symétrique (x <= x pout tout x) et transitive (si x <= y et y <= z alors x <= z) ce qui en fait une relation de préordre (symétrie et transitivité constitue la définition d'un préordre) mais non une relation d'ordre.
        
        Ensuite quand on a une relation de préordre sur une structure, on peut définir un relation d'équivalence par x ~ y si et seulement si x <= y et y <= x. Puis à partir de ces deux relations, on définit naturellement une relation d'ordre sur les classes d'équivalence. Ton problème devient alors le suivant : quel représentant de chaque classe doivent renvoyer les fonctions min et max ? Ici il n'y a pas de réponse unique, bien que la solution choisie par Haskell ou Rust soit la plus « sensée » si l'on cherche à garantir certains invariants lorsque l'on compose des opérations faisant usage de ces différentes relations.
        
        Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
        
        [^] # Re: Mode pinaillage :-P
        
        Posté par Aluminium95 le 29 novembre 2016 à 22:00. Évalué à 4.
        
        En effet, j'ai mis un bout de temps avant d'abandonner l'idée de comprendre la première phrase et continuer de lire l'article pour voir où l'auteur voulait aller :
        
        Dit autrement, soit x = max(a, b) si a == b, quelle est la valeur de x, a ou b ?
        
        Par construction, si a == b alors on ne peut pas les différencier … du coup … on retourne a ou b c'est pareil.
        J'ai fini par comprendre que l'égalité a == b ne signifiait pas l'égalité (ni au sens faible de l'égalité physique de pointeurs, ni au sens fort de l'égalité structurelle). Le problème venait donc bien du fait que la relation d'ordre n'en était pas une !
        
        Notons que si on définit une nouvelle relation d'égalité ~ sur les structures, et que l'ordre <= est une relation d'ordre relativement à cette relation d'égalité, et bien le comportement de max et min redevient totalement déterminé : si on a x ~ y alors c'est que dans notre programme, on a voulu confondre les deux valeurs, et donc il n'y a pas de raison de choisir un représentant plutôt qu'un autre.
        
        Ma conclusion c'est que raisonner sur la sémantique d'une fonction définie sur un ordre (total) en utilisant seulement un ordre (partiel) et se servir de l'implémentation pour la justifier c'est un peu foireux. D'ailleurs, en haskell la documentation précise clairement que Ord représente un ordre total:
        
        The Ord class is used for totally ordered datatypes.
        
        Et la signature de l'interface demande clairement que le type possède une certaine notion d'égalité (ce qui n'est pas nécessaire pour un préordre) :
        
        class Eq a => Ord a where
        
        Néanmoins, il est intéressant de noter que ces conditions ne sont pas vérifiées statiquement, et on peut en effet écrire
        
        sortBy (compare `on` snd) liste
        
        [^] # Re: Mode pinaillage :-P
        
        Posté par Guillaum (site web personnel) le 29 novembre 2016 à 23:17. Évalué à 6.
        
        En fait je pense que j'ai fais une erreur dans mon énoncé, mais comme Luke, je pense qu'il y a encore du bon quelque part ;)
        
        J'ai défini une relation d'ordre entre mes éléments tel que compare (_, a) (_, a') = compare a a' qui implique autant <= que ==. J'ai donc une relation d'ordre totale définie en se servant du second élément du tuple.
        
        Mais dans mon énoncé, et je me sert à tort de l'égalité entre tuple. En effet, quand j'écris :
        
        >>> min(l, key=key) == list(sorted(l, key=key))[0] True >>> max(l, key=key) == list(sorted(l, key=key))[-1] False
        
        je triche, car j'utilise le == défini sur les tuples et non pas le == de ma relation d'ordre. Si j'avais utilisé le bon == j'aurais obtenu True.
        
        Et c'est là que je me suis planté.
        
        Maintenant, je pense que tout cela n'invalide en rien ma conclusion, qui est qu'il faut faire attention avec certaines supposition et que on peut se planter facilement. Mais j'aurais pu l'écrire en moins de caractère, c'est vrai ;)
        
        [^] # Re: Mode pinaillage :-P
        
        Posté par kantien le 29 novembre 2016 à 23:36. Évalué à 3.
        
        Maintenant, je pense que tout cela n'invalide en rien ma conclusion, qui est qu'il faut faire attention avec certaines supposition et que on peut se planter facilement.
        
        En Coq t'aurais pas eu ce problème ! :-P Son système de type, qui est le plus riche que l'on puisse conférer au lambda-calcul, n'autorise pas de telles ambiguïtés.
        
        Sinon pour gérer le maximum, et encoder des preuves sur ce dernier via des termes, avec les GADT il y a un bon exemple dans cette leçon sur les GADT dans le cours de programmation fonctionnelle avancée de Jeremy Yallop et Leo White. Cela rejoint ta question sur les GADT et type families dans mon journal sur la méthode tagless-final.
        
        Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

# R

Posté par gipoisson le 30 novembre 2016 à 02:21. Évalué à 2.

Et vous, vous feriez vous avoir ? Comment votre outil gère-t-il ce cas ?

Ici, c'est du R. La fonction de base qui gère pareils cas est nommée rank. Sa documentation, help(rank), dit partiellement ceci :

Description:

 Returns the sample ranks of the values in a vector.  Ties (i.e.,
 equal values) and missing values can be handled in several ways.

Usage:

 rank(x, na.last = TRUE,
      ties.method = c("average", "first", "last", "random", "max", "min"))

Arguments:

   x: a numeric, complex, character or logical vector.

   na.last: for controlling the treatment of ‘NA’s.  If ‘TRUE’, missing
      values in the data are put last; if ‘FALSE’, they are put
      first; if ‘NA’, they are removed; if ‘"keep"’ they are kept
      with rank ‘NA’.

   ties.method: a character string specifying how ties are treated, see
      ‘Details’; can be abbreviated.

Details:

 If all components are different (and no ‘NA’s), the ranks are well
 defined, with values in ‘seq_along(x)’.  With some values equal
 (called ‘ties’), the argument ‘ties.method’ determines the result
 at the corresponding indices.  The ‘"first"’ method results in a
 permutation with increasing values at each index set of ties, and
 analogously ‘"last"’ with decreasing values.  The ‘"random"’
 method puts these in random order whereas the default,
 ‘"average"’, replaces them by their mean, and ‘"max"’ and ‘"min"’
 replaces them by their maximum and minimum respectively, the
 latter being the typical sports ranking.

Traduction à l'arrache :

Synopsis:

 Retourne les rangs des éléments contenus dans la liste indiquée. Propose
 plusieurs possibilités de traitement des éléments ayant des valeurs égales
 ou/et manquantes.

Signature:

 rank(x, na.last = TRUE,
      ties.method = c("average", "first", "last", "random", "max", "min"))

Arguments:

   …
   ties.method: une chaîne de charactère indiquant comment ranger les éléments de
 même(s) valeur(s). Voir la section « détails » ici-bas.

Détails:

 Les rangs seront bien définis si toutes les valeurs sont différentes et
 s'il n y a pas de valeurs manquantes : ce sera le résultat d'une
 permutation de seq_along(x). S'il y a certains éléments partageant des
 valeurs égales (appelées « égalités » dans la suite), leurs rangs
 dépendront de l'argument « ties.method » qui prend les valeurs suivantes :
 "first", les rangs des égalités sont pris suivant les indices croissants
 selon lesquels elles apparaissent dans la liste en entrée ; "last" procède
 comme "first", cette fois-ci en prenant les indices décroissants ;
 "random" range aléatoirement les égalités ; "average" est la méthode
 utilisée par défaut et moyenne les rangs des égalités ; "max" considère le
 rang de la dernière égalité à apparaître dans la liste ; "min" en
 considère celui de la première …

Talk is cheap, show me the code.

print(R.version.string)

set.seed(39)

eg <- new.env(parent = emptyenv())
eg$b <- c(21L, 58L, 21L, 0L)
eg$critères <- c("first", "last", "random", "average", "max", "min")

print(eg$b)
for (i in eg$critères) cat(i, "\t: ", rank(b, ties.method = i), "\n")

Les sorties ressemblent à quelque chose du genre
[1] "R version 3.3.2 (2016-10-31)" [1] 21 58 21 0 first : 2 4 3 1 last : 3 4 2 1 random : 3 4 2 1 average : 2.5 4 2.5 1 max : 3 4 3 1 min : 2 4 2 1

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.