Euler项目#14:为什么我的TreeMap算法比蛮力慢？

Question

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

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));

我认为这种方法是低效的，因为它运行算法的次数明显超过了必要的次数。任何一个数，如果是前一个数的Collatz序列的一部分，实际上已经确定了它的序列，所以你最终要计算每一个数的序列，每次它出现在Collatz序列中。

我决定最好把每个数字一出现在一个Collatz序列中就存储在一个地图中，这样你只需要计算一次。为此，我使用了一个TreeMap，其中数字用作键，相关的Collatz序列长度作为值，并使用递归函数将每个数字在Collatz序列中出现后立即插入到映射中。（请参见下面的代码。）

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算法需要更长的时间，大约6秒。当我把我的程序修改到500万而不是100万时，差异变得更加明显。我在每个程序中添加了一些代码，以确保第二个程序比第一个程序做的工作少，实际上，我确定addKey方法只对每个键调用一次，而在第一个程序中，while循环需要迭代的次数等于所有数字Collatz序列的长度之和（即，比第二个算法中方法调用的次数多得多）。

那么，为什么第一种算法比第二种算法快得多呢？是因为第一个算法中的原语数组比第二个算法中的包装器对象的TreeMap需要更少的资源吗？搜索映射以检查键是否已经存在，是否比我预期的要慢（不应该是日志时间吗？）？需要大量方法调用的递归方法本身就慢吗？还是我忽略了什么

Answer 1

这段代码测试为1到500万之间的数字找到最长的collatz序列需要多长时间。它使用三种不同的方法：迭代、递归和将结果存储在哈希图中。

输出如下所示

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

因此，对于散列映射解决方案，程序必须采取的步骤数要少近50倍。尽管如此，它还是慢了3倍多，我认为主要原因是对数字的简单数学运算，如加法、乘法等，比对哈希图的运算要快得多。

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);
  }
}