为什么我的埃拉托色尼筛与整数比布尔工作得更快？ [英] Why does my Sieve of Eratosthenes work faster with integers than with booleans?
问题描述
我写的埃拉托色尼的简单筛，它使用的人的名单，并把他们变成零，如果不是素数，像这样：
I wrote a simple Sieve of Eratosthenes, which uses a list of ones and turns them into zeros if not prime, like so:
def eSieve(n): #Where m is fixed-length list of all integers up to n
'''Creates a list of primes less than or equal to n'''
m = [1]*(n+1)
for i in xrange(2,int((n)**0.5)+1):
if m[i]:
for j in xrange(i*i,n+1,i):
m[j]=0
return [i for i in xrange(2,n) if m[i]]
我测试了它与％timeit 运行速度，得到了：
#n: t
#10**1: 7 μs
#10**2: 26.6 μs
#10**3: 234 μs
#10**4: 2.46 ms
#10**5: 26.4 ms
#10**6: 292 ms
#10**7: 3.27 s
我认为，如果我改变了 [1] 和 0 来布尔值，它会跑得更快...但它确实相反：
I assumed, if I changed [1] and 0 to booleans, it would run faster... but it does the opposite:
#n: t
#10**1: 7.31 μs
#10**2: 29.5 μs
#10**3: 297 μs
#10**4: 2.99 ms
#10**5: 29.9 ms
#10**6: 331 ms
#10**7: 3.7 s
为什么是布尔慢？
Why are the booleans slower?
推荐答案
这是因为真和假是抬起头来全局在Python 2 0 和 1 文本只是常量，抬头又迅速数组引用，而在全局的字典的全局命名空间中查找（通过内置的插件命名空间下降）：
This happens because True and False are looked up as globals in Python 2. The 0 and 1 literals are just constants, looked up by a quick array reference, while globals are dictionary lookups in the global namespace (falling through to the built-ins namespace):
>>> import dis
>>> def foo():
... a = True
... b = 1
...
>>> dis.dis(foo)
2 0 LOAD_GLOBAL 0 (True)
3 STORE_FAST 0 (a)
3 6 LOAD_CONST 1 (1)
9 STORE_FAST 1 (b)
12 LOAD_CONST 0 (None)
15 RETURN_VALUE
的真值抬头与 LOAD_GLOBAL 字节code，而 1 文本值复制到堆栈<code> LOAD_CONST 。
The True value is looked up with the LOAD_GLOBAL bytecode, while the 1 literal value is copied to the stack with LOAD_CONST.
如果您真和假的当地人的你可以让他们一样快再次：
If you make True and False locals you can make them just as fast again:
def eSieve(n, True=True, False=False):
m = [True]*(n+1)
for i in xrange(2,int((n)**0.5)+1):
if m[i]:
for j in xrange(i*i,n+1,i):
m[j]=False
return [i for i in xrange(2,n) if m[i]]
分配真和假为默认值设置为参数给出了函数的名称作为当地人，具有确切相同的值;再次使用一个简化的版本：
Assigning True and False as default values to for arguments gives the function those names as locals, with the exact same values; again using a simplified version:
>>> def bar(True=True, False=False):
... True == False
...
>>> dis.dis(bar)
2 0 LOAD_FAST 0 (True)
3 LOAD_FAST 1 (False)
6 COMPARE_OP 2 (==)
9 POP_TOP
10 LOAD_CONST 0 (None)
13 RETURN_VALUE
请注意在 LOAD_FAST 运算codeS，现在指数就像 LOAD_CONST 字节codeS ;当地人在CPython的功能都存储在一个数组就像字节code常量。
Note the LOAD_FAST opcodes, now with indices just like the LOAD_CONST bytecodes; locals in a CPython function are stored in an array just like bytecode constants.
通过这种变化，利用布尔胜出，虽然小幅;我的时序：
With that change, using booleans wins out, albeit by a small margin; my timings:
# n integers globals locals
# 10**1 4.31 µs 4.2 µs 4.2 µs
# 10**2 17.1 µs 17.3 µs 16.5 µs
# 10**3 147 µs 158 µs 144 µs
# 10**4 1.5 ms 1.66 ms 1.48 ms
# 10**5 16.4 ms 18.2 ms 15.9 ms
# 10**6 190 ms 215 ms 189 ms
# 10**7 2.21 s 2.47 s 2.18 s
的区别是不是真的那么多，因为Python的布尔只是一个 INT 子类。
请注意，在Python 3里，真和假已成为关键字，不能再被分配到，使得有可能对待他们就像整数常量。
Note that in Python 3, True and False have become keywords and can no longer be assigned to, making it possible to treat them just like integer literals.
这篇关于为什么我的埃拉托色尼筛与整数比布尔工作得更快？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
