批量更新 Python 列表的一部分
Bulk updating a slice of a Python list
我已经编写了埃拉托色尼筛法的简单实现,我想知道是否有更有效的方法来执行其中一个步骤。
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 的列表切片来更新我的布尔值列表 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
变成我需要的东西。
是否有更快更优雅的批量更新列表切片的方法?有什么我可以做的来修复我尝试过的其他策略,以便我可以将它们与工作策略进行比较吗?谢谢!
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
(//
是整数除法;这使我们的代码面向未来 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)
Python3位用户:请不要直接使用这个公式。相反,只需写 len(range(start, stop, step))
。这给出了具有相似性能的相同结果(即它是 O(1))并且更容易阅读。
我已经编写了埃拉托色尼筛法的简单实现,我想知道是否有更有效的方法来执行其中一个步骤。
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 的列表切片来更新我的布尔值列表 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
变成我需要的东西。
是否有更快更优雅的批量更新列表切片的方法?有什么我可以做的来修复我尝试过的其他策略,以便我可以将它们与工作策略进行比较吗?谢谢!
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
(//
是整数除法;这使我们的代码面向未来 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)
Python3位用户:请不要直接使用这个公式。相反,只需写 len(range(start, stop, step))
。这给出了具有相似性能的相同结果(即它是 O(1))并且更容易阅读。