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

Question

我制作了一个程序,打印出一个数字列表,每个数字都有一个步骤(根据Collat​​z猜想)需要比前一个更多的步骤:

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计划; 我所知道的最好的程序是使用全球数百(数千)台PC上的空闲周期进行分发的.

虽然速度和空间优化通常不一致,但是在纯CPython中可以使用一些简单的方法来优化程序.

• 速度:Python中计算量很大的程序应始终作为函数编写,而不是作为主程序编写.那是因为局部变量访问明显快于全局变量访问.
• 空间:制作known列表而不是字典需要的内存要少得多.你要为每个号码存储一些东西; dicts更适合稀疏映射.
• 空间: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)

获得GONZO

1992年写的一份技术报告提供了许多方法来加速这种搜索: "3x + 1搜索程序",由Leavens和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.

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