java - 欧拉计划 #14 : Why is my TreeMap algorithm slower than brute force?

Question

背景:我几年前在学校里第一次学习 C++ 和 Java，但在过去的 9 年左右时间里我没有做过太多编程，因为我以前的职业不需要它。

我决定研究 Project Euler 以温习我的编程并解决了问题 14，该问题要求找到最长 Collat​​z 序列的 1 到 100 万之间的整数。 (Collat​​z 序列继续进行，给定一个起始数字，将该数字乘以 3，如果是奇数则加 1，如果是偶数则将其减半。该过程一直持续到数字达到 1。)

我首先使用蛮力解决了这个问题，如下面的代码所示。

int n;
long temp; // long is necessary since some Collatz sequences go outside scope of int
int[] n_length = new int[1000000];
    for(n = 0; n < 1000000; n++){
        temp = n + 1;
        n_length[n] = 1;
        while (temp > 1){
            n_length[n]++;
            if (temp % 2 == 0) temp = temp/2;
            else temp = 3*temp + 1;

        }
    }
int max = 0;
    int max_index = 0;
    for (int i = 0; i < 1000000; i++){
        if (n_length[i] > max){
            max = n_length[i];
            max_index = i;
        }
    }
    System.out.println("The number with the longest Collatz sequence is " + (max_index + 1));

我认为这种方法效率低下，因为它运行算法的频率明显高于必要的频率。属于前一个数字的 Collat​​z 序列的任何数字都将有效地确定其序列，因此每次出现在 Collat​​z 序列中时，您最终都会计算每个数字的序列。

我决定最好在每个数字出现在 Collat​​z 序列中时将其存储在 map 中，这样您只需计算一次。为此，我使用了一个 TreeMap，将数字用作键，将关联的 Collat​​z 序列长度用作值，并使用递归函数将每个数字一出现在 Collat​​z 序列中就插入到映射中。 (请参阅下面的代码。)

public static TreeMap<Long, Integer> tm = new TreeMap<Long, Integer>();
public static void main(String[] args) {

    tm.put((long)1, 1);
    int maxVal = 1;
    long keyWithMaxVal = 1;
    int maybeMax;
    for (long i = 2; i <= 1000000; i++){
        if(!(tm.containsKey(i))){
            maybeMax = addKey(i);
            if (maybeMax >= maxVal){
                maxVal = maybeMax;
                keyWithMaxVal = i;
            }
        }
    }
    System.out.println("The number with the longest Collatz sequence is " + keyWithMaxVal + " with length " + maxVal);
}
public static int addKey(long key){

    while (!(tm.containsKey(key))){
        if (key % 2 == 0){
            tm.put(key, 1 +addKey(key/2));
        }
        else{
            tm.put(key, 1 + addKey(3*key + 1));
        }
    }
    return tm.get(key);
}

我使用了 TreeMap，因为它会在输入时自动对键进行排序，因此当我遍历 for 循环时，我可以快速检查键是否已经插入，并避免调用 addKey 方法来添加键，除非我必须这样做。我认为这个算法会快得多。

然而，当我实际运行代码时，我惊讶地发现蛮力算法瞬间得出答案，而递归 TreeMap 算法花费的时间要长得多，大约 6 秒。当我将我的程序修改为 500 万而不是 100 万时，差异变得更加明显。我向每个程序添加了一些代码，以确保第二个程序比第一个程序做的工作少，实际上我确定 addKey 方法只为每个键调用一次，而 while 循环需要迭代的次数在第一个程序中等于所有数字 Collat​​z 序列的长度之和(即比第二个算法中的方法调用次数多得多)。

那么为什么第一个算法比第二个算法快这么多呢？是不是因为第一个算法中的基元数组比第二个算法中的 Wrapper 对象的 TreeMap 需要更少的资源？搜索 map 以检查 key 是否已经存在的速度比我预期的要慢(不应该是记录时间吗？)？需要大量方法调用的递归方法本身就比较慢吗？或者还有其他我忽略的东西

Answer 1

此代码测试为 1 到 500 万之间的数字找到最长的 collat​​z 序列需要多长时间。它使用三种不同的方法:迭代、递归和将结果存储在 HashMap 中。

输出看起来像这样

iterative
time = 2013ms
max n: 3732423, length: 597
number of iterations: 745438133

recursive
time = 2184ms
max n: 3732423, length: 597
number of iterations: 745438133

with hash map
time = 7463ms
max n: 3732423, length: 597
number of iterations: 15865083

因此对于 HashMap 解决方案，程序必须执行的步骤数减少了近 50 倍。尽管如此，它还是慢了 3 倍以上，我认为主要原因是对数字的简单数学运算，例如添加、乘法等操作比 HashMap 上的操作快得多。

import java.util.function.LongUnaryOperator;
import java.util.HashMap;

public class Collatz {
  static int iterations = 0;
  static HashMap<Long, Long> map = new HashMap<>();

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

  static long collatzLength(long n) {
    iterations++;
    int length = 1;
    while(n > 1) {
      iterations++;
      n = nextColl(n);
      length++;
    }
    return length;
  }

  static long collatzLengthMap(long n) {
    iterations++;
    if(n == 1) return 1;
    else return map.computeIfAbsent(n, x -> collatzLengthMap(nextColl(x)) + 1);
  }

  static long collatzLengthRec(long n) {
    iterations++;
    if(n == 1) return 1;
    else return collatzLengthRec(nextColl(n)) + 1;
  }

  static void test(String msg, LongUnaryOperator f) {
    iterations = 0;
    long max = 0, maxN = 0;
    long start = System.nanoTime();
    for(long i = 1; i <= 5000000; i++) {
      long length = f.applyAsLong(i);
      if(length > max) {
        max = length;
        maxN = i;
      }
    }
    long end = System.nanoTime();
    System.out.println(msg);
    System.out.println("time = " + ((end - start)/1000000) + "ms");
    System.out.println("max n: " + maxN + ", length: " + max);
    System.out.println("number of iterations: " + iterations);
    System.out.println();
  }

  public static void main(String[] args) {
    test("iterative", Collatz::collatzLength);
    test("recursive", Collatz::collatzLengthRec);
    test("with hash map", Collatz::collatzLengthMap);
  }
}