python - 最长的 Collat​​z(或 Hailstone)序列优化 - Python 2.7

Question

我制作了一个打印出数字列表的程序，每个数字的步数(根据 Collatz Conjecture )比前一个需要更多的步数:

limit = 1000000000
maximum = 0
known = {}
for num in xrange(2, limit):
    start_num = num
    steps = 0
    while num != 1:
        if num < start_num:
            steps += known[num]
            break;
        if num & 1:
            num = (num*3)+1
            steps += 1
        steps += 1
        num //= 2
    known[start_num] = steps
    if steps > maximum:
        print start_num,"\t",steps
        maximum = steps

我缓存我已知的结果以加速程序。此方法适用于 10 亿的限制，此时我的计算机内存不足 (8GB)。

1. 是否有更有效的方法来缓存结果？
2. 有没有办法进一步优化这个程序？

提前谢谢你。

Answer 1

似乎很难极大地加速 Collat​​z 程序；我知道的最好的程序 are distributed ，在全局数百(数千...)台 PC 上使用空闲周期。

在纯 CPython 中，您可以做一些简单的事情来稍微优化您的程序，尽管速度和空间优化通常是矛盾的:

• 速度:Python 中的计算量大的程序应始终编写为函数，而不是主程序。这是因为局部变量访问明显快于全局变量访问。
• 空间:制作known列表而不是字典需要更少的内存。您正在为每个数字存储一些东西；字典更适合稀疏映射。
• 空格:array.array仍然需要更少的空间 - 虽然比使用列表慢。
• 速度:对于奇数 n , 3*n + 1必然是偶数，因此您可以转到 (3*n + 1)//2 == n + (n >> 1) + 1 将 2 步折叠为 1 步直接。
• 速度:给定最终结果(数字和步数)，您可以向前跳并填写该数字乘以 2 的所有幂的结果。例如，如果 n花了s步骤，然后 2*n将采取s+1 , 4*n将采取s+2 , 8*n将采取s+3 , 等等。

尽管我使用的是 Python 3(在 Python 2 中，您至少需要将 range 更改为 xrange )，但这里有一些包含所有这些建议的代码。请注意，启动时有很长的延迟 - 这是填充大 array 所花费的时间有十亿个 32 位无符号零。

def coll(limit):
    from array import array
    maximum = 0
    known = array("L", (0 for i in range(limit)))
    for num in range(2, limit):
        steps = known[num]
        if steps:
            if steps > maximum:
                print(num, "\t", steps)
                maximum = steps
        else:
            start_num = num
            steps = 0
            while num != 1:
                if num < start_num:
                    steps += known[num]
                    break
                while num & 1:
                    num += (num >> 1) + 1
                    steps += 2
                while num & 1 == 0:
                    num >>= 1
                    steps += 1
            if steps > maximum:
                print(start_num, "\t", steps)
                maximum = steps
            while start_num < limit:
                assert known[start_num] == 0
                known[start_num] = steps
                start_num <<= 1
                steps += 1

coll(1000000000)

获取奇闻趣事

1992 年撰写的一份技术报告提供了多种加速此类搜索的方法:"3x+1 Search Programs", by Leavens and Vermeulen .例如，@Jim Mischel 的“根据先前的峰值进行截断”的想法本质上就是论文的引理 20。

另一个:对于简单的因子 2，请注意您“几乎总是”可以忽略甚至起始数字。为什么:让 s(n)表示达到 1 所需的步数。您正在寻找 s() 值中的新峰值.假设最近的峰值位于 n。 ，并且您正在考虑一个偶数 i与 n < i < 2*n .然后特别i/2 < n , 所以 s(i/2) < s(n) (根据“峰值”的定义，在 n 处达到了新的峰值)。但是s(i) == s(i/2) + 1 , 所以 s(i) <= s(n) : i不可能是一个新的高峰。

因此在 n 处找到一个新峰之后, 您可以跳过所有偶数直到(但不包括)2*n .

论文中还有许多其他有用的想法 - 但它们并不都是那么容易;-)