我正在 interviewbit.com 上解决竞争性编程问题 我基本上使用 unordered_map 来跟踪访问过的数字。当我使用 operator[] 时,我的代码无法及时执行,但是当我使用 find 时它通过了所有测试。两者应该具有相同的时间复杂度。
我尝试使用 clock() 对这两个代码进行计时,方法是运行它们 10 次并对运行时间进行平均,它们都给出了或多或少相同的时间。我用的是g++ 7.4.0,网站提供的环境是g++ 4.8.4。会不会是这个原因。
int Solution::solve(vector<int> &A) {
unordered_map<long long, int> hashmap;
for(auto a : A)
hashmap[a] = 1;
int res = 0;
for(int i = 0; i < A.size(); ++i){
for(int j = i + 1; j < A.size(); ++j){
// if(hashmap.find((long long)A[i] + A[j]) != hashmap.end())
if(hashmap[(long long)A[i] + A[j]] == 1)
++res;
}
}
return res;
}
问题是在数组中找到其和也存在于数组中的对。当我使用 [] 运算符时,我在大约 900 的数组大小上出现“超出时间限制”。
最佳答案
[]-operator 会比 find 慢的原因有两个:
- []-operator 在 map 上正确调用非常量函数以防止各种优化,例如循环展开。
- 更重要的原因:[] 运算符使用默认值在 map 中创建不存在的元素。 map 将被所有之前不在 map 中的 A[i] + A[j] 对膨胀,并将它们的值设置为 0。这将增加 map 大小,从而增加时间。
由于以下一个或多个原因,我认为您的性能测量显示两个备选方案之间没有差异:
- 输入 vector 太小,影响不大
- A[i] + A[j] 的大多数组合已经在 vector 中,因此 unordered_map 没有膨胀到足以产生差异
- 你没有优化你的代码(-O3 或 -Os)你的代码
关于C++ unordered_map operator[ ] vs unordered_map.find() 性能,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57283444/