为什么矢量比地图在一个测试中快，但不是其他？ [英] Why is vector faster than map in one test, but not the other?

问题描述

我一直被告知载体是快速的，在我多年的编程经验，我从来没有见过任何合同。我决定（过早优化和）编写一个关联类，它是一个连续容器（即 :: std :: vector ）的薄包装，并提供与 :: std :: map 。大多数代码非常简单，我很容易处理。

I've always been told vectors are fast, and in my years of programming experience, I've never seen anything to contract that. I decided to (prematurely optimize and) write a associative class that was a thin wrapper around a sequential container (namely ::std::vector and provided the same interface as ::std::map. Most of the code was really easy, and I got it working with little difficulty.

但是，在我测试的各种大小的POD类型（4到64字节）和 std :: strings ，计数从八到二千， :: std :: map :: find 比我的 :: associative :: find 更快，通常快15％所有测试我做了一个简短，自我，正确（可编译），示例，清楚地显示了在ideone 我检查了MSVC9的 :: std :: map :: find 的实现，并确认它匹配我的 vecfind 和 :: std :: lower_bound 代码，并不能说明为什么 :: std :: map :: find 运行得更快，除了有关Stack Overflow的讨论，人们推测二进制搜索方法根本不会从向量的局部性获益，直到最后比较（使它不快），并且它需要指针算术， :: std :: map 节点不需要，使它更慢。

However, in my tests of various sized POD types (4 to 64 bytes), and std::strings, with counts varying from eight to two-thousand, ::std::map::find was faster than my ::associative::find, usually around 15% faster, for almost all tests. I made a Short, Self Contained, Correct (Compilable), Example that clearly shows this at ideone I checked MSVC9's implementation of ::std::map::find and confirmed that it matches my vecfind and ::std::lower_bound code quite closely, and cannot account for why the ::std::map::find runs faster, except for a discussion on Stack Overflow where people speculated that the binary search method does not benefit at all from the locality of the vector until the last comparison (making it no faster), and that it's requires pointer arithmetic that ::std::map nodes don't require, making it slower.

今天有人对我提出质疑，并在ideone 提供了此代码，当我测试时，显示矢量是两倍快。

Today someone challenged me on this, and provided this code at ideone, which when I tested, showed the vector to be over twice as fast.

StackOverflow的代码是否想让我明白这个明显的差异？我已经经历了这两个代码，他们似乎对我有用，但也许我失去了和他们两个玩这么多。

Do the coders of StackOverflow want to enlighten me on this apparent discrepancy? I've gone over both sets of code, and they seem euqivalent to me, but maybe I'm blind from playing with both of them so much.

（Footnote：这是非常接近我之前的一个问题，但我的代码有几个错误，已解决。 ）

(Footnote: this is very close to one of my previous questions, but my code had several bugs which were addressed. Due to new information/code, I felt this was different enough to justify a separate question. If not, I'll work on merging them.)

推荐答案

我遇到了代码的一些问题（ http://ideone.com/41iKt ）你发布在ideone.com。 （ideone实际上显示向量更快，但是Visual Studio 11开发者预览的本地构建显示 map 更快）。

I see some problems with the the code ( http://ideone.com/41iKt ) you posted on ideone.com. (ideone actually shows vector as faster, but a local build with the Visual Studio 11 Developer Preview shows map faster).

首先，我移动了map变量，并使用它来初始化向量以获得相同的元素排序和唯一，然后我给了 lower_bound 一个自定义比较器，只比较第一，因为这是什么地图将做。在这些更改后，Visual Studio 11显示相同100,000个元素的向量更快（尽管ideone时间不会显着更改）。 http://ideone.com/b3OnH

First I moved the map variable and used it to initialize the vector to get the same element ordering and uniquing, and then I gave lower_bound a custom comparator that only compares first, since that's what map will be doing. After these changes Visual Studio 11 shows the vector as faster for the same 100,000 elements (although the ideone time doesn't change significantly). http://ideone.com/b3OnH

使用 test_size 缩小到8地图还是比较快。这并不奇怪，因为这是算法复杂性的工作原理，所有的函数真正描述运行时间的常数与小N有关。我必须提出 test_size 到大约2700为矢量拉均匀，然后在这个系统上的地图。

With test_size reduced to 8 map is still faster. This isn't surprising because this is the way algorithm complexity works, all the constants in the function that truly describes the run time matter with small N. I have to raise test_size to about 2700 for vector to pull even and then ahead of map on this system.

这篇关于为什么矢量比地图在一个测试中快，但不是其他？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！