為什麼微軟在 std::list::sort() 中切換到自上而下的歸併排序？

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

儘管長期使用底部-up 歸併排序方法在std::list::sort() 中，微軟的Visual Studio 2015 轉向了一種令人驚訝的低效遞歸實現的自頂向下歸併排序。這項變化引發了有關潛在動機的問題。

最初，人們認為 Microsoft 有令人信服的理由轉向效率較低的方法，特別是考慮到 VS2015 中引入了非預設可構造和有狀態分配器。然而，經過進一步調查，發現原來的自下而上的歸併排序演算法可以修改為與迭代器一起使用。

微軟的自上而下的方法

微軟的自上而下的實現使用遞歸方法在每個遞歸級別將列表分成兩半。這樣做的明顯原因是為了避免記憶體分配和異常安全問題。他們沒有創建列表數組來儲存排序的運行，而是使用迭代器來追蹤原始列表中的運行邊界。

雖然這種方法可以防止記憶體分配問題，但它會以以下形式引入低效率：在每次遞歸呼叫中存取清單的中點，可能會導致執行時間變慢。

替代的自下而上方法

作為替代方案，其他開發人員提出了底部的修改版本-up 使用迭代器而不是列表數組的合併排序演算法。這種方法涉及建立一個迭代器數組，其中每個條目代表排序運行的起點。掃描清單時，節點將合併到這些運行中，直到獲得單一排序清單。

此方法提供了速度和記憶體效率，在使用記憶體中分散的節點。

結論

微軟轉向自上而下歸併排序的原因仍然有些不清楚。雖然記憶體分配和異常安全問題可能會影響決策，但值得注意的是，這些問題可以透過保持更高效率的替代方法來解決。選擇效率較低的演算法表明 Microsoft 可能優先考慮穩定性和異常處理而不是效能。

以上是為什麼微軟在 std::list::sort() 中切換到自上而下的歸併排序？的詳細內容。更多資訊請關注PHP中文網其他相關文章！