Moo*_*uck 9 c++ profiling vector map
我一直被告知矢量很快,而且在我多年的编程经验中,我从来没有见过任何合同.我决定(过早地优化和)编写一个关联类,它是一个围绕顺序容器的薄包装器(即::std::vector提供相同的接口::std::map.大多数代码非常简单,而且我的工作没有什么困难.
然而,在我对各种大小的POD类型(4到64字节)的测试中,并且std::strings,计数从8到2千不等,::std::map::find比::associative::find几乎所有测试都要快,通常快15%左右.我制作了一个简短,自包含,正确(可编译)的示例,清楚地显示了这一点, 我检查了MSVC9的实现::std::map::find并确认它与我vecfind和::std::lower_bound代码非常接近,并且无法解释为什么::std::map::find运行速度更快,除了讨论Stack Overflow,人们推测二进制搜索方法从向量的局部性开始直到最后一次比较(使其不再快),并且它需要::std::map节点不需要的指针算法,使其变慢.
今天有人对此提出了挑战,并在ideone上提供了这个代码,当我测试时,它显示向量的速度超过两倍.
StackOverflow的程序员是否想要在这个明显的差异上启发我？我已经查看了两组代码,它们对我来说似乎很有用,但也许我对这两款代码都很瞎了.
(附注:这是非常密切的,以我以前的一个问题,但我的代码有哪些解决了几个bug由于新的信息/代码,我觉得这是不够的不同来证明一个单独的问题.如果没有,我会工作.合并他们.)
我发现您在 ideone.com 上发布的代码 ( http://ideone.com/41iKt ) 存在一些问题。（ideone 实际上显示vector得更快，但使用 Visual Studio 11 开发人员预览版的本地构建显示得map更快）。
首先，我移动了 map 变量并使用它来初始化向量以获得相同的元素排序和唯一性，然后我给出了lower_bound一个仅比较 的自定义比较器first，因为这就是 map 将要做的事情。经过这些更改后，对于相同的 100,000 个元素，Visual Studio 11 显示矢量速度更快（尽管 ideone 时间没有显着变化）。http://ideone.com/b3OnH
减少test_size到8张地图仍然更快。这并不奇怪，因为这就是算法复杂性的工作方式，函数中真正描述运行时间的所有常量都与小 N 有关。我必须将test_size向量提高到大约 2700 才能拉平，然后在这个映射之前系统。