无序的地图与矢量

Question

我正在构建一个小的2D游戏引擎.现在我需要存储游戏对象的原型(所有类型的信息).一个容器最多我猜几千个元素都有唯一的键,没有元素将被删除或在第一次加载后添加.键值是一个字符串.

将运行各种线程,并且我需要向每个人发送一个键(或索引)并且具有该访问权限的其他信息(例如用于渲染过程的纹理或用于混合器过程的声音)仅可用于那些线程.

通常我使用向量,因为它们访问已知元素的速度更快.但我发现,如果我使用::at元素访问,无序地图通常也会保持恒定的速度.这将使代码更清晰,也更容易维护,因为我将处理更易理解的人造字符串.

所以问题是,与a vector[n]相比,访问a 与a 之间的速度差异unorderedmap.at("string")与他的收益相比可以忽略不计？

根据我的理解,在程序的不同部分访问各种地图,不同的线程只为我运行"名称"是一个大问题,速度差异不是那么大.但我太缺乏经验,无法确定这一点.虽然我发现有关它的信息似乎我无法理解我是对还是错.

感谢您的时间.

Answer 1

我的问题是通过给定的std :: string类型找到容器上的记录作为密钥访问.考虑只有EXISTS的键(没有找到它们的选项),并且该容器的元素仅在程序开始时生成,之后从未触及.

我有巨大的恐惧无序地图不够快.所以我测试了它,我希望分享结果,希望我不会误解一切.我只是希望能帮助像我这样的人并得到一些反馈,因为最后我是初学者.因此,给定一个随机填充的记录结构,如下所示:

struct The_Mess 
{   
    std::string A_string;
    long double A_ldouble;
    char C[10]; 
    int* intPointer;
    std::vector<unsigned int> A_vector;
    std::string Another_String;
}        

我做了一个无序的地图,给A_string包含记录的密钥:

std::unordered_map<std::string, The_Mess> The_UnOrdMap;

和一个矢量我按A_string值排序(包含键):

std::vector<The_Mess> The_Vector;

还有一个索引向量排序,并用于访问第3方式:

std::vector<std::string> index;

密钥将是一个长度为0-20个字符的随机字符串(我希望最糟糕的情况)包含大写字母和普通字母以及数字或空格.

所以,简而言之,我们的竞争对手是:

1. 无序映射我测量程序执行的时间:

   record = The_UnOrdMap.at( key ); record只是一个The_Mess结构.

2. Sorted Vector测量语句:

   low = std::lower_bound (The_Vector.begin(), The_Vector.end(), key, compare); record = *low;

3. 排序索引向量:

   low2 = std::lower_bound( index.begin(), index.end(), key); indice = low2 - index.begin(); record = The_Vector[indice];

时间以纳秒为单位,是200次迭代的算术平均值.我有一个向量,我在包含所有键的每次迭代中都会进行混乱,并且在每次迭代中我都循环遍历它,并以三种方式查找我在这里的键.这是我的结果:

我认为首字母尖峰是我的测试逻辑的错误(我迭代的表只包含到目前为止生成的密钥,所以它只有1-n个元素).因此,首次进行了200次迭代的1键搜索.2个键的200次迭代第二次搜索等...

无论如何,似乎最好的选择是无序映射,考虑到代码少得多,它更容易实现,并且使整个程序更容易阅读并可能维护/修改.

Answer 2

作为替代方案,您可以考虑使用有序向量,因为向量本身不会被修改.您可以使用STL lower_bound等自己编写实现,或者使用库中的实现(boost :: flat_map).

在这种情况下,Scott Meyers有一篇关于容器性能的博客文章.他做了一些基准测试,结论是a unordered_map可能是一个非常好的选择,很有可能它是最快的选择.如果您有一组受限制的键,您还可以计算最小的最佳散列函数,例如使用gperf

但是,对于这些问题,首要的规则是衡量自己.