为什么地图会比unordered_map快得多?
-
27-10-2019 - |
题
我实现了一个搜索缓存结果,该结果由State类型的键(一个具有7个短整数的类)和Socre类型的值(一个3 double的类)组成。使用unordered_map至少比map慢20倍。为什么?
编辑:该死!我的哈希函数是 通用标签
我忘记了generaodicetagcode,所以一切都发生了冲突!我希望unordered_map有一个hash_function_quality()函数来报告平均碰撞次数。
解决方案
unordered_map的速度与哈希函数的速度成正比。这绝不是直接的关系。例如,如果您使用最简单的哈希函数: 通用标签
然后,您将得到的是一个行为类似于列表而不是散列容器的集合。所有项目都将映射到一个存储桶,并且您必须遍历整个存储桶,直到找到所需的项目(这可能需要O(N)时间。)
您需要做的是看两件事:
- 您正在使用什么哈希函数?是否需要花费大量的时间来处理?
- 会产生多少次碰撞?也就是说,有多少个唯一元素被映射到相同的哈希值?
其中任何一个都能杀死表演。
其他提示
由于哈希函数,std::unordered_map
对于少数元素通常较慢。它花费的时间是固定的(-ish),但仍然可能要花费大量时间。
另一方面,std::map
比std::unordered_map
简单。访问那里的元素所花费的时间取决于元素的数量,但是随着元素数量的增加而越来越少。与c
相比,std :: map的big-oh因子std::unordered_map
通常也非常小。
通常,除非您有特定的原因使用std::map
,否则最好使用std::unordered_map
而不是std::unordered_map
。如果您没有很多元素,这尤其适用。
unordered_map
在后台使用哈希表,因此哈希执行不佳的最明显原因是因为您有太多冲突。您可以考虑使用其他非默认的哈希函数,该函数将为您的键类型提供更好的结果。
对于
我希望unordered_map有一个 hash_function_quality()函数 报告平均数量 碰撞。
我认为以下功能可能会有所帮助。 通用标签
降低
load_factor
,更好的是哈希函数。