java - 内存效率问题(Collat​​z Hailstone 序列)

Question

在过去的几天里(更多是从算法而非数学角度)我对调查给定数字的 Hailstone 序列 (Collatz conjecture) 的长度特别感兴趣。实现递归算法可能是计算长度的最简单方法，但在我看来这是一种不必要的计算时间浪费。许多序列重叠；以 3 的 Hailstone 序列为例:

3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

长度为 7；更具体地说，需要 7 次操作才能达到 1。如果我们再进行 6 次操作:

6 -> 3 -> ...

我们立即注意到我们已经计算过了，所以我们只需添加 3 的序列长度，而不是再次遍历所有这些数字，从而大大减少了计算每个数字的序列长度所需的操作次数。

我尝试使用 HashMap 在 Java 中实现它(考虑到 O(1) 概率获取/放置复杂性，这似乎是合适的):

import java.util.HashMap;

/* NOTE: cache.put(1,0); is called in main to act as the
 * 'base case' of sorts. 
 */

private static HashMap<Long, Long> cache = new HashMap<>();

/* Returns length of sequence, pulling prerecorded value from
 * from cache whenever possible, and saving unrecorded values
 * to the cache.
 */
static long seqLen(long n) {
    long count = 0, m = n;
    while (true) {
        if (cache.containsKey(n)) {
            count += cache.get(n);
            cache.put(m, count);
            return count;
        }
        else if (n % 2 == 0) {
            n /= 2;
        }
        else {
            n = 3*n + 1;
        }
        count++;
    }
}

seqLen 本质上要做的是从一个给定的数字开始，遍历该数字的 Hailstone 序列，直到它遇到一个已经在 cache 中的数字，在这种情况下它会将其添加到 count 的当前值，然后将值和关联的序列长度作为 (key,val) 对记录在 HashMap 中。

我还有以下相当标准的递归算法用于比较:

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

从各方面来看，日志算法应该比朴素的递归方法运行得快很多。然而，在大多数情况下，它根本不会运行得那么快，对于较大的输入，它实际上运行得较慢。运行以下代码产生的时间随着 n 大小的变化而有很大差异:

long n = ... // However many numbers I want to calculate sequence
             // lengths for.

long st = System.nanoTime();
// Iterative logging algorithm
for (long i = 2; i < n; i++) {
    seqLen(i);
}
long et = System.nanoTime();
System.out.printf("HashMap algorithm: %d ms\n", (et - st) / 1000000);

st = System.nanoTime();
// Using recursion without logging values:
for (long i = 2; i < n; i++) {
    recSeqLen(i);
}
et = System.nanoTime();
System.out.printf("Recusive non-logging algorithm: %d ms\n",
                    (et - st) / 1000000);

• n = 1,000:两种算法均为 ~2ms
• n = 100,000:~65ms 用于迭代日志记录，~75ms 用于递归非日志记录
• n = 1,000,000:~500 毫秒和~900 毫秒
• n = 10,000,000:~14,000 毫秒和~10,000 毫秒

在更高的值下我会遇到内存错误，所以我无法检查模式是否继续。

所以我的问题是:为什么对于大的 n 值，日志记录算法突然开始比朴素递归算法花费更长时间？

---

编辑:

完全废弃 HashMap 并选择简单的数组结构(以及删除检查值是否在数组中的部分开销)产生所需的效率:

private static final int CACHE_SIZE = 80000000;
private static long[] cache = new long[CACHE_SIZE];

static long seqLen(long n) {
    int count = 0;
    long m = n;

    do {
        if (n % 2 == 0) {
            n /= 2;
        }
        else {
            n = 3*n + 1;
        }
        count++;
    } while (n > m);

    count += cache[(int)n];
    cache[(int)m] = count;
    return count;
}

迭代整个缓存大小(8000 万)现在只需 3 秒，而使用递归算法需要 93 秒。 HashMap 算法会抛出内存错误，因此它甚至无法进行比较，但考虑到它在较低值时的行为，我感觉它不会很好地进行比较。

Answer 1

即兴发挥，我猜它会花费大量时间重新分配 HashMap 。听起来你是从空开始的，然后不断地往里面加东西。这意味着随着它的大小增加，它将需要分配更大的内存块来存储您的数据，并重新计算所有元素的哈希值，即 O(N)。尝试将大小预先分配给您希望放入其中的大小。参见 https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html进行更多讨论。