这是因为两次查找而不是一次查找速度慢吗？
这是因为两次查找而不是一次查找速度慢吗？
提问于 2014-09-20 15:16:27
当我想确保要使用的条目存在时，我通常会这样做。
#include <unordered_map>
struct type { int member; };
std::unordered_map<type> map;
if (map.find(key) != map.end())
map[key].member = 42;但是，我认为它在哈希映射中对key执行两次查找。这就隐藏了查找。
#include <unordered_map>
struct type { int member; };
std::unordered_map<type> map;
auto find = map.find(key);
if (find != map.end())
find->second.member = 42;第一种选择感觉更有表现力。真的慢了吗？
回答 5
Stack Overflow用户
回答已采纳
发布于 2014-09-20 15:21:55
是的，因为您搜索了两次密钥：map[key]搜索的密钥与map.find完全一样，您丢弃了结果。
这就像打开抽屉看是否有一个给定的物体，说“啊是的！”然后关闭抽屉，然后再打开它，并研究对象来改变它。
第二个代码打开抽屉，搜索一个对象并修改它。
可以进行编译器优化，以避免重复搜索，或者可以在恒定时间内减少搜索，还可以进行编译器优化，以避免将auto find变量存储在内存中(可以是CPU寄存器，因为它的使用非常本地)。
整个问题实际上将减少两次哈希计算的时间(并在哈希冲突情况下遍历最终的映射槽)和访问额外变量的时间：
2*H < H+M意思是H < M。如果M是一个寄存器，H不是平凡的，那么H很难小于M。
Stack Overflow用户
发布于 2014-09-20 15:21:58
它可能会慢一些，但它可能不会(您现在正在“加速”中进行额外的编写)，但是在编写代码时真的不应该担心这么小的优化。写出清晰的表达代码。如果你的程序真的太慢了，在上面运行分析工具，找出你的瓶颈。如果这段代码实际上是一个真正的问题，那么只需尝试“加速”，看看它是否重要。
Stack Overflow用户
发布于 2014-09-20 17:54:04
是的，它可能会慢一些，但可能不会明显地慢下来。还需要做一些额外的工作：
- 哈希可能会计算两次，除非您有足够聪明的编译器，否则使用供应商扩展(如纯正或康斯特 )或使用类似的方法。注意，如果散列很简单，而且编译器知道它的代码，那么现在大多数编译器可能都足够聪明了。
- 需要第二次找到桶的位置(除非编译器会注意到这是相同的散列，因此不需要重新计算)
- 需要执行冲突列表的遍历(或类似的方法，取决于冲突的分辨率)。再次-足够聪明的编译器可能会注意到我们正在做两次，我们实际上没有修改任何东西，我们现在可能有这样的编译器，但我不能100%确定我们是否存在。即使它们不是，它们也是缓存的读，并且它们可能不会带来任何重大成本(例如，与散列或漏读相比)。不详细讨论处理器体系结构，L1$ read在i7 (内存中的数据可能是错误的)上延迟4个周期，处理器在等待时可能会做其他工作。
因此，总结一下，如果：
- 您的哈希函数很昂贵(例如，它需要接受字符串的散列)。
- 编译器不够聪明，无法推断哈希函数不会修改对象并返回相同的值。
- 这是内环的代码。
那你可能会看到不同之处。
作为最后一个词-它可能不会重要，这不是很大的架构差异，而是5s优化。因此，编写任何您认为更容易维护和重新讨论的问题，当分析器将显示该功能会导致减速。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/25950207
复制相关文章
相似问题
腾讯云开发者
