如何改进内存密集型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。发生了这样的事情，在存储这么大的列表时，我很快就碰壁了，它崩溃了。如有任何建议，我们将不胜感激！提前谢谢。

编辑：我不知道这是否有什么不同，但我使用的是Python 3.3

Answer 1

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

其次，如果它简化了索引，就没有理由担心在列表开头浪费一点空间。与列表中其他部分占用的空间相比，它很小，更不用说所有的字符串、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]

Answer 2

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

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素数的列表，可以执行以下操作：

from itertools import islice
gen = ESgen()
list(islice(gen, n))  

如果你只想检查一个数字是否素数，set比list:快

from itertools import islice
gen = ESgen()
set(islice(gen, n))