Python出现内存错误

Question

大家好，我刚开始学习Python。我在网上的一个编程网站上遇到了一个问题。

A=3，B=5
A的乘法表是：3, 6, 9, 12, 15, 18，依此类推
B的乘法表是：5, 10, 15, 20，依此类推
合并后得到：3, 5, 6, 9, 10, 12, 15, 15, 18, 20，依此类推
去掉重复的数字后：3, 5, 6, 9, 10, 12, 15, 18, 20，依此类推
对于N=2，超级表的第二个元素是5

问题是，我可以在A和B的有限范围内得到答案，但当我试图计算第10^9个元素时，出现了内存错误。

from array import *
import itertools
array1=[]
array2=[]
A=int(input())
B=int(input())
N=int(input())
for i in range(0,10**9):
    try:
        array1.append(i+1 * A)
    except MemoryError :
        break 

for j in range(0,10**9):
    try:
        array2.append(j+1 * B)
    except MemoryError :
        break
filter(None ,array1)
filter(None ,array2)
array3 = array1 + array2
array3 = sorted(set(array3))
print (array3[N])

错误追踪（最近的调用在最前面）：
文件 "C:/Users/Clinton D/Desktop/supertables.py"，第21行，
array3 = array1 + array2 内存错误

Answer 1

你不需要提前创建整个列表（也就是说，如果你只想找到第N个值，为什么要创建这么多值呢？）

你想做的事情大概是这样的：

def f(n):
    vals = (x for x in xrange(1, 10**9) if (x % 3 == 0) or (x % 5 == 0))
    for _ in xrange(n - 1):
        vals.next()
    return vals.next()

在这里，你只是一个一个地查看这些东西，所以并没有创建一个很大的列表。

Answer 2

正如大家所提到的，你在内存中创建了一些非常大的列表。我也觉得你居然会期待出现内存错误（MemoryError）这点很惊讶！你的一部分问题可以通过使用列表推导式来解决，这是一种告诉Python如何构建列表的方法，不需要使用for循环和append。比如，计算前100个数字的平方，可以这样写：

squares = [x*x for x in xrange(100)]

列表推导式由两部分组成：元素定义和可迭代集合。在之前的例子中，x*x是元素定义，而for x in xrange(100)是可迭代部分。

现在回到你的问题。第二个让我注意到的点是，你使用了array模块，但其实并不需要它的任何特定功能。

最后，使用filter(None, [...])可以帮助你去掉所有评估为False的元素，对于数字来说，就是0。在你的例子中，列表中没有这样的元素，除非A或B是0。

所以你的脚本应该大致是这样的：

A = int(input())
B = int(input())
N = int(input())

array1 = []
array2 = []
if A:
    array1 = [i * A for i in xrange(1, 10**7 + 1)]
if B:
    array2 = [i * B for i in xrange(1, 10**7 + 1)]

array1.extend(array2)
del(array2)  # not entirely necessary, if you have 128GB RAM or more...
array1 = sorted(set(array1))
print array1[N-1]

我一直在想的一个点，直到我完全卡住了电脑来测试你的代码，就是你可以使用生成器来解决这个问题。我现在对此非常确定。另外，你为什么需要一到二十亿个元素呢？

我认为你这里的问题并不是与Python或内存不足有关，而是一个糟糕的算法来计算这些值——我只是稍微让它好了一点。

编辑：

• @acushner注意到平方列表被简单地命名为list，这可能会干扰Python内置的列表。
• 这里有一些错别字。
• 我之前发布了一个稍微不正确的脚本版本，现在已经修正。

Answer 3

如果你真的需要使用这个大数据集，建议你使用 pandas 或 numpy 来处理它。

不过，如果你是在参加一种编程挑战（叫做代码高尔夫），可以尝试用一个小一点的数据集来测试你的方法。无论如何，你可以考虑使用迭代器，而不是列表，并使用 iterator.chain 来连接多个迭代器。

from itertools import chain

A=int(input())
B=int(input())
N=int(input())

array_a = (i*A for i in range(10**4))
array_b = (i*B for i in range(10**4))
array_c = chain(array_a, array_b)
c = sorted(set(array_c))

print(c[N])