Python bitweise AND auf mehreren Zahlen, schneller Weg als iterativer bitweiser Operator?

Ich suche nach einem schnellsten Weg (O(n^2) ist nicht akzeptabel), einen AND Operator über mehr als 2 Nummern in Python zu bewerben.Python bitweise AND auf mehreren Zahlen, schneller Weg als iterativer bitweiser Operator?

Es gibt zwei Szenarien:
a) bei der Eingabe haben wir Zahlen in einem Bereich zwischen M und N
b) kann es

Derzeit wird ein Satz von allen natürlichen Zahlen meines Code Verwendungen ein & operator in einer Schleife, die immer ein Ergebnis-Bit berechnen (trotz der Tatsache, dass wir wissen, dass, wenn wir 0 haben, dann die nächsten und alle nächsten Ergebnisbits immer 0 sein werden). Eine meiner Ideen besteht darin, Bits pro Spalte zu berechnen und für eine bestimmte Spalte die Berechnung zu beenden, wenn 0 vorhanden ist, weil das Ergebnisbit 0 ist.

Beispiel (in Testcode enthalten unten)

Bitwise puzzle explained on an example

Bestehende (iterative), eher langsam (O(n^2)) Code:

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

Es wäre gut, wenn diese Lösung erweiterbar war zum Beispiel XOR-Operator.

Ich frage nach einigen Ideen, wie man das in der Python-Sprache implementieren und die Leistung maximieren kann.

Danke!

Quelle

2015-06-30 oski86

Sie sind unwahrscheinlich t o Verbessern Sie die Leistung von bitweisen Operationen auf Ganzzahlen, besonders wenn Sie es in Python schreiben. – jonrsharpe

Auch wenn es eine Funktion gibt, die AND mehrere Zahlen erlaubt, kann Ihre CPU wahrscheinlich nur UND 2 Zahlen auf einmal, so dass Ihre "effiziente" Funktion noch O (n^2) auf der CPU-Anweisungsebene. – Aderis

Was lässt Sie glauben, dass Ihr Algorithmus O (n^2) ist?Es ist eigentlich O (n). Sie können 1 Iteration mit "xrange (M + 1, N)" eliminieren, um die Ausführung von "result = M & M" bei der ersten Iteration zu vermeiden. Sie können auch früh anhalten, wenn das Ergebnis gleich Null ist. Es wäre aber immer noch O (n). Es scheint, als ob du an einem Hausaufgabenproblem arbeitest, dass du vielleicht auf andere als die vorgeschriebene Weise näherst. –

Ich würde lassen Python über die Optimierung Sorge, das für eine Sequenz triviale Weise geschrieben werden konnte functools.reduce und operator.and_

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

Wrapping diese in einer Funktion

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

Mit timeit verwenden, dies zu tun 1000000 Mal dauerte 0,758 Sekunden in der folgenden Umgebung:

Python IDLE 3.4.1 (V3.4.1: c0e311e010fc, den 18. Mai 2014 10.38.22) [MSC v.1600 32 bit (Intel)] auf Win32
Prozessor Intel Core i7 -3740QM CPU @ 2,70 GHz
Speicher 16,0 GB
OS 64-Bit-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

Quelle

2015-06-30 17:07:35 CoryKramer

Python bitweise AND auf mehreren Zahlen, schneller Weg als iterativer bitweiser Operator?

Antwort

Verwandte Themen