矢量vs地图表现混乱

Question

编辑:我特别比较std::vector的线性搜索操作的std::map 二进制搜索行动,因为这是香草的要求似乎涉及到.我知道使用二进制搜索会将性能从O(N)移到O(log N),但这不会测试Herb的声明

Bjarne Stroustrup和Herb Sutter最近都谈到了std::vector在人们期望std::list使用的情况下有多棒,这是由于链表遍历期间缓存未命中的代价.(见48分钟后http://channel9.msdn.com/Events/Build/2014/2-661)

Herb做了进一步的声明,然而对有序矢量的操作甚至更快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试图制作的说法感到困惑.

我究竟做错了什么？还是我误解了赫伯的说法？

我的测试应用笔记:

• 它必须使用线性操作 - 练习的全部内容是演示CPU缓存魔法,这些是Herb和Bjarne对练习的约束
• 我没有尝试任何棘手的循环解开我的矢量迭代,但我相信迭代不会影响性能
• 我将循环限制为10K项,因为ideone在较大的集上超时,但增加大小不会改变结果

编辑:有关仅比较查找性能的修改示例,请参阅https://ideone.com/916fVd.线性搜索表现出相同的性能.

Answer 1

我发现幻灯片更容易参考(我看不到图表,但我想这可能是因为专有文件格式).相关幻灯片是第39号,描述了正在解决的问题:

§生成N个随机整数并将它们插入序列中,以便按数字顺序将每个整数插入其正确的位置.

§通过选择序列中的随机位置并删除元素,一次删除一个元素.

现在,相当明显的是,链表不是这个问题的好选择.即使列表在开头或中间插入/删除比使用矢量要好得多,但由于需要线性搜索,因此在随机位置插入/删除不好.由于更好的缓存效率,使用向量的线性搜索速度更快.

Sutter建议一个地图(或一般的树)似乎是这个算法的自然选择,因为你得到了O(log n)搜索.实际上,对于N插入部分中的大值,它确实很容易击败向量.

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

常规二进制搜索树,例如用于std::map或std::set(我假设使用Sutter)的树,没有用于查找第n个元素的快速算法.这里声称平均为O(log n),最坏情况为O(n).但是std::map并且std::set不提供对底层树结构的访问权限,因此对于那些你仍然按顺序遍历的人(如果我错了就纠正我),这又是一次线性搜索!我真的很惊讶地图版本与Sutter的结果中的矢量竞争一致.

对于log(n)复杂性,您需要一个诸如Order statistic tree之类的结构,遗憾的是它不是由标准库提供的.还有如GNU基于策略的STL MAP 这里.

这是我为矢量与set vs ost制作的快速测试代码(对于具有二分搜索的矢量用于良好测量)https://ideone.com/DoqL4H 设置慢得多,而其他基于树的结构比矢量快,不符合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在地图/集合中有点作弊,但我认为在值域时只有很小的意义远大于N.此外,预先保留矢量不会显着改善性能(当N = 20000时,约为1%).