Algorithme hybride - Hybrid algorithm
Un algorithme hybride est un algorithme qui combine deux ou plusieurs autres algorithmes qui résolvent le même problème, et est principalement utilisé dans les langages de programmation comme C++ , soit en en choisissant un (en fonction des données), soit en basculant entre eux au cours de l'algorithme. Ceci est généralement fait pour combiner les caractéristiques souhaitées de chacun, de sorte que l'algorithme global soit meilleur que les composants individuels.
« Algorithme hybride » ne fait pas référence à la simple combinaison de plusieurs algorithmes pour résoudre un problème différent - de nombreux algorithmes peuvent être considérés comme des combinaisons de pièces plus simples - mais uniquement à la combinaison d'algorithmes qui résolvent le même problème, mais diffèrent par d'autres caractéristiques, notamment les performances.
Exemples
En informatique , les algorithmes hybrides sont très courants dans les implémentations optimisées d' algorithmes récursifs dans le monde réel , en particulier les implémentations d' algorithmes diviser pour régner ou diminuer et régner , où la taille des données diminue à mesure que l'on s'enfonce dans la récursion. Dans ce cas, un algorithme est utilisé pour l'approche globale (sur les grandes données), mais au fond de la récursivité, il passe à un algorithme différent, qui est plus efficace sur les petites données. Un exemple courant est dans les algorithmes de tri , où le tri par insertion, qui est inefficace sur des données volumineuses, mais très efficace sur des données petites (disons, cinq à dix éléments), est utilisé comme étape finale, après avoir principalement appliqué un autre algorithme, tel que tri par fusion ou tri rapide . Le tri par fusion et le tri rapide sont asymptotiquement optimaux sur des données volumineuses, mais le surcoût devient important s'ils sont appliqués à de petites données, d'où l'utilisation d'un algorithme différent à la fin de la récursivité. Un algorithme de tri hybride hautement optimisé est Timsort , qui combine le tri par fusion, le tri par insertion, ainsi qu'une logique supplémentaire (y compris la recherche binaire ) dans la logique de fusion.
Une procédure générale pour un algorithme récursif hybride simple consiste à court-circuiter le cas de base, également connu sous le nom de récursivité sans lien de dépendance . Dans ce cas, la question de savoir si l'étape suivante aboutira au cas de base est vérifiée avant l'appel de fonction, évitant ainsi un appel de fonction inutile. Par exemple, dans un arbre, plutôt que de récurser vers un nœud enfant, puis de vérifier s'il est nul, vérifier null avant de récurser. Ceci est utile pour l'efficacité lorsque l'algorithme rencontre généralement le cas de base plusieurs fois, comme dans de nombreux algorithmes d'arbre, mais est par ailleurs considéré comme un style médiocre, en particulier dans le monde universitaire, en raison de la complexité supplémentaire.
Un autre exemple d'algorithmes hybrides pour des raisons de performances sont introsort et introselect , qui combinent un algorithme pour des performances moyennes rapides, se rabattant sur un autre algorithme pour assurer (asymptotiquement) des performances optimales dans le pire des cas. Introsort commence par un tri rapide , mais passe à un tri par tas si le tri rapide ne progresse pas bien ; de manière analogue, introselect commence par quickselect , mais passe à la médiane des médianes si quickselect ne progresse pas bien.
Les algorithmes distribués centralisés peuvent souvent être considérés comme des algorithmes hybrides, constitués d'un algorithme individuel (exécuté sur chaque processeur distribué) et d'un algorithme de combinaison (exécuté sur un distributeur centralisé) - ceux-ci correspondent respectivement à l'exécution de l'ensemble de l'algorithme sur un processeur, ou à l'exécution l'ensemble du calcul sur le distributeur, en combinant des résultats triviaux (un ensemble de données à un élément de chaque processeur). Un exemple de base de ces algorithmes sont les tris de distribution , particulièrement utilisés pour le tri externe , qui divisent les données en sous-ensembles séparés, trient les sous-ensembles, puis combinent les sous-ensembles en données totalement triées ; les exemples incluent bucket sort et flashsort .
Cependant, en général, les algorithmes distribués n'ont pas besoin d'être des algorithmes hybrides, car des algorithmes individuels ou des algorithmes de combinaison ou de communication peuvent résoudre différents problèmes. Par exemple, dans des modèles tels que MapReduce , les étapes Map et Reduce résolvent différents problèmes et sont combinées pour résoudre un troisième problème différent.