python - 批量更新 Python 列表的一部分

Question

我已经编写了埃拉托色尼筛法的简单实现，我想知道是否有更有效的方法来执行其中一个步骤。

def eratosthenes(n):
    primes = [2]
    is_prime = [False] + ((n - 1)/2)*[True]
    for i in xrange(len(is_prime)):
        if is_prime[i]:
            p = 2*i + 1
            primes.append(p)
            is_prime[i*p + i::p] = [False]*len(is_prime[i*p + i::p])
    return primes

我正在使用 Python 的列表切片来更新我的 bool 列表 is_prime。每个元素 is_prime[i] 对应一个奇数 2*i + 1。

is_prime[i*p + i::p] = [False]*len(is_prime[i*p + i::p])

当我找到一个素数 p 时，我可以标记所有对应于该素数 False 倍数的元素，并且因为所有倍数都小于 p**2 也是较小素数的倍数，我可以跳过标记那些。 p**2的索引是i*p + i。

我担心计算 [False]*len(is_prime[i*p + 1::p]) 的成本，我试图将它与我的其他两种策略进行比较无法上类。

出于某种原因，公式 (len(is_prime) - (i*p + i))/p(如果为正)并不总是等于 len(is_prime[i* p + i::p])。是因为我计算的切片长度有误，还是我没有捕捉到切片的一些微妙之处？

当我在函数中使用以下行时:

print len(is_prime[i*p + i::p]), ((len(is_prime) - (i*p + i))/p)
is_prime[i*p + i::p] = [False]*((len(is_prime) - (i*p + i))/p)

我得到以下输出(案例 n = 50):

>>> eratosthenes2(50)
7 7
3 2
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 9, in eratosthenes2
ValueError: attempt to assign sequence of size 2 to extended slice of size 3

我还尝试用以下内容替换批量更新行:

for j in xrange(i*p + i, len(is_prime), p):
    is_prime[j] = False

但是对于较大的 n 值，这会失败，因为 xrange 不会占用任何比 long 更大的值。我放弃了尝试将 itertools.count 变成我需要的东西。

是否有更快更优雅的方式来批量更新列表切片？有什么我可以做的来修复我尝试过的其他策略，以便我可以将它们与工作策略进行比较吗？谢谢!

Answer 1

使用itertools.repeat() :

is_prime[i*p + 1::p] = itertools.repeat(False, len(is_prime[i*p + 1::p]))

切片语法将遍历您放在右侧的任何内容；它不需要是一个完整的序列。

那么让我们修正这个公式。我就borrow the Python 3 formula因为我们知道这行得通:

1 + (hi - 1 - lo) / step

由于 step > 0，hi = stop 和 lo = start，所以我们有:

1 + (len(is_prime) - 1 - (i*p + 1))//p

(// 是整数除法；这使我们的代码面向 future 的 Python 3，但需要 2.7 才能运行)。

现在，把它们放在一起:

slice_len = 1 + (len(is_prime) - 1 - (i*p + 1))//p
is_prime[i*p + 1::p] = itertools.repeat(False, slice_len)

Python 3 用户:请不要直接使用这个公式。相反，只需编写 len(range(start, stop, step))。这给出了具有相似性能的相同结果(即它是 O(1))并且更容易阅读。