如何优化Collatz序列代码，使其运算至1百万级别时无处理延迟

以下优化技巧落地后，100万规模的计算在普通消费级CPU上可控制在数秒内完成：

• 记忆化缓存（核心优化）
  绝大多数数的Collatz序列会重复经过相同的中间值，比如所有偶数折半后得到的数、奇数执行3n+1后得到的偶数，几乎都已经被提前计算过。固定上限为100万时，优先用数组做缓存（比字典/哈希表少了哈希计算和冲突处理开销，随机访问性能更高），直接存储每个数对应的序列长度，遇到已经计算过的数直接读取缓存值即可终止当前计算，无需重复走完整序列。
• 合并计算步骤
  奇数执行3n+1后必然是偶数，无需额外做一次奇偶判断，可以直接将两步合并为(3*n +1) // 2，序列长度直接加2，直接减少一半的判断和运算次数。
• 路径复用优化
  计算单个数值的序列长度时，把本次计算路径上所有没被缓存的数值都记录下来，等走到已缓存的节点后，反向把路径上所有小于等于上限的数值的长度都写入缓存，一次计算就能完成多个数值的缓存填充，进一步减少重复计算量。
• 迭代替换递归
  如果你原有代码用递归实现序列长度计算，替换为迭代实现即可消除递归调用开销，同时避免大数计算时出现栈溢出问题。

参考实现片段（Python） #

max_limit = 10 ** 6
# 缓存数组，索引对应数值，值对应序列长度
cache = [0] * (max_limit + 1)
cache[1] = 1
max_len = 1
result_num = 1

for num in range(2, max_limit + 1):
    current = num
    path = []
    # 走到已缓存的数值前持续计算
    while current > max_limit or cache[current] == 0:
        path.append(current)
        if current % 2 == 0:
            current = current // 2
        else:
            # 奇数两步合并计算
            current = (3 * current + 1) // 2
            # 补占位符保证长度计算准确
            path.append(None)
    # 回填路径上的数值缓存
    total_len = cache[current]
    for n in reversed(path):
        total_len += 1
        if n is not None and n <= max_limit:
            cache[n] = total_len
    # 更新最长序列记录
    if cache[num] > max_len:
        max_len = cache[num]
        result_num = num

上述实现跑100万规模在普通笔记本上耗时在2秒以内。

内容的提问来源于stack exchange，提问作者user15464781