Python/NumPy: eine laufende Summe der Umsetzung (aber nicht ganz)

Question

Gegeben sind zwei Arrays gleicher Länge, ein Haltedaten, man die Ergebnisse hält aber zunächst auf Null gesetzt, zum Beispiel:

a = numpy.array([1, 0, 0, 1, 0, 1, 0, 0, 1, 1]) 
b = numpy.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0]) 

Ich würde Ich mag es, die Summe aller möglichen Teilmengen von drei benachbarten Elementen in a zu berechnen. Wenn die Summe 0 oder 1 ist, bleiben die drei entsprechenden Elemente in b unverändert; nur dann, wenn die Summe 1 überschreitet, sind die drei entsprechenden Elemente in B auf 1 gesetzt, so daß nach der Berechnung b

array([0, 0, 0, 1, 1, 1, 0, 1, 1, 1]) 

eine einfache Schleife wird dies erreichen wird:

for x in range(len(a)-2): 
    if a[x:x+3].sum() > 1: 
     b[x:x+3] = 1 

Danach, b hat die gewünschte Form.

Ich muss dies für eine große Menge von Daten tun, so Geschwindigkeit ist ein Problem. Gibt es einen schnelleren Weg in NumPy, um die obige Operation auszuführen?

(Ich verstehe, das ist ähnlich wie eine Faltung, aber nicht ganz das Gleiche).

Answer 1

Sie können mit einer Faltung starten, um die Werte auszuwählen, die 1 nicht überschreiten, und schließlich eine „Erweiterung“ verwenden:

b = numpy.convolve(a, [1, 1, 1], mode="same") > 1 
b = b | numpy.r_[0, b[:-1]] | numpy.r_[b[1:], 0] 

Da dies die Python-Schleife vermeidet, sollte es schneller sein, als Ihr Ansatz, aber ich Timings nicht gemacht.

Eine Alternative ist eine zweite Faltung verwenden aufzuweiten:

kernel = [1, 1, 1] 
b = numpy.convolve(a, kernel, mode="same") > 1 
b = numpy.convolve(b, kernel, mode="same") > 0 

Wenn Sie SciPy zur Verfügung haben, noch eine weitere Option für die Erweiterung ist

b = numpy.convolve(a, [1, 1, 1], mode="same") > 1 
b = scipy.ndimage.morphology.binary_dilation(b) 

bearbeiten: Durch some timings tun, Ich fand, dass diese Lösung für große Arrays am schnellsten zu sein scheint:

b = numpy.convolve(a, kernel) > 1 
b[:-1] |= b[1:] # Shift and "smearing" to the *left* (smearing with b[1:] |= b[:-1] does not work) 
b[:-1] |= b[1:] # … and again! 
b = b[:-2] 

Für ein Array von einer Million Einträgen war es mehr als 200 mal schneller als die ursprüngliche Vorgehensweise auf meinem Computer. Wie von EOL in den Kommentaren hervorgehoben, könnte diese Lösung jedoch etwas fragil sein, da sie von den Implementierungsdetails von NumPy abhängt.

Answer 2

Sie können die „Faltung“ Summen auf effiziente Art und Weise berechnen mit:

>>> a0 = a[:-2] 
>>> a1 = a[1:-1] 
>>> a2 = a[2:] 
>>> a_large_sum = a0 + a1 + a2 > 1 

Aktualisieren von b kann dann effizient durchgeführt werden, indem man etwas schreiben, das bedeutet „mindestens eines der drei benachbarten a_large_sum Werte True“ :

>>> a_large_sum_0 = np.hstack([a_large_sum, [False, False]]) 
>>> a_large_sum_1 = np.hstack([[False], a_large_sum, [False]]) 
>>> a_large_sum_2 = np.hstack([[False, False], a_large_sum]) 

Sie erhalten dann 01: Sie zuerst a_large_sum Array auf die gleiche Anzahl von Elementen wie a (nach rechts, nach links und nach rechts und dann nach links) zurückreichenauf effiziente Art und Weise:

>>> b = a_large_sum_0 | a_large_sum_1 | a_large_sum_2 

Dies gibt das Ergebnis, das Sie erhalten, aber in einer sehr effizienten Art und Weise, durch eine Bündelung der NumPy interne schnelle Schleifen.

PS: Dieser Ansatz ist im Wesentlichen der gleiche wie Svens erste Lösung, aber ist viel mehr Fußgänger als Svens eleganter Code; es ist jedoch so schnell. Svens zweite Lösung (Doppel convolve()) ist noch eleganter, und es ist doppelt so schnell.

Answer 3

Vielleicht möchten Sie sich auch NumPy's stride_tricks ansehen. Mit Svens Timing-Setup (siehe Link in Svens Antwort), fand ich, dass für (sehr) große Arrays, ist dies auch eine schnelle Art und Weise zu tun, was Sie wollen (dh mit Ihrer Definition von a):

shape = (len(a)-2,3) 
strides = a.strides+a.strides 
a_strided = numpy.lib.stride_tricks.as_strided(a, shape=shape, strides=strides) 
b = np.r_[numpy.sum(a_strided, axis=-1) > 1, False, False] 
b[2:] |= b[1:-1] | b[:-2] 

Nach dem Bearbeiten (siehe Kommentare unten) ist es nicht mehr der schnellste Weg.

Dies erstellt eine besonders detaillierte Ansicht Ihres ursprünglichen Arrays. Die Daten in a werden nicht kopiert, sondern einfach neu betrachtet. Wir wollen im Grunde ein neues Array erstellen, in dem der letzte Index die Sub-Arrays enthält, die wir summieren wollen (d. H. Die drei Elemente, die Sie summieren wollen). Auf diese Weise können wir am Ende leicht mit dem letzten Befehl summieren.

Das letzte Element dieser neuen Form hat daher 3, und das erste Element zu sein, wird die Länge der alten a minus 2 sein (weil wir nur auf die -2 nd Element zusammenfassen können).

Die Schrittliste enthält die Schritte in Byte, die das neue Array a_strided ausführen muss, um zum nächsten Element in jeder Dimension der Form zu gelangen. Wenn Sie diese gleich setzen, bedeutet dies, dass und a_strided[1,0] beide a[1] sind, was genau das ist, was wir wollen. In einem normalen Array wäre dies nicht der Fall (der erste Schritt wäre "Größe der ersten Dimension mal Länge der Anordnung - erste Dimension (= Form [0])"), aber in diesem Fall können wir Nutze es gut.

Nicht sicher, ob ich das alles wirklich gut erklärt habe, aber nur a_stride ausgedruckt und Sie werden sehen, was das Ergebnis ist und wie einfach dies die Operation macht.