最长的 Collatz（或 Hailstone）序列优化 - Python 2.7
Longest Collatz (or Hailstone) sequence optimization - Python 2.7
我制作了一个程序，打印出一个数字列表，每个数字的步数（根据 Collatz Conjecture）达到 1 所需的步数比前一个多：
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)。
- 是否有更有效的方法来缓存结果？
- 有没有办法进一步优化这个程序？
提前致谢。
似乎天生就很难极大地加速 Collatz 程序；我所知道的最好的程序 are distributed，在全球数百（数千 ...）台 PC 上使用空闲周期。
在纯 CPython 中，您可以做一些简单的事情来优化您的程序，尽管速度和 space 优化通常是不一致的：
- Speed：Python 中的计算量大的程序应始终编写为函数，而不是主程序。那是因为局部变量访问明显快于全局变量访问。
- Space：使
known 成为一个列表而不是一个字典需要更少的内存。您正在为每个数字存储一些东西；字典更适合稀疏映射。
- Space：
array.array 仍然需要更少的 space - 虽然比使用列表慢。
- 速度：对于奇数
n，3*n + 1必然是偶数，所以你可以通过转到[=15将2步折叠成1步=]直接。
- 速度：给定最终结果（数字和步数），您可以跳到前面并填写该数字乘以 2 的所有次方的结果。例如，如果
n 走了 s 步，然后 2*n 将走 s+1，4*n 将走 s+2，8*n 将走 [=23] =]，等等。
尽管我使用的是 Python 3（在 Python 2 中，您至少要将 range 更改为 [=25，但这是包含所有这些建议的一些代码=]).请注意，启动时有很长的延迟 - 这是用十亿个 32 位无符号零填充大 array 所花费的时间。
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 的 "cut off based on previous peaks" 想法本质上是论文的引理 20.
另一个：对于简单的因子 2，请注意您可以 "almost always" 忽略甚至起始数字。为什么：让 s(n) 表示达到 1 所需的步数。您正在寻找 s() 值中的新峰值。假设在 n 处发现了最近的峰值，并且您正在考虑 i 和 n < i < 2*n 的偶数整数。然后特别是 i/2 < n，所以 s(i/2) < s(n)（根据 "peak" 的定义，在 n 处达到了新的峰值）。但是s(i) == s(i/2) + 1，所以s(i) <= s(n)：i不可能是新的高峰
因此在 n 处找到新峰后，您可以跳过所有偶数（但不包括）2*n。
论文中还有许多其他有用的想法 - 但它们并不都是 容易的 ;-)
你真的只需要缓存奇数。在你的程序中考虑当你开始处理一个数字时会发生什么。
如果您使用起始编号 X 并执行 mod 4，您最终会遇到以下四种情况之一：
- 0 或 2：重复除以 2 最终会得到一个小于 X 的奇数。您已缓存该值。所以你可以只计算除以 2 的次数，将其添加到缓存值，你就得到了序列长度。
- 1: (3x+1)/2 会得到一个偶数，再除以 2 会得到一个小于 X 的数。如果结果是奇数，那么你已经有了缓存值, 所以你可以只加 3。如果结果是偶数，重复除以2，直到得到一个奇数（你已经缓存了），将缓存的值加上3和除以2的次数，就得到了序列长度[=47] =]
- 3：进行标准的 Collatz 序列计算，直到得到一个小于起始数字的数字。然后你要么缓存了这个值，要么这个数字是偶数，你重复除以 2 直到你得到一个奇数。
这可能会稍微减慢您的程序，因为您有更多的 2 除数，但它会使您的缓存容量翻倍。
您可以通过仅保存 x mod 4 == 3 处数字的序列长度来再次将缓存容量加倍，但代价是更多的处理时间。
那些只会让您线性增加缓存 space。您真正需要的是一种整理缓存的方法，这样您就不必保存那么多结果。以一些处理时间为代价，您只需要缓存产生迄今为止找到的最长序列的数字。
考虑一下，当您计算 27 有 111 步时，您已经节省了：
starting value, steps
1, 0
2, 1
3, 7
6, 8
7, 16
9, 19
18, 20
25, 23
27, 111
所以当你看到28时，你除以2得到14。搜索你的缓存，你看到14到1的步数不能超过19（因为没有数字小于18需要超过 19 个步骤）。所以最大可能的序列长度是20。但是你已经有最大的111。所以你可以停止。
这可能会花费您更多的处理时间，但会大大扩展您的缓存。您只有 44 个条目，一直到 837799。请参阅 https://oeis.org/A006877。
有趣的是，如果您对这些数字绘制对数散点图，您会得到非常接近直线的近似值。参见 https://oeis.org/A006877/graph。
您可以通过保留第二个缓存来组合方法，该缓存告诉您，对于大于当前最大值的数字，需要多少步才能使该数字低于当前最大值。所以在上面的例子中，27 是当前的最大值，你会为数字 35 存储 26，因为它需要六次操作（106、53、160、80、40、20）才能得到 35 到 20。 table 告诉您最多需要 20 步才能达到 1，因此最多可能有 26 步。因此，如果任何其他值减少到 35，则将当前步数添加到 26，如果该数字小于 111，则您知道您不可能使用此数字获得新的最大值。如果大于111，则需要继续计算整个数列。
每当找到新的最大值时，将生成它的数字添加到第一个缓存，并清除第二个缓存。
这比缓存每个值的结果要慢（我的直觉是在最坏的情况下它可能会加倍你的处理时间），但它会大大扩展你的范围。
这里的关键是扩大范围将以牺牲一些速度为代价。这是一个常见的权衡。正如我在上面指出的，您可以做很多事情来保存每第 n 个项目，这将为您提供更大的缓存。所以如果你每 4 个值保存一次，你的缓存实际上是你保存每个值的 4 倍。但是你很快就达到了 returns 减少的程度。也就是说，比原始缓存大 10 倍的缓存并不比 9 倍缓存大很多。
我的建议实质上是以一些处理时间为代价，使缓存呈指数级增长 space。但这不应该是处理时间的巨大增加，因为在最坏的情况下，下一个最大值的数字将是前一个最大值的两倍。 （想想 27，有 111 步，54，有 112 步。）它需要更多的代码来维护，但它应该扩展你的范围，目前只有 30 位，远远超过 40 位。
我制作了一个程序，打印出一个数字列表，每个数字的步数（根据 Collatz Conjecture）达到 1 所需的步数比前一个多：
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)。
- 是否有更有效的方法来缓存结果？
- 有没有办法进一步优化这个程序？
提前致谢。
似乎天生就很难极大地加速 Collatz 程序；我所知道的最好的程序 are distributed，在全球数百（数千 ...）台 PC 上使用空闲周期。
在纯 CPython 中，您可以做一些简单的事情来优化您的程序，尽管速度和 space 优化通常是不一致的：
- Speed：Python 中的计算量大的程序应始终编写为函数，而不是主程序。那是因为局部变量访问明显快于全局变量访问。
- Space：使
known成为一个列表而不是一个字典需要更少的内存。您正在为每个数字存储一些东西；字典更适合稀疏映射。 - Space：
array.array仍然需要更少的 space - 虽然比使用列表慢。 - 速度：对于奇数
n，3*n + 1必然是偶数，所以你可以通过转到[=15将2步折叠成1步=]直接。 - 速度：给定最终结果（数字和步数），您可以跳到前面并填写该数字乘以 2 的所有次方的结果。例如，如果
n走了s步，然后2*n将走s+1，4*n将走s+2，8*n将走 [=23] =]，等等。
尽管我使用的是 Python 3（在 Python 2 中，您至少要将 range 更改为 [=25，但这是包含所有这些建议的一些代码=]).请注意，启动时有很长的延迟 - 这是用十亿个 32 位无符号零填充大 array 所花费的时间。
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 的 "cut off based on previous peaks" 想法本质上是论文的引理 20.
另一个：对于简单的因子 2，请注意您可以 "almost always" 忽略甚至起始数字。为什么：让 s(n) 表示达到 1 所需的步数。您正在寻找 s() 值中的新峰值。假设在 n 处发现了最近的峰值，并且您正在考虑 i 和 n < i < 2*n 的偶数整数。然后特别是 i/2 < n，所以 s(i/2) < s(n)（根据 "peak" 的定义，在 n 处达到了新的峰值）。但是s(i) == s(i/2) + 1，所以s(i) <= s(n)：i不可能是新的高峰
因此在 n 处找到新峰后，您可以跳过所有偶数（但不包括）2*n。
论文中还有许多其他有用的想法 - 但它们并不都是 容易的 ;-)
你真的只需要缓存奇数。在你的程序中考虑当你开始处理一个数字时会发生什么。
如果您使用起始编号 X 并执行 mod 4，您最终会遇到以下四种情况之一：
- 0 或 2：重复除以 2 最终会得到一个小于 X 的奇数。您已缓存该值。所以你可以只计算除以 2 的次数，将其添加到缓存值，你就得到了序列长度。
- 1: (3x+1)/2 会得到一个偶数，再除以 2 会得到一个小于 X 的数。如果结果是奇数，那么你已经有了缓存值, 所以你可以只加 3。如果结果是偶数，重复除以2，直到得到一个奇数（你已经缓存了），将缓存的值加上3和除以2的次数，就得到了序列长度[=47] =]
- 3：进行标准的 Collatz 序列计算，直到得到一个小于起始数字的数字。然后你要么缓存了这个值，要么这个数字是偶数，你重复除以 2 直到你得到一个奇数。
这可能会稍微减慢您的程序，因为您有更多的 2 除数，但它会使您的缓存容量翻倍。
您可以通过仅保存 x mod 4 == 3 处数字的序列长度来再次将缓存容量加倍，但代价是更多的处理时间。
那些只会让您线性增加缓存 space。您真正需要的是一种整理缓存的方法，这样您就不必保存那么多结果。以一些处理时间为代价，您只需要缓存产生迄今为止找到的最长序列的数字。
考虑一下，当您计算 27 有 111 步时，您已经节省了：
starting value, steps
1, 0
2, 1
3, 7
6, 8
7, 16
9, 19
18, 20
25, 23
27, 111
所以当你看到28时，你除以2得到14。搜索你的缓存，你看到14到1的步数不能超过19（因为没有数字小于18需要超过 19 个步骤）。所以最大可能的序列长度是20。但是你已经有最大的111。所以你可以停止。
这可能会花费您更多的处理时间，但会大大扩展您的缓存。您只有 44 个条目，一直到 837799。请参阅 https://oeis.org/A006877。
有趣的是，如果您对这些数字绘制对数散点图，您会得到非常接近直线的近似值。参见 https://oeis.org/A006877/graph。
您可以通过保留第二个缓存来组合方法，该缓存告诉您，对于大于当前最大值的数字，需要多少步才能使该数字低于当前最大值。所以在上面的例子中，27 是当前的最大值，你会为数字 35 存储 26，因为它需要六次操作（106、53、160、80、40、20）才能得到 35 到 20。 table 告诉您最多需要 20 步才能达到 1，因此最多可能有 26 步。因此，如果任何其他值减少到 35，则将当前步数添加到 26，如果该数字小于 111，则您知道您不可能使用此数字获得新的最大值。如果大于111，则需要继续计算整个数列。
每当找到新的最大值时，将生成它的数字添加到第一个缓存，并清除第二个缓存。
这比缓存每个值的结果要慢（我的直觉是在最坏的情况下它可能会加倍你的处理时间），但它会大大扩展你的范围。
这里的关键是扩大范围将以牺牲一些速度为代价。这是一个常见的权衡。正如我在上面指出的，您可以做很多事情来保存每第 n 个项目，这将为您提供更大的缓存。所以如果你每 4 个值保存一次，你的缓存实际上是你保存每个值的 4 倍。但是你很快就达到了 returns 减少的程度。也就是说，比原始缓存大 10 倍的缓存并不比 9 倍缓存大很多。
我的建议实质上是以一些处理时间为代价，使缓存呈指数级增长 space。但这不应该是处理时间的巨大增加，因为在最坏的情况下，下一个最大值的数字将是前一个最大值的两倍。 （想想 27，有 111 步，54，有 112 步。）它需要更多的代码来维护，但它应该扩展你的范围，目前只有 30 位，远远超过 40 位。