为什么微软在 std::list::sort() 中切换到自上而下的归并排序？-C++-PHP中文网

首页

后端开发

C++

为什么微软在 std::list::sort() 中切换到自上而下的归并排序？

Susan Sarandon

Oct 28, 2024 pm 07:53 PM

Why Did Microsoft Switch to a Top-Down Merge Sort in std::list::sort()?

std::list::sort() - 为什么突然切换到自上而下策略？

尽管长期使用底部-up 归并排序方法在 std::list::sort() 中，微软的 Visual Studio 2015 转向了一种令人惊讶的低效递归实现的自顶向下归并排序。这一变化引发了有关潜在动机的问题。

最初，人们认为 Microsoft 有令人信服的理由转向效率较低的方法，特别是考虑到 VS2015 中引入了非默认可构造和有状态分配器。然而，经过进一步调查，发现原来的自下而上的归并排序算法可以修改为与迭代器一起使用。

微软的自上而下的方法

微软的自上而下的实现使用递归方法在每个递归级别将列表分成两半。这样做的明显原因是为了避免内存分配和异常安全问题。他们没有创建列表数组来存储排序的运行，而是使用迭代器来跟踪原始列表中的运行边界。

虽然这种方法可以防止内存分配问题，但它会以以下形式引入低效率：在每次递归调用中访问列表的中点，可能会导致执行时间变慢。

替代的自下而上方法

作为替代方案，其他开发人员提出了底部的修改版本-up 使用迭代器而不是列表数组的合并排序算法。这种方法涉及创建一个迭代器数组，其中每个条目代表排序运行的起点。扫描列表时，节点将合并到这些运行中，直到获得单个排序列表。

此方法提供了速度和内存效率，在使用内存中分散的节点。

结论

微软转向自上而下归并排序的原因仍然有些不清楚。虽然内存分配和异常安全问题可能会影响决策，但值得注意的是，这些问题可以通过保持更高效率的替代方法来解决。选择效率较低的算法表明 Microsoft 可能优先考虑稳定性和异常处理而不是性能。

以上是为什么微软在 std::list::sort() 中切换到自上而下的归并排序？的详细内容。更多信息请关注PHP中文网其他相关文章！

声明

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

在C中使用XML：库和工具指南May 09, 2025 am 12:16 AM

在C 中使用XML是因为它提供了结构化数据的便捷方式，尤其在配置文件、数据存储和网络通信中不可或缺。1)选择合适的库，如TinyXML、pugixml、RapidXML，根据项目需求决定。2)了解XML解析和生成的两种方式：DOM适合频繁访问和修改，SAX适用于大文件或流数据。3)优化性能时，TinyXML适合小文件，pugixml在内存和速度上表现好，RapidXML处理大文件优异。

C＃和C：探索不同的范例May 08, 2025 am 12:06 AM

C#和C 的主要区别在于内存管理、多态性实现和性能优化。1）C#使用垃圾回收器自动管理内存，C 则需要手动管理。2）C#通过接口和虚方法实现多态性，C 使用虚函数和纯虚函数。3）C#的性能优化依赖于结构体和并行编程，C 则通过内联函数和多线程实现。

C XML解析：技术和最佳实践May 07, 2025 am 12:06 AM

C 中解析XML数据可以使用DOM和SAX方法。1)DOM解析将XML加载到内存，适合小文件，但可能占用大量内存。2)SAX解析基于事件驱动，适用于大文件，但无法随机访问。选择合适的方法并优化代码可提高效率。

c在特定领域：探索其据点May 06, 2025 am 12:08 AM

C 在游戏开发、嵌入式系统、金融交易和科学计算等领域中的应用广泛，原因在于其高性能和灵活性。1)在游戏开发中，C 用于高效图形渲染和实时计算。2)嵌入式系统中，C 的内存管理和硬件控制能力使其成为首选。3)金融交易领域，C 的高性能满足实时计算需求。4)科学计算中，C 的高效算法实现和数据处理能力得到充分体现。