更高效的结构为unordered_map <pair <int,int>,int>

Question

我有大约20,000,000 pair<int, int>,我需要与ints联系.我这样做了unordered_map<pair<int, int>, int>.分析我的算法表明检查条目是否存在

bool exists = myMap[make_pair(a, b)] != NULL

是性能瓶颈.我认为从a中检索这些信息unordered_map会非常快,因为它是O(1).但如果常数很大,则恒定时间可能会很慢......

我的哈希函数是

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.

大新闻

我上传了原始数据,因此您可以看到结构.

Answer 1

你试过用过myMap.find(make_pair(a,b)) != myMap.end()吗？operator[]如果元素不存在,则创建元素.我希望find会更快.