应该使用插入排序还是构建堆来提高性能？

Question

我们有大量（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 之后进行排序。

我认为我基本上有两个选择来提高性能：

1. 使用（手工制作的？）插入排序而不是std::sort来提高排序性能（插入对部分排序的向量进行排序的速度快得令人眼花缭乱）

2. 使用 std::make_heap 和 std::push_heap 创建堆来维护排序顺序

我的问题是：

• 我应该实现插入排序吗？ Boost 中有什么可以帮助我的吗？

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

---

编辑：

感谢您的所有回复。 我知道我给出的示例远非最佳，它并不能完全代表我现在代码中的内容。 它只是为了说明我遇到的性能瓶颈 - 也许这就是为什么这个问题没有看到很多赞成票:)

非常感谢你 史蒂夫，通常最简单的答案就是最好的，也许是我对问题的过度分析让我看不到也许是最明显的解决方案。 我确实喜欢您概述的直接插入到预先排序的向量中的简洁方法。

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

Answer 1

有序插入不需要 boost：

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

upper_bound 提供了一个有效的插入点，前提是向量已排序，因此只要您只将元素插入到正确的位置，就完成了。 我最初说的是lower_bound，但是如果向量包含多个相等的元素，那么upper_bound会选择需要较少工作的插入点。

这确实需要复制 O(n) 个元素，但是你说插入排序“快得令人眼花缭乱”，而这更快。 如果不够快，你必须找到一种方法来批量添加项目并在最后验证，否则放弃连续存储并切换到维护顺序的容器，例如 set 或多重集。

堆不维护底层容器中的顺序，但对于优先级队列或类似队列很有用，因为它可以快速删除最大元素。 您说您想要按顺序维护向量，但如果您从未真正按顺序迭代整个集合，那么您可能不需要它完全排序，这就是堆有用的时候。

Answer 2

根据 Meyers'Effective STL 的第 23 条，如果您的应用程序分 3 个阶段使用其数据结构，则应该使用排序向量。 从书中，他们是：

1. 设置。 通过向其中插入大量元素来创建新的数据结构。 在这个阶段，几乎所有的操作都是插入和擦除。 查找很少甚至不存在
2. 查找。 查阅数据结构以查找特定信息。 在这个阶段，几乎所有的操作都是查找。 插入和擦除很少或根本不存在。 查找次数太多，这个阶段的性能使得其他阶段的性能变得次要。
3. 重新组织。修改数据结构的内容。 也许通过擦除所有当前数据并在其位置插入新数据。 从行为上来说，此阶段相当于第 1 阶段。此阶段完成后，应用程序将返回到第 2 阶段

如果您对数据结构的使用与此类似，则应使用排序向量，然后使用提到的 binary_search。 如果没有，典型的关联容器应该可以做到这一点，这意味着集合、多集、映射或多映射，因为这些结构默认排序

Answer 3

为什么不直接使用二分搜索来查找插入新元素的位置呢？ 然后您将准确地插入所需的位置。

Answer 4

如果您需要将大量元素插入到已排序的序列中，请使用 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
}

Answer 5

使用二分搜索来查找插入位置不会大大加快算法速度，因为执行插入操作的时间复杂度仍然是 O(N)（考虑在向量的开头插入 - 您必须将每个元素向下移动一个）来创造空间）。

树（又名堆）的插入时间复杂度为 O(log(N))，性能更好。

请参阅http://www.sgi.com/tech/stl/priority_queue.html

请注意，除非树是平衡的，否则插入树在最坏情况下仍将具有 O(N) 性能，例如 AVL 树。

Answer 6

为什么不使用 boost::multi_index ？

注意：boost::multi_index 不提供内存连续性，这是 std::vectors 的一种属性，通过该属性，元素在单个内存块中彼此相邻存储。

Answer 7

您需要做一些事情。

1. 您可能需要考虑使用 reserve() 来避免整个向量的过度重新分配。 如果您知道它将增长到的大小，您可以通过自己执行 resrve() 来获得一些性能（而不是让实现使用内置启发式自动执行它们）。

2. 进行二分查找来找到插入位置。 然后调整大小并将插入点后面的所有内容向上移动一位以腾出空间。

3. 考虑一下：你真的想使用向量吗？ 也许set或map更好。

二分搜索相对于 lower_bound 的优势在于，如果插入点接近向量的末尾，则无需付出 theta(n) 复杂度。

Answer 8

1. 如果你想将一个元素插入到“正确”的位置，为什么你打算使用排序。 使用 lower_bound 查找位置并使用向量的“insert”方法插入。 插入新项目的时间复杂度仍然是 O(N)。

2. 堆不会帮助你，因为堆没有排序。 它允许您快速获取最小元素，然后快速删除它并获取下一个最小元素。 但是，堆中的数据不是按排序顺序存储的，因此如果您有必须按顺序迭代数据的算法，那将无济于事。

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

Answer 9

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

• 您不想对大型集合使用连续内存，插入不应花费 O(n) 时间；
• 您希望对单个元素至少使用二进制插入，应该对多个元素进行预排序，以便可以使搜索边界更小；
• 您不希望数据结构浪费内存，因此每个数据元素都没有左指针和右指针。

Answer 10

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

如果您担心列表分配在不同的内存页面上并导致与缓存相关的性能问题，请在数组中预分配节点（池对象）并将它们插入列表中。

您可以在数据类型中添加一个值，表示它是从堆分配还是从池分配。 这样，如果您检测到池空间不足，您可以开始从堆中分配并向自己抛出一个断言或其他内容，这样您就知道要增加池大小（或将其设为要设置的命令行选项）。

希望如此有帮助，因为我看到你已经有很多很好的答案。