欧拉计划 #14：为什么我的TreeMap算法比暴力算法慢？

Question

背景：数年前我在学校学习了C++和Java，但是过去的9年左右，由于我的先前职业不需要它，我并没有进行太多的编程。

我决定研究一下欧拉计划，以此来提高我的编程能力，并解决问题14，该问题要求找到长度最长的Collatz序列中介于一百万以内的整数。（Collatz序列按照如下方式进行处理：给定一个起始数字，如果该数字是奇数，则将其乘以3再加1；如果该数字是偶数，则将其除以2。这个过程会一直持续到数字达到1。）

我首先使用 brute force 方法解决了这个问题，代码如下所示。

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，因为它会自动按键排序，所以当我遍历for循环时，可以快速检查是否已经插入了键，并且只有在必要时才调用addKey方法添加键。我认为这个算法会快得多。

然而，当我实际运行代码时，惊讶地发现暴力算法瞬间就能得出答案，而递归TreeMap算法花费了更长的时间，大约6秒钟。当我将程序修改为达到500万而不是100万时，差异变得更加明显。我向每个程序中添加了一些代码，以确保第二个程序做的工作比第一个少，的确确定了对于每个键，addKey方法仅被调用一次，而while循环需要迭代的次数等于所有数字Collatz序列的长度之和（即比第二种算法中的方法调用次数更频繁）。

那么，为什么第一个算法比第二个算法快得多？是因为第一个算法中的原始数组需要比第二个算法中的Wrapper对象的TreeMap更少的资源吗？搜索是否已经存在的键的映射比我预期的慢（难道不应该是log时间吗？）？需要大量方法调用的递归方法本质上是较慢的吗？还是我忽略了其他东西？

- nobody

---

递归方法需要大量方法调用，它们本身就比较慢吗？一般而言：是的。递归通常更容易编写和理解，但将其转换为循环可能会显著提高性能。但我认为这并不是执行时间增加的全部原因。 - Turing85

这个问题最好使用动态规划（你的第二个解决方案）来解决，然而，似乎你的递归解决方案并没有完全达到你想要的效果。为什么要使用TreeMap而不是HashMap？你可以在Map中获得常数时间查找，而不是对数时间。 - Andrew Malta

嗯...切换到HashMap确实有所改善，但它仍然比第一个程序慢得明显。我有点生疏，就像我在问题开头解释的那样，所以我可能不记得某些细节，比如HashMap具有恒定的查找时间。 - nobody

另一个需要考虑的问题是，当你完成时，地图中有2168611个条目。因此，尽管您尝试为100万个数字计算Collatz序列，但实际上您已经计算（并存储）了两倍多。 （换句话说，内存膨胀可能是问题所在）。但是您需要进行分析以确保。 - FDinoff

问题不在于优化代码，而是你已经在第一段代码中创建了一个很好的查找结构：不需要创建单独的映射结构，你可以使用你已经构建的数组作为所有小于你正在查找的数字的映射。另外请注意，你使用数组的方式相当无用：你只是在单独的遍历中确定最大值，但是你可以在主循环中轻松跟踪到目前为止的最大值，这将只需要一个整数而不是一百万个。 - M Oehm

Answer 1

除了其他答案中已经提到的原因之外，数组实现的主要原因更快可能是由于它具有很多CPU缓存效应的好处：

1. 您的两个独立的小型紧凑循环将完全适合现代CPU的L0指令缓存（Sandy Bridge可以包含1,536个解码微操作）。顺序运行这两个循环比具有更多指令且不适合该缓存的单个循环要快得多。鉴于第二个循环非常小，其指令很可能已经被预取和解码为微操作，并将适合Loop Block Buffer（28个微操作）。

   ^{来源：hardwaresecrets.com}

2. 数据访问具有很高的引用局部性，在您的第一个和第二个循环中都执行顺序访问。预取器也有所帮助，因为您的访问模式是完全可预测的。

---

关于这两个主题以及更多内容，我想推荐您观看这个出色的“技能广播”：95%的性能取决于干净的代表模型，由Martin Thompson讨论了这些和其他主题的更多细节。

- Alex

Answer 2

这段代码测试了找到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);
  }
}

- SpiderPig

---

你能否尝试将 HashMap 的初始容量设置为预期元素数量的1.34倍？ - jxh

Answer 3

我认为自动装箱和拆箱是问题的根源。即使Java SE 8编程指南也提到了这一点： 结果列表的性能可能很差，因为它在每次获取或设置操作时都会进行装箱或拆箱。它足够快以供偶尔使用，但在性能关键的内部循环中使用它是愚蠢的。

- Turing85

Answer 4

我对你的代码进行了一些修改，现在它似乎更快了，但仍然不是瞬间完成。

总的来说，我试图消除不必要的重复map访问。

将TreeMap替换为HashMap，将一些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();
  }
}

- Patricia Shanahan

Answer 5

正如其他人所指出的那样，你应该使用HashMap而不是TreeMap，以减少插入和检索操作的复杂度。

然而，最佳使用HashMap取决于设置其初始容量。如果你不这样做，一旦插入超过默认容量，HashMap将重新分配更大的表格，并且你的项目最终会被重新散列到新表格中。这将减慢程序的执行速度。

最小的更改应该是：

public static HashMap<Long, Integer> tm = new HashMap<Long, Integer>(1000000, 1.0);

HashMap(int initialCapacity, float loadFactor)
构造一个指定初始容量和负载因子的空HashMap。
_Java文档

在这里，我们声明希望HashMap具有1000000的容量（能够容纳那么多元素）和1.0的负载因子（插入操作必须超过容量的100％才会触发重新散列）。

- jxh

Answer 6

你好，我认为containsKey是导致该结果的原因。

TreeMap的containsKey的时间复杂度为O(log(n))。

https://github.com/benblack86/java-snippets/blob/master/resources/java_collections.pdf

根据http://en.wikipedia.org/wiki/Collatz_conjecture，任何小于1亿的初始数字的最长进展是63,728,127，需要949步。我们将考虑Collatz复杂度为C。因此，在第一个案例中，您有：O(n * C + n) = O( n*(C+1) ) = O(k*n)。而在递归解决方案中：O(n*(log(n) + C * log(n)) ) = O( k * n * log(n))。（我不太确定递归部分，但我确定它大于1，因为在递归函数内部再次调用containsKey）。

- mayo