Python按位和多个数字,比迭代按位运算符更快？

Question

我正在寻找一种最快的方式(O(n^2)不可接受)来应用AND超过2个数字的运算符Python.

有两种情况:
a)在输入上我们有M和N之间的数字
b)可以有一组任何自然数

目前我的代码使用& operator一个循环,它总是计算一个结果位(尽管我们知道,如果我们知道,那么0下一个和所有下一个结果位将始终是0).我的一个想法是计算每列的位数,对于给定的列,当存在时停止计算0,因为结果位将是0.

示例(包含在下面的测试代码中)

现有(迭代),相当慢(O(n^2))代码:

def solution(M, N):
    result = M
    for x in xrange(M, N):
        result &= x
    return result


def solution_sets(N):
    result = N[0]
    for x in N:
        result &= x
    return result


print solution(5, 7)  # 4
print solution(64, 128)  # 64
print solution(44, 55)  # 32
print solution_sets([60, 13, 12, 21])

如果该解决方案可扩展到例如XOR运算符将是好的.

我想问一些关于如何在Python语言中开始实现它并最大化性能的想法.

谢谢!

Answer 1

我会让 Python 担心优化，这可以用functools.reduce和operator.and_

>>> functools.reduce(operator.and_, [60, 13, 12, 21])
4

将其包装在一个函数中

def solution_sets(l):
    return functools.reduce(operator.and_, l)

timeit在以下环境中使用, 执行 1000000 次需要 0.758 秒：

蟒IDLE 3.4.1（V3.4.1：c0e311e010fc 5月18日到2014年，10点38分22秒）[MSC v.1600 32位（英特尔）]在Win32
处理器的Intel Core i7-3740QM CPU @ 2.70 GHz的
内存16.0 GB
OS 64 -位 Windows 7

setup = '''
import functools
import operator

def solution_sets(l):
    return functools.reduce(operator.and_, l)'''

>>> timeit.timeit('solution_sets([60, 13, 12, 21])', setup)
0.7582756285383709