c++ - C++ unordered_map operator[ ] vs unordered_map.find() 性能
问题描述
我在 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 时出现“超出时间限制”。
解决方案
[] 运算符比 find 慢的原因有两个:
- [] 运算符在地图上调用非常量函数,以正确防止各种优化,例如循环展开。
- 更重要的原因:[] 运算符使用其默认值在地图中创建不存在的元素。地图将因之前不在地图中的所有 A[i] + A[j] 对而膨胀,并将其值设置为 0。这将增加地图大小,从而增加时间。
我认为由于以下一个或多个原因,您的性能测量显示两种选择之间没有区别:
- 输入向量太小无法产生影响
- A[i] + A[j] 的大多数组合已经在向量中,因此 unordered_map 不够臃肿,无法产生影响
- 您没有优化您的代码(-O3 或 -Os)您的代码
推荐阅读
- python - 使用 Google Colaboratory 时图表不显示
- javascript - 更新节点中的对象值
- scope - 如何在 Chrome Dev Tools 的全局范围内设置断点?
- rust - 不能将 `self.blocks` 借为可变的,因为它也被借为不可变的
- java - 负数除法得到的余数
- jquery - 选择选择 - 注入动态选项作为第一个选择选项
- laravel - 验证请求中的数据失败
- javascript - 在 Shopify 网页中创建简单的尺寸转换脚本
- c++ - c++- 数字 100 的阶乘
- flutter - 如何从 inAppWeview Flutter 中的 webVew 按钮操作接收值