为什么Unordered_Map哈希太慢，我的简单数组哈希 [英] Why Unordered_Map hashing is too slow then my simple array hash

问题描述

我说的是连续第三次
我已经解决了 UVa 100 - 3n + 1问题
我首先通过创建一个大小为1000000的数组实现简单哈希，然后将结果存储在该数组中，然后I尝试C ++无序映射的哈希和两者之间的时间差对于同样的输入太大了

这里是我的源代码

我已经尝试粘贴我的代码在这里，但每次破碎，所以我粘在这里对不起：（

这里是
所需的时间1.简单数组
2.简单映射
3.无序映射

所以为什么在无序映射和简单数组之间有太多的时间差我知道简单映射很慢，但差别在于3分钟：（

方案

由于可以和一个散列表交换使用一个数组，肯定数组会快很多。 m [n] 在数组上只是指针运算和取消引用，而在 unordered_map 在桶中查找，并做一些平等比较。另外，你查找索引的方式给你在数组中的大量缓存局部性的好处，将不适用于 unordered_map。我完全希望数组赢得每个

也就是说，你的 unordered_map 实现可以改进很多：

  while（n！= 1）{
 if（m1 [n]！= 0）{
 res + = m1 [n]; 
} 
} 
  

这样做两次查找同一个索引两次。你应该只做一次（你 std :: map btw ...）：

  while（n！= 1）{
 auto it = m1.find（n）; 
 if（it！= m.end（））{
 res + = it-> second; 
} 
} 
  

与您的印刷循环相同：

  if（res< m1 [i]）res = m1 [i] 
  

应为：

  int m1i = m1 [i]; 
 if（res< m1i）res = m1i; 
  

最后，这行是未定义的行为：

  i =（i + j） - （j = i）; 
 ^^^^^^^^^ 
  

修改 j 在第二个表达式中的顺序与第一个表达式中对它的访问无关。

Well I am saying this third consecutive time that I have solved UVa 100 - The 3n + 1 problem I have first implemented simple hash by creating a array of size 1000000 and then I store result in that array, then I tried C++ Unordered Map for hashing and time difference between both of them are too huge for same input

here is my source code

I have tried pasting my code here but every time it shattered so I paste here Sorry :(

here is the time taken by 1. Simple array 2. Simple Map 3. unordered map

So why there is too much time difference between unordered map and simple array. I know simple map is slow but the difference is about 3 min :(

解决方案

Given that you can use an array interchangably with a hash table, definitely the array will be a lot faster. m[n] on an array is just pointer arithmetic and a dereference, versus on an unordered_map involves calculating a hash, looking up in a bucket, and doing some equality comparisons. Also, the way you're looking up your indices gives you massive cache locality benefits in the array which will not apply in the unordered_map. I would fully expect the array to win every time - it just necessarily has to do less work.

That said, your unordered_map implementation could be improved a lot:

while(n != 1) {
    if(m1[n] != 0) {
        res += m1[n];
    }
}

That's doing two lookups for the same index twice. You should do it just once (which you do for std::map btw...):

while (n != 1) {
    auto it = m1.find(n);
    if (it != m.end()) {
        res += it->second;
    }
}

And same for your printing loop:

if (res < m1[i]) res = m1[i];

Should be:

int m1i = m1[i];
if (res < m1i) res = m1i;

And lastly, this line is undefined behavior:

i = ( i + j ) - ( j = i );
                ^^^^^^^^^

The modification of j in the 2nd expression is unsequenced with the respect to the access of it in the first expression.

这篇关于为什么Unordered_Map哈希太慢，我的简单数组哈希的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！