Ala*_*lan 2 c++ sorting algorithm boost stl
我们有大型(100,000+元素)结构的有序向量(运算符<重载以提供排序):
std::vector < MyType > vectorMyTypes;
std::sort(vectorMyType.begin(), vectorMyType.end());
我的问题是,在保留排序顺序的同时向这些向量添加新元素时,我们会看到性能问题.目前我们正在做类似的事情:
for ( a very large set )
{
vectorMyTypes.push_back(newType);
std::sort(vectorMyType.begin(), vectorMyType.end());
...
ValidateStuff(vectorMyType); // this method expects the vector to be ordered
}
这不完全是我们的代码看起来的样子,因为我知道这个例子可以用不同的方式进行优化,但是它可以让你了解性能如何成为一个问题,因为我在每一个之后进行排序push_back.
我认为我基本上有两种选择来提高性能:
使用(手工制作？)插入排序而不是std::sort提高排序性能(部分排序的矢量上的插入排序非常快)
通过使用std::make_heap和std::push_heap维护排序顺序来创建堆
我的问题是:
我应该实现插入排序吗？Boost中有什么东西可以帮助我吗？
我应该考虑使用堆吗？我该怎么做？
编辑:
感谢您的所有回复.我理解我给出的示例远非最佳,并且它不能完全代表我现在在代码中的内容.它只是在那里说明我遇到的性能瓶颈 - 也许这就是为什么这个问题没有看到许多上升票:)
非常感谢史蒂夫,这通常是最简单的答案,也许是我对问题的过度分析使我对最明显的解决方案视而不见.我喜欢你概述的简洁方法直接插入预先排序的矢量.
正如我评论的那样,我现在限制使用向量,因此std :: set,std :: map等不是一个选项.
Ste*_*sop 10
有序插入不需要提升:
vectorMyTypes.insert(
std::upper_bound(vectorMyTypes.begin(), vectorMyTypes.end(), newType),
newType);
upper_bound提供一个有效的插入点,前提是向量按开始排序,所以只要你只在正确的位置插入元素,就完成了.我原先说过lower_bound,但是如果向量包含多个相等的元素,那么upper_bound选择需要较少工作的插入点.
这必须复制O(n)元素,但是你说插入排序"非常快",而且速度更快.如果它不够快,你必须找到一种方法来批量添加项目并在最后验证,或者放弃连续存储并切换到维护订单的容器,例如set或multiset.
堆不会在底层容器中维护顺序,但对于优先级队列或类似物是有利的,因为它可以快速删除最大元素.你说你想按顺序维护向量,但如果你从来没有按顺序迭代整个集合,那么你可能不需要它完全排序,那就是堆有用的时候.
根据Meyers的Effective STL项目23,如果您的应用程序在3个阶段中使用其数据结构,则应使用排序向量.从这本书中,他们是:
- 设置.通过在其中插入大量元素来创建新的数据结构.在此阶段,几乎所有操作都是插入和擦除.查找很少见,不存在
- 查找.查阅数据结构以查找特定信息.在此阶段,几乎所有操作都是查找.插入和删除很少或不存在.有这么多的查找,这个阶段的性能使其他阶段的性能偶然.
- 改组.修改数据结构的内容.也许通过删除所有当前数据并在其位置插入新数据.在行为上,这个阶段相当于第1阶段.一旦完成此阶段,应用程序将返回阶段2
如果您对数据结构的使用类似于此,则应使用已排序的向量,然后使用提及的binary_search.如果没有,典型的关联容器应该这样做,这意味着一个集合,多集,地图或多图,因为这些结构是默认排序的