我有大约20,000,000pair<int, int>需要与ints关联。我这样做了unordered_map<pair<int, int>, int>。对我的算法进行性能分析表明，检查条目是否存在
bool exists = myMap[make_pair(a, b)] != NULL
是性能瓶颈。我以为从O（1）检索信息unordered_map非常快。但是如果常数很大，常数时间可能会变慢...
我的哈希函数是
template <>
struct tr1::hash<pair<int, int> > {
public:
size_t operator()(pair<int, int> x) const throw() {
size_t h = x.first * 1 + x.second * 100000;
return h;
}
};
您知道我的问题有更好的数据结构吗？
显然，我不能仅将信息存储在矩阵中，因此内存容量无法容纳任何现有计算机。我所知道的所有分布myMap[make_pair(a, a)]都不存在a。并且所有ints都在从0到大约20,000,000的连续范围内。
可以将其视为一个稀疏的20,000,000x20,000,000矩阵，其中包含大约20,000,000个条目，但永远不在主对角线上。
将一vector<pair<int, int>>*（阵列Ñ预期的条目）要快？查找a将是微不足道的（只是数组的索引），然后我将遍历向量，将对的first值与进行比较b。
我上传了原始数据，因此您可以看到结构。
作为suggestet，我去一个vector<pair<int, int>>*有ñ条目。比大约快40％unordered_map。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句