Algorithme de sélection - Selection algorithm

En informatique , un algorithme de sélection est un algorithme pour trouver le k ème plus petit nombre dans une liste ou un tableau ; un tel nombre est appelé k e statistique d'ordre . Cela inclut les cas de recherche des éléments minimum , maximum et médian . Il existe des algorithmes de sélection en O( n )-temps (temps linéaire dans le pire des cas), et des performances sublinéaires sont possibles pour les données structurées ; à l'extrême, O(1) pour un tableau de données triées. La sélection est un sous-problème de problèmes plus complexes comme le voisin le plus proche et les problèmes de chemin le plus court . De nombreux algorithmes de sélection sont dérivés en généralisant un algorithme de tri , et inversement certains algorithmes de tri peuvent être dérivés en tant qu'application répétée de la sélection.

Le cas le plus simple d'un algorithme de sélection consiste à trouver l'élément minimum (ou maximum) en itérant dans la liste, en gardant une trace du minimum en cours - le minimum jusqu'à présent - (ou maximum) et peut être considéré comme lié au tri de sélection . Inversement, le cas le plus difficile d'un algorithme de sélection est de trouver la médiane. En fait, un algorithme de sélection médiane spécialisé peut être utilisé pour construire un algorithme de sélection général, comme dans la médiane des médianes . L'algorithme de sélection le plus connu est Quickselect , qui est lié à Quicksort ; comme Quicksort, il a des performances moyennes (asymptotiquement) optimales, mais des performances médiocres dans le pire des cas, bien qu'il puisse également être modifié pour donner des performances optimales dans le pire des cas.

Sélection par tri

En triant la liste ou le tableau puis en sélectionnant l'élément souhaité, la sélection peut être réduite au tri . Cette méthode est inefficace pour sélectionner un seul élément, mais est efficace lorsque de nombreuses sélections doivent être effectuées à partir d'un tableau, auquel cas un seul tri initial et coûteux est nécessaire, suivi de nombreuses opérations de sélection bon marché - O (1) pour un tableau , bien que la sélection soit O( n ) dans une liste chaînée, même si elle est triée, en raison du manque d' accès aléatoire . En général, le tri nécessite un temps O( n log n ), où n est la longueur de la liste, bien qu'une limite inférieure soit possible avec des algorithmes de tri non comparatifs comme le tri par base et le tri par comptage .

Plutôt que de trier toute la liste ou le tableau, on peut plutôt utiliser un tri partiel pour sélectionner les k éléments les plus petits ou les k plus grands. Le k ème plus petit (resp., k ème élément le plus grand) est alors le plus grand (resp., élément le plus petit) de la liste partiellement triée - cela prend alors O (1) pour accéder dans un tableau et O( k ) pour accéder dans une liste.

Tri partiel non ordonné

Si le tri partiel est assoupli pour que les k éléments les plus petits soient renvoyés, mais pas dans l'ordre, le facteur de O( k log k ) peut être éliminé. Une sélection maximale supplémentaire (en prenant un temps O( k )) est requise, mais puisque , cela donne toujours une complexité asymptotique de O( n ). En fait, les algorithmes de sélection basés sur des partitions produisent à la fois le k ème élément le plus petit lui-même et les k éléments les plus petits (avec d'autres éléments non dans l'ordre). Cela peut être fait en un temps O( n ) - complexité moyenne de Quickselect et complexité dans le pire des cas des algorithmes de sélection raffinés basés sur des partitions. ${\displaystyle k\leq n}$

Inversement, étant donné un algorithme de sélection, on peut facilement obtenir un tri partiel non ordonné ( k plus petits éléments, pas dans l'ordre) en O( n ) temps en itérant dans la liste et en enregistrant tous les éléments inférieurs au k ème élément. S'il en résulte moins de k  − 1 éléments, tous les éléments restants sont égaux au k ième élément. Il faut prendre soin, en raison de la possibilité de l' égalité des éléments: il ne faut pas inclure tous les éléments moins ou égal à la k e élément, comme éléments supérieurs à la k ième élément peut aussi être égal.

Ainsi, le tri partiel non ordonné (les k éléments les plus bas , mais non ordonnés) et la sélection du k ème élément sont des problèmes très similaires. Non seulement ils ont la même complexité asymptotique, O( n ), mais une solution à l'un peut être convertie en solution à l'autre par un algorithme simple (trouver un maximum de k éléments, ou filtrer les éléments d'une liste en dessous d'un coupure de la valeur du k ème élément).

Tri par sélection partielle

Un exemple simple de sélection par tri partiel consiste à utiliser le tri par sélection partielle .

L'algorithme de temps linéaire évident pour trouver le minimum (resp. maximum) - en itérant sur la liste et en gardant une trace de l'élément minimum (resp. maximum) jusqu'à présent - peut être considéré comme un tri par sélection partielle qui sélectionne le 1 plus petit élément. Cependant, de nombreux autres tris partiels se réduisent également à cet algorithme pour le cas k =1, comme un tri par tas partiel.

Plus généralement, un tri par sélection partielle donne un algorithme de sélection simple qui prend un temps O( kn ). Ceci est asymptotiquement inefficace, mais peut être suffisamment efficace si k est petit et est facile à mettre en œuvre. Concrètement, nous trouvons simplement la valeur minimale et la déplaçons au début, en répétant sur la liste restante jusqu'à ce que nous ayons accumulé k éléments, puis retournons le k ème élément. Voici un algorithme basé sur le tri par sélection partielle :

function select(list[1..n], k)
    for i from 1 to k
        minIndex = i
        minValue = list[i]
        for j from i+1 to n do
            if list[j] < minValue then
                minIndex = j
                minValue = list[j]
        swap list[i] and list[minIndex]
    return list[k]

Sélection basée sur les partitions

Les performances linéaires peuvent être obtenues par un algorithme de sélection basé sur les partitions, le plus fondamentalement Quickselect . Quickselect est une variante de Quicksort - dans les deux cas, on choisit un pivot puis on partitionne les données par celui-ci, mais alors que Quicksort récurse des deux côtés de la partition, Quickselect ne récurse que d'un côté, à savoir le côté sur lequel se trouve le k ème élément souhaité. . Comme avec Quicksort, cela a des performances moyennes optimales, dans ce cas linéaires, mais des performances médiocres dans le pire des cas, dans ce cas quadratiques. Cela se produit par exemple en prenant le premier élément comme pivot et en recherchant l'élément maximum, si les données sont déjà triées. En pratique, cela peut être évité en choisissant un élément aléatoire comme pivot, ce qui donne une performance linéaire presque certaine . Alternativement, une stratégie de pivot déterministe plus prudente peut être utilisée, telle que la médiane des médianes . Ceux-ci sont combinés dans l' algorithme d' introselect hybride (analogue à introsort ), qui commence par Quickselect mais revient à la médiane des médianes si la progression est lente, ce qui entraîne à la fois des performances moyennes rapides et des performances optimales dans le pire des cas de O( n ).

Les algorithmes partitionnés sont généralement mis en place, ce qui conduit donc à un tri partiel des données. Ils peuvent être effectués hors de propos, sans modifier les données d'origine, au prix de O( n ) d'espace supplémentaire.

Sélection médiane comme stratégie pivot

Un algorithme de sélection médiane peut être utilisé pour produire un algorithme de sélection général ou un algorithme de tri, en l'appliquant comme stratégie de pivot dans Quickselect ou Quicksort ; si l'algorithme de sélection médiane est asymptotiquement optimal (temps linéaire), l'algorithme de sélection ou de tri résultant l'est également. En fait, une médiane exacte n'est pas nécessaire – une médiane approximative est suffisante. Dans l' algorithme de sélection de la médiane des médianes , la stratégie de pivot calcule une médiane approximative et l'utilise comme pivot, en se reproduisant sur un ensemble plus petit pour calculer ce pivot. En pratique, le surcoût du calcul du pivot est important, de sorte que ces algorithmes ne sont généralement pas utilisés, mais cette technique présente un intérêt théorique pour relier les algorithmes de sélection et de tri.

Dans le détail, étant donné un algorithme de sélection médiane, on peut l'utiliser comme stratégie de pivot dans Quickselect, obtenant un algorithme de sélection. Si l'algorithme de sélection médiane est optimal, c'est-à-dire O( n ), alors l'algorithme de sélection générale résultant est également optimal, c'est-à-dire à nouveau linéaire. En effet, Quickselect est un algorithme de division pour régner , et l'utilisation de la médiane à chaque pivot signifie qu'à chaque étape, la taille de l'ensemble de recherche diminue de moitié, de sorte que la complexité globale est une série géométrique multipliée par la complexité de chaque étape, et donc simplement une constante fois la complexité d'une seule étape, en fait des fois (somme de la série). ${\style d'affichage 2=1/(1-(1/2))}$

De même, étant donné un algorithme de sélection de médiane ou un algorithme de sélection générale appliqué pour trouver la médiane, on peut l'utiliser comme stratégie de pivot dans Quicksort, obtenant un algorithme de tri. Si l'algorithme de sélection est optimal, c'est-à-dire O( n ), alors l'algorithme de tri résultant est optimal, c'est-à-dire O( n log n ). La médiane est le meilleur pivot pour le tri, car elle divise uniformément les données, et garantit ainsi un tri optimal, en supposant que l'algorithme de sélection est optimal. Un tri analogue à la médiane des médianes existe, utilisant la stratégie de pivot (médiane approximative) dans Quicksort, et produit de la même manière un Quicksort optimal.

Tri incrémental par sélection

Contrairement à la sélection par tri, on peut effectuer un tri incrémental par sélection répétée. De manière abstraite, la sélection ne produit qu'un seul élément, le k ème élément. Cependant, les algorithmes de sélection pratiques impliquent fréquemment un tri partiel ou peuvent être modifiés pour le faire. La sélection par tri partiel le fait naturellement, le tri des éléments jusqu'à k , et la sélection par partitionnement trie également certains éléments : les pivots sont triés aux positions correctes, le k ème élément étant le pivot final, et les éléments entre les pivots ont valeurs entre les valeurs pivot. La différence entre la sélection basée sur les partitions et le tri basé sur les partitions, comme dans Quickselect par rapport à Quicksort, est que dans la sélection, on recourt à un seul côté de chaque pivot, en triant uniquement les pivots (une moyenne de log( n ) pivots est utilisée), plutôt que de se répéter des deux côtés du pivot.

Cela peut être utilisé pour accélérer les sélections suivantes sur les mêmes données ; à l'extrême, un tableau entièrement trié permet la sélection O(1). De plus, par rapport à un premier tri complet, le tri incrémental par sélection répétée amortit le coût du tri sur des sélections multiples.

Pour les données partiellement triées (jusqu'à k ), tant que les données partiellement triées et l'index k jusqu'auquel les données sont triées sont enregistrés, les sélections ultérieures de j inférieur ou égal à k peuvent simplement sélectionner le j ème élément, comme il est déjà trié, tandis que les sélections de j supérieures à k n'ont besoin de trier que les éléments au-dessus de la k ème position.

Pour les données partitionnées, si la liste des pivots est stockée (par exemple, dans une liste triée des indices), alors les sélections suivantes n'ont qu'à sélectionner dans l'intervalle entre deux pivots (les pivots les plus proches en dessous et au dessus). Le plus gros gain provient des pivots de haut niveau, qui éliminent les grandes partitions coûteuses : un seul pivot près du milieu des données réduit de moitié le temps des futures sélections. La liste pivot s'allongera au fil des sélections suivantes, à mesure que les données seront mieux triées, et pourront même être transmises à un tri basé sur une partition comme base d'un tri complet.

Utilisation de structures de données pour sélectionner en temps sublinéaire

Étant donné une liste de données non organisée, un temps linéaire (Ω( n )) est nécessaire pour trouver l'élément minimum, car nous devons examiner chaque élément (sinon, nous pourrions le manquer). Si nous organisons la liste, par exemple en la gardant triée à tout moment, alors la sélection du k ème élément le plus grand est triviale, mais alors l'insertion nécessite un temps linéaire, comme le font d'autres opérations telles que la combinaison de deux listes.

La stratégie pour trouver une statistique d'ordre en temps sublinéaire consiste à stocker les données de manière organisée en utilisant des structures de données appropriées qui facilitent la sélection. Deux de ces structures de données sont des structures arborescentes et des tables de fréquences.

Lorsque seul le minimum (ou le maximum) est nécessaire, une bonne approche consiste à utiliser un tas , qui est capable de trouver l'élément minimum (ou maximum) en temps constant, tandis que toutes les autres opérations, y compris l'insertion, sont O(log n ) ou mieux. Plus généralement, un arbre de recherche binaire auto-équilibré peut facilement être augmenté pour permettre à la fois d'insérer un élément et de trouver le k ième plus grand élément en un temps O(log n ) ; c'est ce qu'on appelle un arbre de statistiques d'ordre . Nous stockons simplement dans chaque nœud le nombre de descendants qu'il possède et l'utilisons pour déterminer le chemin à suivre. Les informations peuvent être mises à jour efficacement car l'ajout d'un nœud n'affecte que le nombre de ses ancêtres O(log n ) et les rotations d'arbres n'affectent que le nombre de nœuds impliqués dans la rotation.

Une autre stratégie simple est basée sur certains des mêmes concepts que la table de hachage . Lorsque nous connaissons la plage de valeurs à l'avance, nous pouvons diviser cette plage en h sous-intervalles et les affecter à h buckets. Lorsque nous insérons un élément, nous l'ajoutons au seau correspondant à l'intervalle dans lequel il se situe. Pour trouver l'élément minimum ou maximum, nous parcourons depuis le début ou la fin pour le premier seau non vide et trouvons l'élément minimum ou maximum dans ce seau . En général, pour trouver le k ème élément, nous maintenons un compte du nombre d'éléments dans chaque seau, puis parcourons les seaux de gauche à droite en additionnant les comptes jusqu'à ce que nous trouvions le seau contenant l'élément souhaité, puis utilisons le linéaire attendu. algorithme de temps pour trouver le bon élément dans ce seau.

Si nous choisissons h de taille approximativement sqrt( n ), et que l'entrée est presque uniformément distribuée, ce schéma peut effectuer des sélections dans le temps O(sqrt( n )) attendu . Malheureusement, cette stratégie est également sensible au regroupement d'éléments dans un intervalle étroit, ce qui peut entraîner des buckets avec un grand nombre d'éléments (le regroupement peut être éliminé grâce à une bonne fonction de hachage, mais trouver l'élément avec la k ème plus grande valeur de hachage n'est pas t très utile). De plus, comme les tables de hachage, cette structure nécessite des redimensionnements de table pour maintenir l'efficacité à mesure que des éléments sont ajoutés et que n devient beaucoup plus grand que h ² . Un cas utile de ceci est de trouver une statistique d'ordre ou un extremum dans une plage finie de données. L'utilisation du tableau ci-dessus avec l'intervalle de seau 1 et le maintien des comptes dans chaque seau sont bien supérieurs aux autres méthodes. Ces tables de hachage sont comme des tables de fréquence utilisées pour classer les données dans les statistiques descriptives .

Limites inférieures

Dans The Art of Computer Programming , Donald E. Knuth a discuté d'un certain nombre de limites inférieures pour le nombre de comparaisons nécessaires pour localiser les t plus petites entrées d'une liste non organisée de n éléments (en utilisant uniquement des comparaisons). Il existe une borne inférieure triviale de n − 1 pour l'entrée minimale ou maximale. Pour le voir, considérons un tournoi où chaque match représente une comparaison. Étant donné que chaque joueur, à l'exception du vainqueur du tournoi, doit perdre une partie avant de connaître le vainqueur, nous avons une limite inférieure de n − 1 comparaisons.

L'histoire devient plus complexe pour les autres index. Nous définissons comme le nombre minimum de comparaisons nécessaires pour trouver les t plus petites valeurs. Knuth fait référence à un article publié par SS Kislitsyn, qui montre une limite supérieure sur cette valeur : ${\style d'affichage W_{t}(n)}$

${\displaystyle W_{t}(n)\leq n-t+\sum _{n+1-t<j\leq n}\lceil {\log _{2}\,j}\rceil \quad {\text {pour}}\,n\geq t}$

Cette borne est réalisable pour t = 2 mais mieux, des bornes plus complexes sont connues pour un t plus grand .

Complexité spatiale

La complexité spatiale requise de la sélection est un stockage supplémentaire O(1), en plus du stockage de la matrice dans laquelle la sélection est effectuée. Une telle complexité spatiale peut être obtenue tout en préservant une complexité temporelle O(n) optimale.

Algorithme de sélection en ligne

La sélection en ligne peut se référer étroitement au calcul du k ème plus petit élément d'un flux, auquel cas des algorithmes de tri partiel - avec k + O(1) espace pour les k plus petits éléments jusqu'à présent - peuvent être utilisés, mais les algorithmes basés sur les partitions ne peuvent pas être utilisés. .

Alternativement, la sélection elle-même peut être requise pour être en ligne , c'est-à-dire qu'un élément ne peut être sélectionné qu'à partir d'une entrée séquentielle à l'instance d'observation et chaque sélection, respectivement refus, est irrévocable. Le problème est de sélectionner, sous ces contraintes, un élément spécifique de la séquence d'entrée (comme par exemple la plus grande ou la plus petite valeur) avec la plus grande probabilité. Ce problème peut être résolu par l' algorithme Odds , qui donne l'optimal sous une condition d'indépendance ; il est également optimal lui-même en tant qu'algorithme, le nombre de calculs étant linéaire dans la longueur d'entrée.

L'exemple le plus simple est le problème du secrétaire consistant à choisir le maximum avec une probabilité élevée, auquel cas la stratégie optimale (sur des données aléatoires) consiste à suivre le maximum courant des premiers n / e éléments et à les rejeter, puis à sélectionner le premier élément qui est supérieur à ce maximum.

Problèmes connexes

On peut généraliser le problème de sélection à appliquer aux plages dans une liste, ce qui donne le problème des requêtes de plage . La question des requêtes de la médiane des plages (calcul des médianes de plusieurs plages) a été analysée.

Support linguistique

Très peu de langues ont un support intégré pour la sélection générale, bien que beaucoup offrent des facilités pour trouver le plus petit ou le plus grand élément d'une liste. Une exception notable est C++ , qui fournit une nth_elementméthode basée sur un modèle avec une garantie de temps linéaire attendu, et partitionne également les données, exigeant que le n ème élément soit trié à sa place correcte, les éléments avant le n ème élément sont inférieurs à lui, et les éléments après le n ième élément sont supérieurs à celui-ci. Il est implicite mais pas obligatoire qu'il soit basé sur l'algorithme de Hoare (ou une variante) par son exigence de temps linéaire attendu et de partitionnement des données.

Pour Perl , le module Sort::Key::Top , disponible sur CPAN , fournit un ensemble de fonctions pour sélectionner les n premiers éléments d'une liste en utilisant plusieurs classements et procédures d'extraction de clés personnalisées. De plus, le module Statistics::CaseResampling fournit une fonction pour calculer les quantiles à l'aide de Quickselect.

La bibliothèque standard de Python (depuis 2.4) inclut heapq.nsmallest()et nlargest(), renvoyant des listes triées, en temps O( n log k ).

Matlab inclut maxk()et des mink()fonctions, qui renvoient les valeurs k maximales (minimales) dans un vecteur ainsi que leurs indices.

Parce que la prise en charge du langage pour le tri est plus omniprésente, l'approche simpliste du tri suivi de l'indexation est préférée dans de nombreux environnements malgré son inconvénient en termes de vitesse. En effet, pour les langages paresseux , cette approche simpliste peut même atteindre la meilleure complexité possible pour les k plus petits/plus grands triés (avec maximum/minimum comme cas particulier) si le tri est suffisamment paresseux.

Voir également

• Optimisation ordinale

Les références

Liens externes

• " Notes de cours du 25 janvier 1996 : Statistiques de sélection et d'ordre ", ICS 161 : Conception et analyse d'algorithmes, David Eppstein