python递归内存不足

Question

当这段代码运行时，OSX 通知我应用程序内存不足并暂停应用程序。 Python 使用的空间量很快就突破了 10 GB。这段代码永远不会达到 Python 的最大递归级别，它应该只会达到 525 最坏的情况，但由于缓存它应该小得多。我有一种感觉，列表链在递归的每一层都被复制，但它似乎是一个全局变量，应该在每次调用 collat​​z() 时共享。我在 stackoverflow 上寻找过类似的问题，但没有找到相同的问题。

# The following iterative sequence is defined for the set of positive integers:
#  n = n/2  (n is even)
#    = 3n+1 (n is odd)
# Using the rule above and starting with 13, we generate the following sequence:
#  13,40,20,10,5,16,8,4,2,1
# It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 
#  terms. Although it has not been proved yet (Collatz Problem), it is thought that
#  all starting numbers finish at 1.
# Which starting number, under one million, produces the longest chain?
# Comments: I'm using dynamic programming to avoid computing the same values over and over
#            again.

lim = 1000000
chain = [1,1]
maxL = 0

def collatz(i):
   if i >= len(chain): chain.extend([None]*(i-len(chain)+1))
   if chain[i] == None: chain[i] = 1 + collatz(i/2 if i%2==0 else 3*i+1)
   return chain[i]

for i in range(1, lim): 
   maxL = i if (collatz(i) > chain[maxL]) else maxL 
   print i, chain[maxL]
print "collatz chain of {} is {} terms long.".format(maxL, collatz(maxL))

编辑:在这里查看我的工作词典实现:https://stackoverflow.com/a/20229855/1084773 .

Answer 1

要查看您的内存错误，请使用 limit = 100 运行您的代码，然后打印出链。

也许您想序列化您的递归代码:

lengths = {1: 1}

def collatz(i):
    i0 = i
    acc = 0
    while True:
        if i in lengths:
            lengths[i0] = acc + lengths[i]
            return acc + lengths[i]
        acc += 1
        i = (i * 3 + 1) if i % 2 else i // 2

longest = 1
for i in range(1, 1000000):
    c = collatz(i)
    if c > longest:
        longest = c
        print(i, c)

这当然可以在很多方面进行优化，但它会在 4 秒内产生预期的结果。

---

编辑:

您的方法创建了一个列表，其中包含曾经达到的最高任期的长度。对于 limit = 100，这是 9232。这不是那么多。但是对于 limit = 1000000，它是 56991483520(从 704511 开始的链)，这是一个相当大的数字。如果它只是一个基于 int32 的数组，这已经是 212 GB 的内存，而实际上它不止于此。

---

Here the troublesome chain: 704511, 2113534, 1056767, 3170302, 1585151, 4755454, 2377727, 7133182, 3566591, 10699774, 5349887, 16049662, 8024831, 24074494, 12037247, 36111742, 18055871, 54167614, 27083807, 81251422, 40625711, 121877134, 60938567, 182815702, 91407851, 274223554, 137111777, 411335332, 205667666, 102833833, 308501500, 154250750, 77125375, 231376126, 115688063, 347064190, 173532095, 520596286, 260298143, 780894430, 390447215, 1171341646, 585670823, 1757012470, 878506235, 2635518706, 1317759353, 3953278060, 1976639030, 988319515, 2964958546, 1482479273, 4447437820, 2223718910, 1111859455, 3335578366, 1667789183, 5003367550, 2501683775, 7505051326, 3752525663, 11257576990, 5628788495, 16886365486, 8443182743, 25329548230, 12664774115, 37994322346, 18997161173, 56991483520 , 28495741760, 14247870880, 7123935440, 3561967720, 1780983860, 890491930, 445245965, 1335737896, 667868948, 333934474, 166967237, 500901712, 250450856, 125225428, 62612714, 31306357, 939 19072, 46959536, 23479768, 11739884, 5869942, 2934971, 8804914, 4402457, 13207372, 6603686, 3301843, 9905530, 4952765, 14858296, 7429148, 3714574, 1857287, 5571862, 2785931, 8357794, 4178897, 12536692, 6268346, 3134173, 9402520, 4701260, 2350630, 1175315, 3525946, 1762973, 5288920, 2644460, 1322230, 661115, 1983346, 991673, 2975020, 1487510, 743755, 2231266, 1115633, 3346900, 1673450, 836725, 2510176, 1255088, 627544, 313772, 156886, 78443, 235330, 117665, 352996, 176498, 88249, 264748, 132374, 66187, 198562, 99281, 297844, 148922, 74461, 223384, 111692, 55846, 27923, 83770, 41885, 125656, 62828, 31414, 15707, 47122, 23561, 70684, 35342, 17671, 53014, 26507, 79522, 39761, 119284, 59642, 29821, 89464, 44732, 22366, 11183, 33550, 16775, 50326, 25163, 75490, 37745, 113236, 56618, 28309, 84928, 42464, 21232, 10616, 5308, 2654, 1327, 3982, 1991, 5974, 2987, 8962, 4481, 13444, 6722, 3361, 10084, 5042, 2521, 7564, 3782, 1891, 5674, 2837, 8512, 4256, 2128, 1064, 532, 266, 133, 400, 200, 100, 5 0, 25, 76, 38, 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

---

使用你确切的递归想法，但使用字典(稀疏的)而不是列表(运行没有问题):

lengths = {1: 1}

def collatz(i):
    if i in lengths: return lengths [i]
    j = (i * 3 + 1) if i % 2 else i // 2
    c = collatz (j) + 1
    lengths [i] = c
    return c

longest = 1
for i in range(1, 1000000):
    c = collatz(i)
    if c > longest:
        longest = c
        print(i, c)