Python MemoryError发生大循环

Question

我正在尝试创建一个脚本来为我在Project Euler上解决问题，但是它一直返回MemoryError。我完全不知道为什么。divisible = Truepossible = 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            breakPython似乎认为它发生在这条线上 possible[i] = [n]

Answer 1

问题出在你的线上

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

你的意思是说

if len(possible) == 20:

照原样，您的代码将继续运行-大概是因为循环计数如此之大，所以某些堆栈已填满...

另外-尽管我不确定您要实现的目标，但是您的break命令位于最内层的循环中-因此您会中断该循环，然后再次执行此操作...并且由于长度仅恰好是20一次，因此您仍然被卡住。检查您的逻辑。

例如，对代码进行以下小的更改将产生有用的输出（尽管我不知道它是否对您有用...但是它可能会给您一些想法）：

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) == 20:

        print i

        break

    else:

        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 = True

possible = [];

biggest = 0;

bigN = 100000000;

for i in xrange(1, bigN):

    for n in xrange(1, 21):

        if i%n != 0:

            divisible = False

        else:

            if len(possible) > 0:

                possible.append(n)

            else:

                possible = [n]

    if len(possible) >= 20:

        print i

        print possible

        break

    else:

        if bigN < 1000:

            print i, possible; # handy for debugging

        if biggest < len(possible):

            biggest = len(possible);

        possible = []

计算您正在做的事情的“手动”方法是找到所有1到20的数字的素数；计算每个中出现质数的最大次数；并拿走他们的产品：

2  = 2

3  =     3

4  = 22

5  =        5

6  = 2   3

7  =          7

8  = 222

9  =     33

10 = 2      5

11 =              11

12 = 22  3

13 =                 13

14 = 2         7

15 =     3  5

16 = 2222

17 =                    17

18 = 2   33

19 =                      19

20 = 22     5

答案：（2 * 2 * 2 * 2）*（3 * 3）* 5 * 7 * 11 * 13 * 17 * 19 = 232792560

Answer 2

该检查应在内部循环之外，以使其正确终止。否则，程序将永远不会在预期的出口处停止。

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

顺便说一句，一种快速的方法是找到LCM，而不是像这样的暴力破解方法。

编辑：一种不使用内存的变体。

divisible = True

possible = []

for i in xrange(0, 1000000000):

    count = 0

    for n in xrange(1, 21):

        if i%n != 0:

            divisible = False

        else:

            count += 1

    if count == 20:

        possible.append(i)

        print i

    else:

        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指针，您可以看到我们已经开始消耗大量的内存。

另请注意，出于性能原因，列表被过度分配。您使用的内存可能比您需要的更多，这是因为您的列表不完整。

当然，您实际上并没有全部存储它们，并且您有一个早期中断条件（显然）没有受到打击。您的某处可能存在逻辑错误。