在过去的几天里，我对研究给定数字的冰雹序列的长度（科拉茨猜想）特别感兴趣（更多的是从算法而不是数学角度）。实现递归算法可能是计算长度的最简单方法，但在我看来，这似乎是对计算时间的不必要浪费。许多序列重叠；以 3 的冰雹序列为例：
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，然后记录该值和关联的序列HashMap 中的长度为一(key,val)对。
我还有以下相当标准的递归算法进行比较：
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: 两种算法~2msn = 100,000：~65ms 用于迭代记录，~75ms 用于递归非记录n = 1,000,000: ~500ms 和 ~900msn = 10,000,000: ~14,000ms 和 ~10,000ms
在较高的值下，我会出现内存错误，所以我无法检查模式是否继续。
所以我的问题是：为什么对于较大的 n 值，日志记录算法突然开始比天真的递归算法花费更长的时间？
编辑：
完全废弃 HashMaps 并选择一个简单的数组结构（以及删除检查值是否在数组中的部分开销）会产生所需的效率：
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 算法会引发内存错误，因此甚至无法进行比较，但考虑到它在较低值下的行为，我觉得它不能很好地比较。