Pourquoi Microsoft est-il passé à un tri par fusion descendante dans std::list::sort() ?

std::list<>::sort() - Pourquoi le passage soudain à une stratégie descendante ?

Malgré l'utilisation de longue date d'une stratégie bottom -up Merge Sort dans std::list<>::sort(), Visual Studio 2015 de Microsoft a opté pour une implémentation récursive étonnamment inefficace du tri par fusion descendant. Ce changement soulève des questions sur les motivations sous-jacentes.

Au départ, il était supposé que Microsoft avait une raison impérieuse de passer à une approche moins efficace, en particulier compte tenu de l'introduction d'allocateurs avec état et non constructibles par défaut dans VS2015. Cependant, après une enquête plus approfondie, il a été découvert que l'algorithme de tri par fusion ascendant d'origine pouvait être modifié pour fonctionner avec des itérateurs.

L'approche descendante de Microsoft

L'implémentation descendante de Microsoft utilise un approche récursive pour diviser la liste en deux à chaque niveau de récursion. La raison apparente en est d'éviter les problèmes d'allocation de mémoire et de sécurité des exceptions. Au lieu de créer un tableau de listes pour stocker les exécutions triées, ils utilisent des itérateurs pour suivre les limites des exécutions dans la liste d'origine.

Bien que cette approche puisse éviter les problèmes d'allocation de mémoire, elle introduit une inefficacité sous la forme de accéder au point médian de la liste dans chaque appel récursif, ce qui pourrait entraîner un temps d'exécution plus lent.

Approche alternative ascendante

Comme alternative, d'autres développeurs ont proposé une version modifiée du bottom -up Merge Sort, algorithme qui utilise des itérateurs au lieu d'un tableau de listes. Cette approche implique la création d'un tableau d'itérateurs, où chaque entrée représente le point de départ d'une exécution triée. Au fur et à mesure que la liste est analysée, les nœuds sont fusionnés dans ces exécutions jusqu'à ce qu'une seule liste triée soit obtenue.

Cette méthode offre à la fois vitesse et efficacité de la mémoire, surpassant le tri par fusion descendant d'environ 40 à 50 % sur les listes avec nœuds dispersés en mémoire.

Conclusion

Les raisons du passage de Microsoft au tri par fusion descendant restent quelque peu floues. Bien que les problèmes d'allocation de mémoire et de sécurité des exceptions puissent avoir influencé la décision, il est important de noter que ces problèmes peuvent être résolus avec des approches alternatives qui maintiennent une efficacité plus élevée. Le choix d'un algorithme moins efficace suggère que Microsoft a peut-être donné la priorité à la stabilité et à la gestion des exceptions plutôt qu'aux performances.

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!