Python MemoryError发生大循环

Question

我正在尝试创建一个脚本来为我在Project Euler上解决问题，但是它一直返回MemoryError。我完全不知道为什么。

divisible = True

possible = dict()

for i in xrange(1, 100000000):

    for n in xrange(1, 21):

        if i%n != 0:

            divisible = False

        else:

            if i in possible:

                possible[i].append(n)

            else:

                possible[i] = [n]

        if len(possible[i]) == 20:

            print i

            break

Python似乎认为它发生在这条线上 possible[i] = [n]

Answer 1

问题出在你的线上if len(possible[i]) == 20:你的意思是说if len(possible) == 20:照原样，您的代码将继续运行-大概是因为循环计数如此之大，所以某些堆栈已填满...另外-尽管我不确定您要实现的目标，但是您的break命令位于最内层的循环中-因此您会中断该循环，然后再次执行此操作...并且由于长度仅恰好是20一次，因此您仍然被卡住。检查您的逻辑。例如，对代码进行以下小的更改将产生有用的输出（尽管我不知道它是否对您有用...但是它可能会给您一些想法）：divisible = Truepossible = dict()for i in xrange(1, 100000000):&nbsp; &nbsp; for n in xrange(1, 21):&nbsp; &nbsp; &nbsp; &nbsp; if i%n != 0:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; divisible = False&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if i in possible:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; possible[i].append(n)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; possible[i] = [n]&nbsp; &nbsp; if len(possible) == 20:&nbsp; &nbsp; &nbsp; &nbsp; print i&nbsp; &nbsp; &nbsp; &nbsp; break&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; print i, possible[i]输出：1 [1]2 [1, 2]3 [1, 3]4 [1, 2, 4]5 [1, 5]6 [1, 2, 3, 6]7 [1, 7]8 [1, 2, 4, 8]9 [1, 3, 9]10 [1, 2, 5, 10]11 [1, 11]12 [1, 2, 3, 4, 6, 12]13 [1, 13]14 [1, 2, 7, 14]15 [1, 3, 5, 15]16 [1, 2, 4, 8, 16]17 [1, 17]18 [1, 2, 3, 6, 9, 18]19 [1, 19]20编辑代码时要更仔细，我想您想做的是找到正好有20个因数的数字。因此你的情况是正确的。问题在于您还存储了所有其他术语-这是非常大量的列表。如果您只在最后一个数字之后（毕竟唯一的输出i就在休息之前），那么您真的不需要保留所有其他术语。下面的代码就是这样做的-它在我的计算机上运行良好，现在占用了最长的时间约20 MB的内存（但目前还没有答案...）divisible = Truepossible = [];biggest = 0;bigN = 100000000;for i in xrange(1, bigN):&nbsp; &nbsp; for n in xrange(1, 21):&nbsp; &nbsp; &nbsp; &nbsp; if i%n != 0:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; divisible = False&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if len(possible) > 0:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; possible.append(n)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; possible = [n]&nbsp; &nbsp; if len(possible) >= 20:&nbsp; &nbsp; &nbsp; &nbsp; print i&nbsp; &nbsp; &nbsp; &nbsp; print possible&nbsp; &nbsp; &nbsp; &nbsp; break&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; if bigN < 1000:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; print i, possible; # handy for debugging&nbsp; &nbsp; &nbsp; &nbsp; if biggest < len(possible):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; biggest = len(possible);&nbsp; &nbsp; &nbsp; &nbsp; possible = []计算您正在做的事情的“手动”方法是找到所有1到20的数字的素数；计算每个中出现质数的最大次数；并拿走他们的产品：2&nbsp; = 23&nbsp; =&nbsp; &nbsp; &nbsp;34&nbsp; = 225&nbsp; =&nbsp; &nbsp; &nbsp; &nbsp; 56&nbsp; = 2&nbsp; &nbsp;37&nbsp; =&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 78&nbsp; = 2229&nbsp; =&nbsp; &nbsp; &nbsp;3310 = 2&nbsp; &nbsp; &nbsp; 511 =&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 1112 = 22&nbsp; 313 =&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;1314 = 2&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;715 =&nbsp; &nbsp; &nbsp;3&nbsp; 516 = 222217 =&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 1718 = 2&nbsp; &nbsp;3319 =&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 1920 = 22&nbsp; &nbsp; &nbsp;5答案：（2 * 2 * 2 * 2）*（3 * 3）* 5 * 7 * 11 * 13 * 17 * 19 = 232792560

Answer 2

该检查应在内部循环之外，以使其正确终止。否则，程序将永远不会在预期的出口处停止。divisible = Truepossible = dict()for i in xrange(1, 100000000):&nbsp; &nbsp; for n in xrange(1, 21):&nbsp; &nbsp; &nbsp; &nbsp; if i%n != 0:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; divisible = False&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if i in possible:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; possible[i].append(n)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; possible[i] = [n]&nbsp; &nbsp; if len(possible[i]) == 20:&nbsp; &nbsp; &nbsp; &nbsp; print i&nbsp; &nbsp; &nbsp; &nbsp; break顺便说一句，一种快速的方法是找到LCM，而不是像这样的暴力破解方法。编辑：一种不使用内存的变体。divisible = Truepossible = []for i in xrange(0, 1000000000):&nbsp; &nbsp; count = 0&nbsp; &nbsp; for n in xrange(1, 21):&nbsp; &nbsp; &nbsp; &nbsp; if i%n != 0:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; divisible = False&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count += 1&nbsp; &nbsp; if count == 20:&nbsp; &nbsp; &nbsp; &nbsp; possible.append(i)&nbsp; &nbsp; &nbsp; &nbsp; print i&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; print "\r", "%09d %d %d" % (i, 232792560, count),print possible

Answer 3

快速了解封套计算。您有一些类似100000000整数的东西，如果将它们全部存储起来，则将是0.4 Gb（以C为单位）的数量级。当然，这些是python整数，因此每个整数都超过4个字节...在我的系统上，每个都是24（！）字节，这将使0.4 Gb增大为2.34 Gb。现在，您将每个指针存储在多达21个列表中。因此（最多）还有指向每个指针的21个指针。假设一个指向int的4byte指针，您可以看到我们已经开始消耗大量的内存。另请注意，出于性能原因，列表被过度分配。您使用的内存可能比您需要的更多，这是因为您的列表不完整。当然，您实际上并没有全部存储它们，并且您有一个早期中断条件（显然）没有受到打击。您的某处可能存在逻辑错误。