哈希图记忆比直接计算答案慢

Question

我一直在尝试 Project Euler 挑战，以帮助提高我对 Java 的了解。特别是，我为 problem 14 编写了以下代码，它要求您找到从 1,000,000 以下的数字开始的最长 Collatz 链。它的工作假设是子链极有可能出现不止一次，并且通过将它们存储在缓存中，不会进行冗余计算。

Collatz.java:

import java.util.HashMap;

public class Collatz {
    private HashMap<Long, Integer> chainCache = new HashMap<Long, Integer>();

    public void initialiseCache() {
        chainCache.put((long) 1, 1);
    }

    private long collatzOp(long n) {
        if(n % 2 == 0) {
            return n/2;
        }
        else {
            return 3*n +1;
        }
    }

    public int collatzChain(long n) {
        if(chainCache.containsKey(n)) {
            return chainCache.get(n);
        }
        else {
            int count = 1 + collatzChain(collatzOp(n));     
            chainCache.put(n, count);
            return count;
        }
    }  
}

ProjectEuler14.java:

public class ProjectEuler14 {
    public static void main(String[] args) {
        Collatz col = new Collatz();
    
        col.initialiseCache();
        long limit = 1000000;
    
        long temp = 0;
        long longestLength = 0;
        long index = 1;
    
        for(long i = 1; i < limit; i++) {
            temp = col.collatzChain(i);
            if(temp > longestLength) {
                longestLength = temp;
                index = i;
            }
        }
        System.out.println(index + " has the longest chain, with length " + longestLength);
    }
}

这行得通。根据 Windows Powershell 的“measure-command”命令，执行大约需要 1708 毫秒（1.708 秒）。

然而，在阅读论坛后，我注意到有些人编写了看似幼稚的代码，从头开始计算每条链，但执行时间似乎比我好得多。我（概念上）取了其中一个答案，并将其翻译成 Java:

天真ProjectEuler14.java:

public class NaiveProjectEuler14 {
    public static void main(String[] args) {
        int longest = 0;
        int numTerms = 0;
        int i;
        long j;

        for (i = 1; i <= 10000000; i++) {
            j = i;
            int currentTerms = 1;

            while (j != 1) {
                currentTerms++;
    
                if (currentTerms > numTerms){
                    numTerms = currentTerms;
                    longest = i;
                }
    
                if (j % 2 == 0){
                    j = j / 2;
                }
                else{
                    j = 3 * j + 1;
                }
            }
        }
        System.out.println("Longest: " + longest + " (" + numTerms + ").");
    }
}

在我的机器上，这也给出了正确的答案，但它给出了 0.502 毫秒 - 是我原来程序速度的三分之一。一开始我觉得可能创建HashMap的开销很小，花费的时间太少，无法得出任何结论。但是，如果我在两个程序中将上限从 1,000,000 增加到 10,000,000，NaiveProjectEuler14 需要 4709 毫秒（4.709 秒），而 ProjectEuler14 需要高达 25324 毫秒（25.324 秒）！

为什么 ProjectEuler14 需要这么长时间？我能理解的唯一解释是在 HashMap 数据结构中存储大量的对会增加巨大的开销，但我不明白为什么会这样。我还尝试记录在程序过程中存储的（键，值）对的数量（1,000,000 的情况下为 2,168,611 对，10,000,000 的情况下为 21,730,849 对）并向 HashMap 构造函数提供略高于该数字的数量，因此它最多只需要调整自身大小一次，但这似乎不会影响执行时间。

有人知道为什么记忆版本慢很多吗？

Answer 1

造成这种不幸的现实有一些原因：

不要使用 containsKey，而是立即获取并检查 null
代码使用了一个额外的方法来调用
地图存储基本类型的包装对象（整数、长整型）
将字节码翻译成机器码的 JIT 编译器可以做更多的计算
缓存不涉及很大的百分比，比如斐波那契

可比较的是

public static void main(String[] args) {
    int longest = 0;
    int numTerms = 0;
    int i;
    long j;

    Map<Long, Integer> map = new HashMap<>();

    for (i = 1; i <= 10000000; i++) {
        j = i;

        Integer terms = map.get(i);
        if (terms != null) {
            continue;
        }
        int currentTerms = 1;

        while (j != 1) {
            currentTerms++;

            if (currentTerms > numTerms){
                numTerms = currentTerms;
                longest = i;
            }

            if (j % 2 == 0){
                j = j / 2;

                // Maybe check the map only here
                Integer m = map.get(j);
                if (m != null) {
                    currentTerms += m;
                    break;
                }
            }
            else{
                j = 3 * j + 1;
            }
        }
        map.put(j, currentTerms);
    }
    System.out.println("Longest: " + longest + " (" + numTerms + ").");
}

这并没有真正做到足够的记忆。对于不检查 3*j+1 的增加参数，会稍微减少未命中（但也可能会跳过 meoized 值）。

记忆来自于每次调用的大量计算。如果函数由于深度递归而不是计算而花费很长时间，则每次函数调用的记忆开销会产生负面影响。

哈希图记忆比直接计算答案慢

Hashmap memoization slower than directly computing the answer

java

performance

hashmap

memoization