1

今天,我为初筛写了一个简短的脚本,我正在寻找改进它。我对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

4

2 回答 2

2

首先,您正在使用一种非常奇怪、低效的方式来记录某事物是否是复合的。您不需要存储数字的字符串表示形式,甚至不需要存储数字本身。你可以只使用一个大的布尔值列表,如果是素数,哪里prime[n]是真的。n

其次,如果它简化了索引,就没有理由担心在列表的开头浪费一点空间。与列表的其余部分占用的空间相比,它很小,更不用说您正在使用的所有字符串和整数和东西了。这就像为您的 300,000 美元汽车节省 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]
于 2013-08-23T04:01:00.557 回答
0

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

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))  
于 2013-08-23T03:55:02.090 回答