python - 如何改进内存密集型Python脚本？

Question

今天，我为素数筛编写了一个简短的脚本，我希望对其进行改进。我对 python 和一般编程相当陌生，所以我想知道:在涉及大量数字列表的程序中减少内存使用的好方法是什么？这是我的示例脚本:

def ES(n):
    A = list(range(2, n+1))
    for i in range(2, n+1):
        for k in range(2, (n+i)//i):
            A[i*k-2] = str(i*k)
    A = [x for x in A if isinstance(x, int)]
    return A

该脚本将列表 A 中的所有组合转换为字符串，然后返回剩余整数的列表，这些整数都是素数，但它运行 A[i*k-2] = str(i*k) 三数字 12 的倍数，因为它经历了 2 的所有倍数，然后是 3，再一次是 6。发生了类似的事情，在存储这么大的列表时，我很快就碰上了砖墙，它崩溃了。任何建议将不胜感激!提前致谢。

编辑:我不知道这是否有什么不同，但我正在使用 Python 3.3

Answer 1

首先，您使用了一种非常奇怪、低效的方式来记录某些内容是否是复合的。您不需要存储数字的字符串表示形式，甚至不需要存储数字本身。您可以只使用一个大的 bool 值列表，其中如果 n 是质数，则 prime[n] 为 true。

其次，如果简化了索引，就没有理由担心在列表开头浪费一点空间。与列表其余部分所占用的空间相比，它很小，更不用说您正在使用的所有字符串、整数和其他内容了。这就像为您值(value) 30 万美元的汽车节省 3 美元的油漆费用。

第三，range 采用一个 step 参数，您可以使用它来简化循环。

def sieve(n):
    """Returns a list of primes less than n."""

    # n-long list, all entries initially True
    # prime[n] is True if we haven't found a factor of n yet.
    prime = [True]*n

    # 0 and 1 aren't prime
    prime[0], prime[1] = False, False

    for i in range(2, n):
        if prime[i]:
            # Loop from i*2 to n, in increments of i.
            # In other words, go through the multiples of i.
            for j in range(i*2, n, i):
                prime[j] = False

    return [x for x, x_is_prime in enumerate(prime) if x_is_prime]