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

Question

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

我决定调查项目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序列中将每个数字存储在地图中,因此您只需要计算一次.为此,我使用了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序列的长度之和(即比第二个算法中的方法调用数更多).

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

Answer 1

我对你的代码做了一些更改，看起来更快，但仍然不是即时的。

一般来说，我试图摆脱不必要的、重复的地图访问。

用 HashMap 替换 TreeMap 将一些 O(log n) 操作更改为 O(1)。您实际上从未使用 TreeMap 的排序属性，而只是使用其 contains 方法。

maybeMax >= maxVal在主循环中向后移动会减少条件为真的次数。

import java.util.HashMap;

public class Test {
  public static HashMap<Long, Integer> tm = new HashMap<Long, Integer>();

  public static void main(String[] args) {
    tm.put((long) 1, 1);
    int maxVal = 1;
    long keyWithMaxVal = 1;
    int maybeMax;
    for (long i = 1000000; i >= 2; 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) {
    Integer boxedValue = tm.get(key);
    if (boxedValue == null) {
      if (key % 2 == 0) {
        int value = 1 + addKey(key / 2);
        tm.put(key, value);
        return value;
      } else {
        int value = 1 + addKey(3 * key + 1);
        tm.put(key, value);
        return value;
      }
    }
    return boxedValue.intValue();
  }
}