Python：循环和操作大型数组时的性能

Question

我的问题有两个方面：

1. 有没有一种方法既有效地循环又操纵 使用枚举数组，例如和操作 同时？在
2. python中有没有内存优化的数组版本？ （就像NumPy用指定的类型创建更小的数组）

我用Sieve of Eratosthenes做了一个在（2-rng）范围内寻找素数的算法。在

注意：如果在2-1000000（总运行时间也低于1秒）内搜索素数，则不存在该问题。在数千万和数亿人中，这种情况开始受到伤害。到目前为止，将表格从包含所有自然数改为只包含奇数，我可以搜索的粗略最大范围是4亿（奇数为2亿）。在

Whiles而不是for循环至少会降低当前算法的性能。
NumPy虽然可以通过类型转换创建更小的数组，但使用相同的代码进行处理实际上需要大约两倍的时间，除了

oddTable = np.int8(np.zeros(size))

代替

^{pr2}$

并使用整数指定值“prime”和“not prime”来保持数组类型。在

使用伪代码，算法如下所示：

oddTable = [0] * size    # Array representing odd numbers excluding 1 up to rng

for item in oddTable:
    if item == 0:        # Prime, since not product of any previous prime
        set item to "prime"
        set every multiple of item in oddTable to "not prime"

Python是一种简洁的语言，特别是当循环遍历列表中的每一项时，但是作为索引，比如

for i in range(1000)

不能被操纵，而在循环中，我不得不转换了几次范围，以产生一个可使用的iterable。在代码中：“P”表示质数，“”表示非质数，0表示不选中。在

num = 1                  # Primes found (2 is prime)
size = int(rng / 2) - 1  # Size of table required to represent odd numbers
oddTable = [0] * size    # Array with odd numbers \ 1: [3, 5, 7, 9...]

new_rng = int((size - 1) / 3)    # To go through every 3rd item
for i in range(new_rng):         # Eliminate no % 3's
    oddTable[i * 3] = "_"
oddTable[0] = "P"                # Set 3 to prime
num += 1

def act(x):              # The actual integer index x in table refers to
    x = (x + 1) * 2 + 1
return x
        # Multiples of 2 and 3 eliminated, so all primes are 6k + 1 or 6k + 5
        # In the oddTable: remaining primes are either 3*i + 1 or 3*i + 2
        # new_rng to loop exactly 1/3 of the table length -> touch every item once
for i in range(new_rng):
    j = 3*i + 1                    # 3*i + 1
    if oddTable[j] == 0:
        num += 1
        oddTable[j] = "P"
        k = act(j)
        multiple = j + k    # The odd multiple indexes of act(j)
        while multiple < size:
            oddTable[multiple] = "_"
            multiple += k
    j += 1                         # 3*i + 2
    if oddTable[j] == 0:
        num += 1
        oddTable[j] = "P"
        k = act(j)
        multiple = j + k
        while multiple < size:
            oddTable[multiple] = "_"
            multiple += k

Answer 1

为了使代码更具python风格，可以将算法分成更小的块（函数），这样每个块都可以很容易地掌握。在

我的第二条评论可能会让你大吃一惊：Python自带“电池”。为了编写Erathostenes的siever，为什么需要显式地操作数组并用它污染代码？为什么不创建一个函数（例如is_prime）并使用为此目的提供的standard memoize decorator？（如果坚持使用2.7，请参见memoization library for python 2.7）。在

上面两条建议的结果可能不是“最有效的”，但它（正如我在这个问题上的经验）会很好地工作，同时允许您快速创建流畅的代码，从而节省程序员的时间（包括创建和维护）。在