為什麼 Visual Studio 2015 對 std::list::sort() 從自下而上合併排序切換為自上而下合併排序？

std::list::sort() - 為什麼突然切換到自頂向下策略？

在 Visual Studio 2015 中， std::list::sort() 的實作經歷了從經典的自下而上合併排序到自上而下合併排序的重大變化。這種轉變要求為每個遞歸等級找到清單的中點，從而導致明顯的低效率。

更改的原因：

但是，如文件中所述在提供的更新中，Microsoft 進行了優化以保留無內存分配和異常安全修復，這些修復促使最初更改為使用迭代器。具體來說，遞歸實作：

• 使用高效的合併排序，在每個遞歸層級將清單除以 2，而不是掃描清單。
• 恢復為使用指標迭代器，有可能提高效能。
• 實作拼接邏輯以改善一次多個節點的合併。

與自下而上歸併排序的比較：

儘管進行了優化，但在處理大型、分散的鍊錶時，由於緩存未命中增加，自上而下的方法仍然有可能比自下而上的合併排序慢。

替代實現：

提供了一種替代實現，它保留了自下而上的合併排序方法，同時使用迭代器而不是列表數組。這種方法的目的是避免在遞歸過程中總是必須找到列表的中點而對效能造成影響。

結論：

在 Visual 中切換到自上而下的合併排序Studio 2015 並非一時興起。 Microsoft 實施了最佳化來解決潛在的低效率問題，同時保留異常安全性和減少記憶體分配的優勢。然而，對於大型、稀疏的鍊錶，自下而上的合併排序方法仍然可以提供更好的效能。

以上是為什麼 Visual Studio 2015 對 std::list::sort() 從自下而上合併排序切換為自上而下合併排序？的詳細內容。更多資訊請關注PHP中文網其他相關文章！