c++ - vector 与 map 性能混淆

Question

edit:我专门将 std::vector 的 linear 搜索操作与 std::map binary 搜索操作，因为这似乎与 Herb 的声明有关。我知道使用二分搜索会将性能从 O(N) 提高到 O(log N) 但这不会测试 Herb 的主张

Bjarne Stroustrup 和 Herb Sutter 最近都谈到了 std::vector 在人们期望使用 std::list 的情况下是多么的棒，因为链表遍历期间缓存未命中的成本。 (见 http://channel9.msdn.com/Events/Build/2014/2-661 在 48 分钟标记处)

Herb 进一步声明，对有序 vector 的操作甚至比 std::map 还要快(参见 http://i.imgur.com/zX07TZR.png，取自上述 channel9 视频的 51:30 标记)，我发现很难理解。所以我创建了一个小测试来证明这一点，但很难重现这些结果:https://ideone.com/MN7DYK

这是测试代码:

template <typename C>
void test(std::string name, std::vector<int> shuffledInputValues, C & c)
{
   // fill container 'c' with values from 'shuffledInputValues' then erase them all
   {
      std::cout << "testing " << name << "..." << std::endl;
      timer t;

      for (auto val : shuffledInputValues) insert(c, val);
      for (auto val : shuffledInputValues) remove(c, val);
  }
}

// output:
// testing vector...99.189ms
// testing deque...120.848ms
// testing set...4.077ms

注意 std::vector 的执行速度比 std::set 慢一个数量级。当然这是我预期的结果，但我对 Herb 试图提出的说法感到困惑。

我做错了什么？还是我误解了 Herb 的说法？

关于我的测试应用的注意事项:

• 它必须使用线性运算 - 练习的重点是演示 CPU 缓存魔法，这是 Herb 和 Bjarne 对练习的约束
• 我没有为 vector 迭代尝试任何棘手的循环解开，但我相信迭代不会对性能产生太大影响
• 我将循环限制为 10K 项，因为 ideone 在更大的集合上超时，但增加大小不会改变结果

编辑:见 https://ideone.com/916fVd对于仅比较查找性能的修改示例。线性搜索表现出相同的性能。

Answer 1

我找到了 slides为了更容易引用(我看不到图表，但我想这可能是因为专有文件格式)。相关的幻灯片是第 39 号，它描述了正在解决的问题:

§ Generate N random integers and insert them into a sequence so that each is inserted in its proper position in the numerical order.

§ Remove elements one at a time by picking a random position in the sequence and removing the element there.

现在，很明显链表不是解决这个问题的好选择。尽管列表在开头或中间插入/删除比 vector 好得多，但由于需要线性搜索，因此在 随机 位置插入/删除并不好。由于缓存效率更高，使用 vector 进行线性搜索要快得多。

Sutter 建议 map (或一般的树)似乎是该算法的自然选择，因为您得到 O(log n) 搜索。事实上，对于插入部分中较大的 N 值，它确实很容易击败 vector 。

但是来了。您需要删除第 n 个元素(对于随机 n)。这就是我认为您的代码作弊的地方。您可以按照插入的顺序删除元素，有效地将输入 vector 用作查找表，以在“随机”位置查找元素的值，以便您可以在 O(log n) 中搜索它。所以你实际上是在使用集合和 vector 的组合来解决问题。

常规的二叉搜索树，例如用于 std::map 或 std::set(我假设 Sutter 使用)的二叉搜索树没有快速算法用于查找第 n 个元素。 Here's one据称平均为 O(log n)，在最坏的情况下为 O(n)。但是 std::map 和 std::set 不提供对底层树结构的访问，所以对于那些你被按顺序遍历卡住的人(如果我错了)这又是一个线性搜索!实际上，我很惊讶 map 版本与 Sutter 结果中的 vector 版本具有竞争力。

对于 log(n) 复杂度，您需要一个结构，例如 Order statistic tree不幸的是，标准库没有提供。有如图所示的 GNU Policy-Based STL MAP here .

这是我为 vector vs 集合 vs ost 制作的快速测试代码(vs vector 与二进制搜索以获得良好的度量)https://ideone.com/DoqL4HSet 慢得多，而其他基于树的结构比 vector 快，这与 Sutter 的结果不符。

order statistics tree: 15.958ms
vector binary search: 99.661ms
vector linear search: 282.032ms
set: 2004.04ms

(N = 20000，差异只会更大，有利于具有更大值的ost)

简而言之，我得出了相同的结论，即 Sutter 的原始结果看起来很奇怪，但原因略有不同。在我看来，这次更好的渐近复杂度赢得了更低的常数因子。

请注意，问题描述并不排除重复随机值的可能性，因此使用 map/set 而不是 multimap/multiset 有点欺骗 map/set，但我认为只有很小的意义当值域远大于 N 时。此外，预先保留 vector 不会显着提高性能(当 N = 20000 时大约为 1%)。