是& 检查奇数时比 % 更快？

Question

要检查奇数和偶数，最低位检查是否比使用模数更有效？

>>> def isodd(num):
        return num & 1 and True or False

>>> isodd(10)
False
>>> isodd(9)
True

Answer 1

是的。 标准库中的 timeit 模块是您检查这些内容的方式。 例如：

$ python -m timeit -s 'def isodd(x): x & 1' 'isodd(9)'
1000000 loops, best of 3: 0.446 usec per loop
$ python -m timeit -s 'def isodd(x): x & 1' 'isodd(10)'
1000000 loops, best of 3: 0.443 usec per loop
$ python -m timeit -s 'def isodd(x): x % 2' 'isodd(9)'
1000000 loops, best of 3: 0.461 usec per loop
$ python -m timeit -s 'def isodd(x): x % 2' 'isodd(10)'
1000000 loops, best of 3: 0.453 usec per loop

如您所见，在我的 (first-day==old==slow;-) Macbook Air 上，& 解决方案可重复地比 %< 快 7 到 18 纳秒/代码> 解决方案。

timeit 不仅告诉您哪个更快，而且还告诉您快了多少（只需运行测试几次），这通常表明它是多么不重要（您真的关心吗？ 10 纳秒的差异，当调用函数的开销约为 400 时？！-)...

让程序员相信微优化本质上是无关紧要的，这已被证明是一项不可能完成的任务——尽管已经过去了 35 年（计算机在这段时间里）速度提高了几个数量级！）自从 Knuth 写道

我们应该忘记小事
效率大约是 97%
时间：过早优化是
万恶之源。

正如他所解释的那样，这句话引用自霍尔的一份更古老的声明。 我想每个人都完全相信他们的情况属于剩下的 3%！

因此，我们（特别是 Tim Peters 值得尊敬）没有无休止地重复“没关系”，而是放入了标准 Python 库模块 timeit，这使得测量此类微量数据变得非常容易。基准，从而至少让一些程序员说服自己，嗯，这个案例确实属于 97% 组！-)

Answer 2

老实说，我认为这并不重要。

第一个问题是可读性。 什么对其他开发人员更有意义？ 我个人在检查数字的偶数/奇数时会期望取模。 我预计大多数其他开发人员也会有同样的期望。 通过引入不同的、意想不到的方法，您可能会使代码阅读和维护变得更加困难。

第二个事实是，在执行任一操作时您可能永远不会遇到瓶颈。 我支持优化，但早期优化是在任何语言或环境中都可以做的最糟糕的事情。 如果由于某种原因，确定一个数字是偶数还是奇数成为瓶颈，那么找到解决问题的最快方法。 然而，这让我回到了我的第一点——第一次编写例程时，应该以最易读的方式编写它。

Answer 3

您可以获得的最佳优化是不将测试放入函数中。 'number % 2' 和 'number & 1' 是检查奇数/偶数的非常常见的方法，经验丰富的程序员会立即识别该模式，并且如果您确实需要它很明显，您可以随时添加注释，例如“# if number is odd, then blah blah blah” 。

# state whether number is odd or even
if number & 1:
    print "Your number is odd"
else:
    print "Your number is even"

Answer 4

“返回 num & 1 和 True 或 False”？ 哇！ 如果您是速度狂 (1)“return num & 1”(2) 内联它：if somenumber % 2 == 1 清晰且击败 isodd(somenumber) code> 因为它避免了 Python 函数调用。

Answer 5

约翰提出了一个很好的观点。 真正的开销在于函数调用：

me@localhost ~> python -mtimeit -s'9 % 2'
10000000 loops, best of 3: 0.0271 usec per loop
me@localhost ~> python -mtimeit -s'10 % 2'
10000000 loops, best of 3: 0.0271 usec per loop

me@localhost ~> python -mtimeit -s'9 & 1'
10000000 loops, best of 3: 0.0271 usec per loop
me@localhost ~> python -mtimeit -s'9 & 1'
10000000 loops, best of 3: 0.0271 usec per loop

me@localhost ~> python -mtimeit -s'def isodd(x): x % 2' 'isodd(10)'
1000000 loops, best of 3: 0.334 usec per loop
me@localhost ~> python -mtimeit -s'def isodd(x): x % 2' 'isodd(9)'
1000000 loops, best of 3: 0.358 usec per loop

me@localhost ~> python -mtimeit -s'def isodd(x): x & 1' 'isodd(10)'
1000000 loops, best of 3: 0.317 usec per loop
me@localhost ~> python -mtimeit -s'def isodd(x): x & 1' 'isodd(9)'
1000000 loops, best of 3: 0.319 usec per loop

有趣的是，这两种方法在没有函数调用的情况下同时执行。

Answer 6

使用Python 3.6，答案是否。 在 2017 MBP 上使用下面的代码表明使用模更快。

# odd.py
from datetime import datetime

iterations = 100_000_000


def is_even_modulo(n):
    return not n % 2


def is_even_and(n):
    return not n & 1


def time(fn):
    start = datetime.now()
    for i in range(iterations, iterations * 2):
        fn(i)
    print(f'{fn.__name__}:', datetime.now() - start)


time(is_even_modulo)
time(is_even_and)

给出这个结果：

$ python3 -m odd
is_even_modulo: 0:00:14.347631
is_even_and: 0:00:17.476522
$ python3 --version
Python 3.6.1

正如其他答案中所建议的，函数调用是一个很大的开销，但是，删除它表明模数仍然比按位更快，并且在 Python 3.6.1 中：

# odd.py
from datetime import datetime

iterations = 100_000_000


def time_and():
    start = datetime.now()
    for i in range(iterations):
        i & 1 
    print('&:', datetime.now() - start)


def time_modulo():
    start = datetime.now()
    for i in range(iterations):
        i % 2
    print('%:', datetime.now() - start)


time_modulo()
time_and()

结果：

$ python3 -m odd
%: 0:00:05.134051
&: 0:00:07.250571

奖励：事实证明这需要大约两倍的时间在 Python 2.7 中运行。

$ time python2 -m odd
('&:', '0:00:20.169402')
('%:', '0:00:19.837755')

real    0m41.198s
user    0m39.091s
sys 0m1.899s
$ time python3 -m odd
&: 0:00:11.375059
%: 0:00:08.010738

real    0m19.452s
user    0m19.354s
sys 0m0.042s

Answer 7

除了邪恶的优化之外，它还消除了每个程序员无需多看就能理解的非常惯用的“var % 2 == 0”。 所以这也违反了蟒蛇的禅宗，而且收获甚微。

此外，为了提高可读性，a = b 和 True 或 False 已被替换为

return True if num & 1 其他错误

Answer 8

真的很惊讶上面的答案都没有同时进行变量设置（时间文字是不同的故事）和没有函数调用（这显然隐藏了“较低项”）。 卡在 ipython 的 timeit 的时间上，我得到了明显的获胜者 x&1 - 使用 python2.6 的结果更好，约 18%（使用 python3.1 的约 12%）。

在我很旧的机器上：

$ python -mtimeit -s 'x = 777' 'x&1'
10000000 loops, best of 3: 0.18 usec per loop
$ python -mtimeit -s 'x = 777' 'x%2'
1000000 loops, best of 3: 0.219 usec per loop

$ python3 -mtimeit -s 'x = 777' 'x&1'
1000000 loops, best of 3: 0.282 usec per loop
$ python3 -mtimeit -s 'x = 777' 'x%2'
1000000 loops, best of 3: 0.323 usec per loop