Python bitowy ORAZ na wielu liczbach, szybszy niż iteracyjny operator bitowy?

Question

Szukam najszybszego sposobu (O(n^2) jest niedopuszczalne) do zastosowania operatora AND na więcej niż 2 numery w Python.

Istnieją dwa scenariusze:
a) na wejściu mamy numery w przedziale pomiędzy M i N
b) nie może być zbiorem dowolnych liczb naturalnych

Obecnie moje wykorzystuje kod & operator w pętli, która zawsze oblicza bit wyniku (pomimo faktu, że wiemy, że jeśli mamy 0, wtedy następny i wszystkie następne bity wynikowe będą zawsze 0). Jednym z moich pomysłów jest obliczenie bitów na kolumny, a dla danej kolumny zatrzymanie obliczeń, gdy istnieje 0, ponieważ bit wyniku będzie 0.

Przykład (w procedurze badania poniżej)

istniejących (wielokrotny), a mała (O(n^2)) Kod:

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]) 

Byłoby dobrze, gdyby roztwór ten rozszerzalny do na przykład operator XOR.

Pytam o kilka pomysłów, jak rozpocząć wdrażanie tego w języku Python i zmaksymalizować wydajność.

Dzięki!

Answer 1

chciałbym niech Python martwić się o optymalizacji, może to być napisane trywialnie dla sekwencji przy użyciu functools.reduce i operator.and_

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

Zawijanie to w funkcji

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

---

Korzystanie timeit, Aby to zrobić 1000000 razy trwało 0,758 sekundy w następującym środowisku:

Pythona IDLE 3.4.1 (v3.4.1: c0e311e010fc, 18 maja 2014 10:38:22) [MSC v.1600 32 bitów (Intel)] w win32
Procesor Core i7 -3740QM CPU @ 2.70 GHz
pamięci 16,0 GB
OS 64-bitowego systemu 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