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

Question

我的问题有两个:

1. 是否有一种方法可以有效地循环和操作一个数组使用enumerate，例如和操作循环同一时间?
2. 是否有任何内存优化版本的数组在python?(如NumPy创建指定类型的较小数组)

我用埃拉托色尼筛子找到了范围(2 - rng)内的素数。

注意:如果在2 - 1,000,000(总运行时间也小于1秒)内搜索素数，则不存在问题。数千万甚至数亿人开始受到伤害。到目前为止，将表从包含所有自然数更改为仅包含奇数，我能够搜索的粗略最大范围是4亿(其中2亿是奇数)。

而代替for循环会降低性能，至少在当前算法中是这样。NumPy虽然能够使用类型转换创建更小的数组，但实际上使用相同的代码处理大约需要两倍的时间，除了

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

代替

oddTable = [0] * size

和使用整数赋值"素数"one_answers"非素数"来保持数组类型。

使用伪代码，算法看起来像这样:

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)

不能在循环中操作，我必须转换几次范围以产生要使用的可迭代对象。代码中:"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'筛，为什么需要显式地操作数组并使用它污染您的代码?为什么不创建一个函数(例如is_prime)并使用为此目的提供的标准memoize装饰器呢?(如果你坚持使用2.7，请参见python 2.7的memoization库)。

以上两条建议的结果可能不是"最有效的"，但它将(正如我所经历的那个问题)工作得足够好，同时允许您快速创建整洁的代码，从而节省程序员的时间(创建和维护)。