代码之家 › 专栏 › 技术社区 › Alan

应该使用插入排序或构造堆来提高性能?

boost stl sorting algorithm c++

Alan · 技术社区 · 17 年前

我们有大型(100000+个元素)结构的有序向量(运算符<重载以提供排序):

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 维持分拣顺序

我应该考虑使用堆吗?我该怎么做?

编辑:

谢谢你的回复。我知道我给出的示例远远不是最优的,它不能完全代表我现在代码中的内容。这仅仅是为了说明我所经历的性能瓶颈——也许这就是为什么这个问题没有获得很多赞成票的原因:)

Steve ,往往最简单的答案才是最好的,也许是我对问题的过度分析让我看不到最明显的解决方案。我非常喜欢您概述的直接插入到预排序向量的简洁方法。

正如我所评论的,我现在只能使用向量,所以std::set、std::map等都不是一个选项。

10 回复 | 直到 9 年前

Steve Jessop 17 年前

有序插入不需要增强:

vectorMyTypes.insert(
    std::upper_bound(vectorMyTypes.begin(), vectorMyTypes.end(), newType),
    newType);

upper_bound 提供一个有效的插入点,前提是向量从开始排序,因此只要您只在正确的位置插入元素,就完成了。我原来说 lower_bound ,但如果向量包含多个相等的元素,则选择需要较少工作的插入点。

这确实需要复制O(n)个元素,但您说插入排序“快得惊人”,而且速度更快。如果速度不够快,您必须找到一种方法来批量添加项并在最后进行验证,或者放弃连续存储并切换到维护顺序的容器,例如 set multiset .

堆不维护底层容器中的顺序,但适合优先级队列或类似队列,因为它可以快速删除最大元素。你说你想保持向量的顺序,但是如果你从来没有按顺序迭代过整个集合,那么你可能不需要对它进行完全排序,这时堆是有用的。

Gab Royer 17 年前

根据Meyers的有效STL第23项,如果应用程序分3个阶段使用其数据结构,则应使用排序向量。从书中可以看出,它们是:

安装程序 . 通过向其中插入大量元素来创建新的数据结构。在这个阶段,几乎所有的操作都是插入和擦除。在不存在的数据库上很少进行查找

查找 . 查阅数据结构以查找特定的信息。在此阶段,几乎所有操作都是查找。插入和擦除很少或根本不存在。有如此多的查找,此阶段的性能使其他阶段的性能附带。

重组。

如果您对数据结构的使用类似于此,那么应该使用排序向量,然后使用前面提到的二进制搜索。如果不是,典型的关联容器应该这样做,这意味着 集合、多集合、映射或多映射 如那些结构 默认情况下是按顺序排列的

sharptooth 17 年前

Marc Mutz - mmutz 17 年前

如果需要在排序序列中插入大量元素,请使用 std::merge ,可能首先对新元素进行排序:

void add( std::vector<Foo> & oldFoos, const std::vector<Foo> & newFoos ) {
    std::vector<Foo> merged;
    // precondition: oldFoos _and newFoos_ are sorted
    merged.reserve( oldFoos.size() + newFoos.size() ); // only for std::vector
    std::merge( oldFoos.begin(), oldFoos.end(),
                newFoos.begin(), newFoos.end(),
                std::back_inserter( merged );
    // apply std::unique, if wanted, here
    merged.erase( std::unique( merged.begin(), merged.end() ), merged.end() );
    oldFoos.swap( merged ); // commit changes
}

Larry Watanabe 17 年前

树(又名heap)将被O(log(N))插入,性能更好。

看 http://www.sgi.com/tech/stl/priority_queue.html

请注意,除非树是平衡的,否则对于insert,树仍将具有最差的O(N)性能,例如AVL树。

Kirill V. Lyadvinsky 17 年前

为什么不使用 boost::multi_index ?

注: boost::multi_index std::vectors

Ari 17 年前

你需要做几件事。

你可以考虑利用 reserve() resrve() s你自己(而不是让实现使用内置的启发式自动完成它们)。
执行二进制搜索以查找插入位置。然后 resize
思考:你真的想使用向量吗?也许是 set 或 map 你的情况更好。

二进制搜索的优势 lower_bound 如果插入点接近向量的末端,则不必支付θ(n)复杂度。

Vladimir Prus 17 年前

分类 lower_bound
堆不会帮助您,因为堆没有排序。它允许您快速获取最小的元素,然后快速删除它并获取下一个最小的元素。但是,堆中的数据不是按排序顺序存储的,因此,如果您有必须按顺序迭代数据的算法,这将没有帮助。

恐怕您的描述略过了很多细节,但似乎列表并不是该任务的合适元素。 std::deque 更适合在中间插入,您也可以考虑 std::set . 我建议您解释一下为什么需要对数据进行排序,以获得更有用的建议。

Stephan Eggermont 17 年前

您可能需要考虑使用BTree或Judy Trie。

您不想为大型集合使用连续内存,插入不应该花费O(n)时间;
如果要对单个元素使用至少二进制插入,则应对多个元素进行预排序,以便缩小搜索边界;

jeffdev 13 年前

正如其他人所说,我可能会从链表中创建一个BTree,而不是使用向量。即使你已经解决了排序问题,向量在需要增长时也存在完全重新分配的问题,假设你事先不知道自己的最大大小。

如果您担心在不同内存页上分配列表会导致与缓存相关的性能问题,请在阵列中预先分配节点,(将对象合并)并将它们插入列表中。

希望这有帮助,因为我看到你已经有了很多很好的答案。