如何提升验证考拉兹猜想的Python代码运行速度？

以下是针对你的考拉兹猜想验证代码的效率提升建议，结合代码优化细节：

核心优化点 #

1. 缓存已验证结果，避免重复计算 #

考拉兹链中大量数字会重复出现，处理大数字时必然会遇到更小的已验证数字。用字典缓存所有已确认能归约到1的数字，每次计算前先查询缓存，直接跳过重复计算：

collatz_cache = {1: True}

2. 合并奇数处理的连续步骤 #

奇数执行3n+1后必然是偶数，可以直接合并两步为(3n+1) // 2，减少循环次数：

# 替代原奇数分支的代码
i = (3 * i + 1) // 2

3. 只遍历奇数，跳过偶数冗余检查 #

所有偶数最终都会归约到奇数，因此可以直接跳过偶数遍历，只处理奇数。对于起始的偶数，先除以2直到得到奇数，再验证该奇数的链：

# 处理初始数字，先归约到奇数
while i % 2 == 0:
    i = i // 2

4. 移除冗余代码与IO操作 #

原代码中的func函数无实际作用，频繁的print会大幅拖慢速度。只保留必要的进度输出，或者批量输出：

# 替代原进度打印逻辑，每10000个数字打印一次
if data % 10000 == 0:
    print(f"已验证 {data} 个数字，当前处理到 {num}")

5. 用位运算替代算术运算 #

Python中位运算比取模、除法更快，比如：

• 判断偶数：i & 1 == 0（替代i % 2 == 0）
• 除以2：i >> 1（替代i // 2）

6. 并行计算利用多核CPU #

每个数字的验证独立，可以用多进程并行处理，充分利用CPU资源：

from concurrent.futures import ProcessPoolExecutor

def check_collatz(n):
    # 单个数字的验证逻辑，包含缓存查询
    while n != 1 and n not in collatz_cache:
        if n & 1 == 0:
            n = n >> 1
        else:
            n = (3 * n + 1) >> 1
    return n == 1 or collatz_cache.get(n, False)

# 并行遍历处理
with ProcessPoolExecutor() as executor:
    for result, num in zip(executor.map(check_collatz, infinity()), infinity()):
        if not result:
            print(f"找到反例：{num}")
            break

优化后的完整代码示例 #

collatz_cache = {1: True}

def infinity():
    n = 295147905179352825856  # 2^68
    while True:
        yield n
        n += 1

def check_collatz(num):
    n = num
    # 先归约到奇数
    while n & 1 == 0:
        n = n >> 1
    # 检查缓存或计算
    while n != 1 and n not in collatz_cache:
        if n & 1 == 1:
            n = (3 * n + 1) >> 1
        else:
            n = n >> 1
    # 缓存所有经过的数字，避免后续重复计算
    current = num
    while current not in collatz_cache:
        collatz_cache[current] = True
        if current & 1 == 0:
            current = current >> 1
        else:
            current = (3 * current + 1) >> 1
    return True

def main_func():
    data = 0
    check = 0
    for num in infinity():
        data += 1
        if check_collatz(num):
            if data == 100000:
                data = 0
                check += 1
                print(f"已完成 {check * 100000} 个数字验证，当前数字：{num}")
        else:
            print(f"发现反例：{num}")
            break

if __name__ == "__main__":
    main_func()

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