c++ - 为什么 Unordered_Map 散列比我的简单数组散列太慢

Question

好吧，我连续第三次说我已经解决了UVa 100 - The 3n + 1 problem我首先通过创建一个大小为 1000000 的数组来实现简单哈希，然后我将结果存储在该数组中，然后我尝试使用 C++ Unordered Map 进行哈希处理，并且它们之间的时间差对于相同的输入来说太大了

这是我的源代码

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

这是花费的时间1.简单数组2. 简单 map 3. 无序图

那么为什么unordered map和simple array的时间差太大。我知道简单的 map 很慢，但差异大约是 3 分钟 :(

Answer 1

鉴于您可以将数组与哈希表互换使用，数组肯定会快很多。数组上的 m[n] 只是指针算术和取消引用，而 unordered_map 则涉及计算散列、在存储桶中查找以及进行一些相等性比较。此外，您查找索引的方式为您提供了数组中的大量缓存位置优势，这不适用于 unordered_map。 我完全希望数组每次都能获胜 - 它只是必然有减少工作量。

也就是说，您的 unordered_map 实现可以改进很多:

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

这是对同一个索引进行两次查找。你应该只做一次(你为 std::map 顺便说一句...):

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 的修改是无序的。