如何改进内存密集型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中的所有组合转换为字符串，然后返回剩余整数的列表，这些整数都是素数，但是它对数字12运行三次A[i*k-2]=str（i*k），因为它遍历所有2的倍数，然后是3，然后是6。像这样的事情发生了，在存储这么大的列表时，我很快就遇到了麻烦，它崩溃了。任何建议都将不胜感激！提前谢谢。在

编辑：我不知道这是否有区别，但我使用的是python3.3

Answer 1

您可以使用生成器，而不是使用大型列表。在

def ESgen():
    d = {}  
    q = 2   
    while 1:
        if q not in d:
            yield q        
            d[q*q] = [q]   
        else:
            for p in d[q]: 
                d.setdefault(p+q,[]).append(p)
            del d[q]      
        q += 1

要使用生成器获取第一个n素数的列表，可以执行以下操作：

^{pr2}$

如果只想检查一个数是否为素数，set比list快：

from itertools import islice

gen = ESgen()
set(islice(gen, n))  

Answer 2

首先，你用了一种非常奇怪、效率低下的方法来记录某个东西是否是复合的。您不需要存储数字的字符串表示形式，甚至不需要存储数字本身。您可以使用一个大的布尔值列表，其中如果n是素数，prime[n]为真。在

第二，如果简化了索引，就没有理由担心在列表开头会浪费一点空间。与列表中其他部分占用的空间相比，它是很小的，更不用说您使用的所有字符串、int和其他东西了。这就像为你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]