- La médiane se trouve facilement en triant, mais le coût du tri impose une limite en O(n log n) même pour le problème de sélection d’un seul élément
- quickselect explore récursivement uniquement le côté nécessaire, ce qui permet de trouver le k-ième élément ou la médiane en O(n) en moyenne
- Un pivot aléatoire fonctionne bien en pratique, mais si l’on continue à choisir de mauvais pivots, un seul élément est éliminé à chaque étape et la complexité peut se dégrader jusqu’à O(n²)
- median-of-medians choisit ensuite la médiane parmi les médianes de groupes de cinq, ce qui permet d’éliminer au moins 30 % des éléments même dans le pire des cas
- En pratique, le coût de calcul du pivot peut être élevé, si bien qu’introselect, qui combine quickselect et heapselect comme dans la bibliothèque standard C++, peut être un choix plus pragmatique
Limites de la recherche de la médiane par tri
- La manière la plus simple de calculer la médiane consiste à trier la liste puis à prendre la valeur à l’indice central
- Pour une liste de longueur impaire, on renvoie l’élément du milieu ; pour une liste de longueur paire, on renvoie la moyenne des deux éléments centraux
- La meilleure complexité temporelle possible pour un tri par comparaison est O(n log n) ; le temps d’exécution de cette méthode est donc dominé par le tri
- Le code a l’avantage d’être simple, mais il effectue plus de travail que nécessaire pour trouver une seule médiane
quickselect et son O(n) moyen
- quickselect est un algorithme récursif créé par Tony Hoare ; il permet de trouver non seulement la médiane, mais aussi n’importe quel k-ième élément d’une liste
- Son principe de base consiste à partitionner la liste autour d’un pivot, puis à continuer la recherche uniquement du côté qui contient le k-ième élément
- choisir un pivot dans la liste
- partitionner la liste entre les éléments inférieurs ou égaux au pivot et ceux strictement supérieurs au pivot
- déterminer de quel côté se trouve le k-ième élément recherché, puis appeler récursivement uniquement la sous-liste correspondante
- lorsqu’on descend dans la sous-liste de droite, ajuster la valeur de k en fonction du nombre d’éléments de gauche déjà exclus
- Dans la liste d’exemple
[9,1,0,2,3,4,6,8,7,10,5], la longueur est 11 ; on cherche donc le 6e plus petit élément, et selon le pivot choisi, on réduit progressivement l’intervalle jusqu’à renvoyer finalement 5
quickselect_median cherche un seul indice central avec quickselect si la longueur de la liste est impaire, et si elle est paire, cherche les deux indices centraux puis en fait la moyenne- Si le pivot coupe la liste presque en deux à chaque fois, la quantité de travail devient
n + n/2 + n/4 + ... = 2n, soit O(n)
Éviter le pire cas exige un bon pivot
- Le O(n) moyen de quickselect repose sur l’hypothèse que le choix du pivot est suffisamment bon
- Si l’on n’a pas de chance, par exemple en choisissant le maximum comme pivot à chaque étape, un seul élément est éliminé à chaque fois, ce qui mène à O(n²)
- Pour garantir un temps linéaire même dans le pire des cas, il faut fournir à quickselect un pivot suffisamment bon en temps linéaire
- Cet algorithme de sélection du pivot a été développé en 1973 par Blum, Floyd, Pratt, Rivest et Tarjan ; l’article correspondant est lié ici : 1973 paper
Sélection du pivot par median-of-medians
- median-of-medians est la procédure qui permet à quickselect de choisir un bon pivot
- Le déroulement de l’implémentation est le suivant
- s’il y a moins de 5 éléments, utiliser la fonction existante de médiane basée sur le tri
- découper la liste en groupes de 5
- ignorer, pour simplifier, le groupe incomplet final s’il contient moins de 5 éléments
- trier chaque groupe et collecter la médiane d’indice 2
- rechercher ensuite la médiane de cette liste de médianes et la renvoyer comme pivot
- Comme chaque groupe a une taille fixe de 5, le tri à l’intérieur d’un groupe est considéré comme un coût constant, ce qui donne au total un travail en O(n)
- L’appel récursif qui cherche la médiane des médianes fait partie de l’analyse comme un sous-problème de taille
n/5
Pourquoi au moins 30 % des éléments peuvent être éliminés
- Si l’on trie les groupes de 5 et qu’on les dispose en colonnes, puis qu’on trie leurs médianes pour choisir la médiane des médianes, on peut analyser la qualité du pivot
- Même dans le pire cas, où le pivot est aussi décalé que possible vers l’avant, certains quadrants garantissent des éléments plus petits ou plus grands que le pivot
- En prenant 3 éléments dans chaque colonne et la moitié des colonnes, on peut éliminer au moins
3/5 * 1/2 * n = 3/10 n éléments
- Taux d’élimination garanti : {p:30}
- Le temps d’exécution total s’exprime par la récurrence suivante
T(n) = n + T(n/5) + T(7n/10)
- Ici,
n correspond au travail de partitionnement, T(n/5) au calcul de median-of-medians, et T(7n/10) à l’exploration récursive de quickselect
- Comme cette récurrence contient deux termes récursifs, on ne peut pas appliquer directement un théorème maître simple, et un raisonnement par induction est la méthode de preuve la plus intuitive
Résultat de la combinaison : trouver la médiane en temps linéaire
- quickselect peut trouver la médiane en temps linéaire si on lui fournit un pivot suffisamment bon
- median-of-medians peut choisir ce bon pivot en O(n) pour quickselect
- En combinant les deux algorithmes, on obtient un algorithme capable de trouver la médiane ou le n-ième élément d’une liste en temps linéaire
Choix à faire dans une implémentation réelle
- En pratique, choisir un pivot aléatoire est presque toujours suffisant
- median-of-medians est lui aussi linéaire, mais dans la réalité il peut être lent à cause du coût de calcul du pivot
- La bibliothèque standard C++ utilise introselect, qui combine heapselect et quickselect et offre une borne supérieure en O(n log n)
- introselect commence généralement par un algorithme souvent rapide mais à mauvaise borne supérieure, puis bascule vers un algorithme plus lent mais à meilleure borne lorsqu’il ne parvient pas à choisir des pivots efficaces
- Dans la comparaison du nombre d’éléments examinés par la fonction quickselect, le pivot déterministe a presque toujours considéré moins d’éléments que le pivot aléatoire, mais cette comparaison n’inclut pas le coût de calcul de median-of-medians
- Un new paper publié en 2017 présente une approche qui rend la méthode median-of-medians compétitive face à d’autres algorithmes de sélection
1 commentaires
Commentaires sur Hacker News
Il y a environ 4 ans, j’ai comparé plusieurs algorithmes de médiane, et l’article est devenu bien plus long que prévu :)
https://danlark.org/2020/11/11/miniselect-practical-and-generic-selection-algorithms/
Il y a 10 à 15 ans, je devais régulièrement trouver la médiane de milliards de valeurs parsées depuis des entrées de journal de plusieurs kilo-octets. À l’époque, on utilisait MapReduce pour les traitements à grande échelle, et avec ce volume de données il fallait non seulement du temps linéaire, mais si possible une approche en une seule passe, distribuée sur plusieurs machines.
Le fait de connaître la précision et la plage des données aidait. Les valeurs étaient des durées en millisecondes entières, donc non négatives, et on savait aussi que le 90e percentile était très nettement inférieur à 1 seconde.
En général, trouver une médiane demande un travail proche du tri, mais dans ces conditions un tri par compartiments devient possible. Il suffit de construire un dictionnaire — autrement dit un histogramme — avec pour clé la durée en millisecondes entières et pour valeur le nombre d’occurrences.
Comme on ne connaissait pas la durée maximale, pour éviter que la taille du dictionnaire n’explose, toutes les valeurs au-dessus de 999 ms étaient placées dans le compartiment 999 ms ; on était donc limité à environ 2000 entiers au total, entre les clés 0 à 999 et leurs valeurs. C’est là que cela différait d’un tri par compartiments classique ; même distribué avec MapReduce, c’était très facile à traiter en une seule passe, puis il suffisait d’extraire la médiane de l’histogramme.
Le nombre 10 000 est arbitraire ici, mais on peut calculer statistiquement le nombre d’échantillons nécessaires pour le niveau de confiance voulu, et il ne me semble pas que ce soit énorme.
Sur certains systèmes avec lesquels j’ai travaillé, Prometheus semblait appliquer une limite d’environ 10 secondes aux latences. Donc les requêtes dépassant cette limite étaient toutes comptées comme 10 secondes, même si elles pouvaient en réalité durer plus longtemps. Intéressant.
Il y a eu en 2017 un nouvel article qui rendait l’approche median-of-medians compétitive avec d’autres algorithmes de sélection, et le post-scriptum indique que l’auteur de l’article, Andrei Alexandrescu, l’a signalé.
Il avait aussi fait une présentation sur son algorithme en 2016. C’est quelqu’un de passionnant à écouter, je recommande vivement.
There's Treasure Everywhere - Andrei Alexandrescu
https://www.youtube.com/watch?v=fd1_Miy1Clg
Si vous travaillez avec du logiciel, je recommande d’écouter et de lire tous les articles et présentations d’Andrei que vous pouvez trouver. Cette présentation aussi est un vrai trésor.
En licence, j’ai appris l’algorithme median-of-medians quickselect, et il m’avait vraiment marqué. Je l’ai implémenté moi-même, mais il était atrocement lent. Son temps d’exécution croissait bien linéairement, mais pour que cela ait un intérêt, il fallait au moins des dizaines de milliards d’éléments dans la liste.
En en parlant avec un ami doctorant, il m’a dit quelque chose comme : « Oui, c’est lent, mais l’important est que cela prouve qu’on peut effectuer une sélection dans une liste non triée en temps O(n). À une époque, on ne savait même pas si c’était possible ; maintenant qu’on sait que ça l’est, il peut exister des algorithmes linéaires plus rapides. »
C’était une leçon à la fois si simple et si profonde que j’ai presque candidaté en master/doctorat. Je ne sais pas si cet ami se souvient de cette conversation, mais pour moi, ça a été un moment charnière dans ma formation.
On pourrait aussi se dire : « Puisque je sais déjà qu’un certain algorithme existe, il pourrait aussi en exister un plus rapide. » Pourquoi l’existence d’un algorithme en O(n) serait-elle un signal plus fort que l’existence d’un algorithme en O(n log n) ?
Il me semble que le facteur constant de cet algorithme était autour de 22, même si c’était peut-être un algorithme apparenté.
L’un des aspects amusants de l’algorithme median-of-medians, c’est que la liste des auteurs est carrément all-star
Manuel Blum — prix Turing 1995
Robert Floyd — prix Turing 1978
Ron Rivest — prix Turing 2002
Bob Tarjan — prix Turing 1986 et premier lauréat du prix Nevanlinna en 1982
Vaughan Pratt — le seul de la liste à ne pas avoir reçu le prix Turing, mais professeur émérite à Stanford, il a dirigé le projet SUN avant qu’il ne devienne Sun Microsystems, a joué un rôle important aux débuts de Sun comme directeur de la recherche et concepteur du logo de Sun, et a laissé plein de choses chouettes, comme les certificats de primalité de Pratt
Quatre prix Turing distincts, plus la SPARCstation : cet article a tout
La liste des auteurs est vraiment impressionnante
Le « P » de l’algorithme KMP, c’est aussi Pratt
return l[len(l) / 2]Je ne suis pas spécialiste de Python, mais l’opérateur
/en Python ne renvoie-t-il pas un flottant ? Pourquoi ne pas utiliser la division entière//au lieu d’utiliser un flottant comme index de tableau ?Ce n’est peut-être pas un problème sauf pour de très grands tableaux, mais ça sent quand même assez fort le code smell. Si l’auteur débute en Python et ne savait pas que les deux opérateurs existaient séparément, passe encore, mais l’article contient aussi du code encore plus étrange où une branche utilise la division entière et l’autre la division flottante
def quickselect_median(l, pivot_fn=random.choice):if len(l) % 2 == 1:return quickselect(l, len(l) // 2, pivot_fn)else:return 0.5 * (quickselect(l, len(l) / 2 - 1, pivot_fn) +quickselect(l, len(l) / 2, pivot_fn))Il y a déjà 50 commentaires et personne ne semble l’avoir vu, ce qui ne fait que renforcer mes préjugés existants sur la qualité moyenne du code Python
Indexer un tableau avec un flottant devrait lever une exception, à mon avis
L’auteur a choisi un vrai langage de programmation qui ressemble à du pseudo-code, plutôt que du pseudo-code, et je pense que, pour l’explication, le code s’exécute probablement correctement
J’ai vraiment pris plaisir à lire l’article original, mais la partie disant que « si l’on choisit le plus grand élément comme pivot à chaque étape, on peut tomber en O(n²) au lieu de O(n) » m’a gêné
Si l’on craint une entrée adversariale, on peut d’abord mélanger les données en O(n) pour empêcher que cela soit forcé. Si les données sont trop volumineuses pour être mélangées, il suffit de le faire une seule fois quand le bucket est devenu assez petit pour être mélangé
Une fois le mélange effectué, les probabilités garantissent que le pire cas ne se produit pratiquement pas. Si quelqu’un dit que c’est « techniquement » possible, je répondrais que, « techniquement », un attaquant peut aussi deviner tous les bits d’une clé privée de 256 bits
Notre monde est construit sur les probabilités. Toutes les clés privées sont protégées par l’impossibilité mathématique pratique que quelqu’un les devine exactement
D’après ce que j’ai lu, quickselect après mélange est O(n) en pratique
Malgré tout, si l’on peut faire confiance à l’aléatoire, la probabilité d’un temps d’exécution supérieur à O(n) est très faible
Floyd-Rivest y parvient aussi. Si je me souviens bien, c’est un peu plus efficace
Mais je n’ai jamais réussi à comprendre son fonctionnement
https://en.m.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm
Quand on sélectionne le n-ième élément, si n est très petit ou très grand, median-of-medians n’est pas forcément le meilleur choix
À la place, on peut utiliser un pivot biaisé comme dans [1], ou une approche que j’appelle « le j-ième parmi k ». Floyd-Rivest peut aussi accélérer les choses
J’ai un projet perso qui atteint un débit de 1,2 à 2,0 fois supérieur à celui d’un quickselect bien implémenté : https://github.com/koskinev/turboselect
Je serais intéressé par des ressources sur des algorithmes de sélection en place rapides et généralistes
[1] https://doi.org/10.4230/LIPIcs.SEA.2017.24
On peut aussi utiliser des algorithmes de streaming capables d’estimer des quantiles arbitraires sans stocker toutes les données en mémoire
Peut-on accepter un calcul approché ? Quelles hypothèses faut-il faire sur les données pour fixer une borne d’erreur ? Comment vérifier que ces hypothèses restent valables ?
Personnellement, tant que je ne suis pas dans une situation où je dois vraiment envisager une approximation de la médiane en streaming, je pense que je pencherais pour l’algorithme quickselect présenté dans l’article original