Pourquoi `std::list::sort()` est-il passé à une approche de tri par fusion descendante ?

STL : repenser std::list::sort()

Traditionnellement, std::list::sort() implémentait un algorithme de tri par fusion ascendant en utilisant pointeurs. Cependant, à partir de Visual Studio 2015, la bibliothèque standard est passée à une stratégie de tri par fusion descendante. Malgré la perception initiale d'inefficacité due aux analyses séquentielles répétées à chaque niveau de récursivité, un examen plus approfondi du code révèle une autre histoire.

L'approche descendante et ses avantages

Au lieu de En analysant la liste pour la diviser, l'approche descendante divise de manière récursive la taille entière par 2, permettant une fusion plus rapide en réduisant le nombre de comparaisons d'éléments. De plus, l'utilisation initiale de std::next pour localiser le point médian peut sembler inefficace, mais elle tire parti des propriétés de la liste pour diviser efficacement la liste en deux.

Le passage à l'utilisation d'itérateurs évite l'allocation de mémoire et garantit sécurité exceptionnelle. Si une fonction de comparaison lève une exception, la liste restera ordonnée sans perdre aucune donnée. L'utilisation de std::list::splice dans la logique de fusion permet un mouvement efficace des nœuds dans la liste d'origine, améliorant encore sa stabilité et sa gestion des exceptions.

Considérations sur les performances

Contrairement à l'initiale hypothèses, le tri par fusion descendant dans std::list::sort() surpasse souvent le tri par fusion ascendant dans certains scénarios. Pour les listes avec des nœuds dispersés ou lorsque la mémoire est limitée, le tri par fusion descendant présente un meilleur comportement du cache, ce qui entraîne une exécution plus rapide. Cependant, si la mémoire est abondante, déplacer la liste vers un tableau ou un vecteur et la trier dans ce format est généralement plus efficace.

Tri alternatif par fusion ascendante avec itérateurs

Malgré l'efficacité de Avec l'approche descendante, certains ont cherché à modifier le tri par fusion ascendant pour fonctionner avec des itérateurs, éliminant ainsi le besoin d'un tableau de listes. Cette approche utilise un ensemble d'itérateurs pour suivre les limites d'exécution triées et emploie std::list::splice pour la fusion, obtenant des résultats similaires à l'approche descendante.

Conclusion

Le passage à un tri par fusion descendant dans std::list::sort() n'était pas une décision hâtive mais une optimisation soigneusement réfléchie qui a donné des améliorations significatives en termes de performances et de stabilité. Même si l'approche descendante n'est pas toujours idéale, elle a fait ses preuves dans certains scénarios, offrant un algorithme de tri plus rapide et plus fiable.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!