Finde Länge von Sequenzen von identischen Werten in einem numpy Array

In einem Pylab-Programm (das wohl auch ein Matlab-Programm sein könnte) habe ich ein numpy Array von Zahlen, die Distanzen darstellen: d[t] ist die Distanz zum Zeitpunkt t (und die Zeitspanne meiner Daten ist len(d) Zeiteinheiten) .

Die Ereignisse, an denen ich interessiert bin, sind, wenn der Abstand unterhalb einer bestimmten Schwelle liegt, und ich möchte die Dauer dieser Ereignisse berechnen. Es ist einfach, eine Reihe von Booleschen mit b = d<threshold , und das Problem kommt auf die Berechnung der Sequenz der Längen der True-only Wörter in b . Aber ich weiß nicht, wie man das effizient macht (dh mit numpy primitives), und ich habe es geschafft, das Array zu gehen und manuelle Änderungserkennung durchzuführen (dh Initialisierungszähler, wenn Wert von False zu True geht, Zähler erhöhen, solange Wert wahr ist , Und geben Sie den Zähler an die Sequenz aus, wenn der Wert auf False zurückkehrt). Aber das ist ungeheuer langsam

Wie kann man diese Art von Sequenzen in numpy Arrays effizient erkennen?

Unten ist ein paar Python-Code, der mein Problem veranschaulicht: Der vierte Punkt dauert sehr lange, um zu erscheinen (wenn nicht, erhöhen Sie die Größe des Arrays)

 from pylab import * threshold = 7 print '.' d = 10*rand(10000000) print '.' b = d<threshold print '.' durations=[] for i in xrange(len(b)): if b[i] and (i==0 or not b[i-1]): counter=1 if i>0 and b[i-1] and b[i]: counter+=1 if (b[i-1] and not b[i]) or i==len(b)-1: durations.append(counter) print '.' 

5 Solutions collect form web for “Finde Länge von Sequenzen von identischen Werten in einem numpy Array”

Während nicht numpy primitives, itertools Funktionen sind oft sehr schnell, so geben Sie diese eine versuchen (und messen mal für verschiedene Lösungen einschließlich dieser, natürlich):

 def runs_of_ones(bits): for bit, group in itertools.groupby(bits): if bit: yield sum(group) 

Wenn Sie die Werte in einer Liste benötigen, können Sie einfach die Liste (run_of_ones (Bits)), natürlich; Aber vielleicht könnte ein Listenverständnis noch geringfügig schneller sein:

 def runs_of_ones_list(bits): return [sum(g) for b, g in itertools.groupby(bits) if b] 

Umzug zu "numpy-native" Möglichkeiten, was ist mit:

 def runs_of_ones_array(bits): # make sure all runs of ones are well-bounded bounded = numpy.hstack(([0], bits, [0])) # get 1 at run starts and -1 at run ends difs = numpy.diff(bounded) run_starts, = numpy.where(difs > 0) run_ends, = numpy.where(difs < 0) return run_ends - run_starts 

Wieder: Achten Sie darauf, Lösungen gegeneinander in realistisch-für-Sie Beispiele zu benchmark!

Völlig numpy vektorisierte und generische RLE für jedes Array (arbeitet mit Strings, Booleans etc.).

Ausgabe von Tupel von Lauflängen, Startpositionen und Werten.

 import numpy as np def rle(inarray): """ run length encoding. Partial credit to R rle function. Multi datatype arrays catered for including non Numpy returns: tuple (runlengths, startpositions, values) """ ia = np.array(inarray) # force numpy n = len(ia) if n == 0: return (None, None, None) else: y = np.array(ia[1:] != ia[:-1]) # pairwise unequal (string safe) i = np.append(np.where(y), n - 1) # must include last element posi z = np.diff(np.append(-1, i)) # run lengths p = np.cumsum(np.append(0, z))[:-1] # positions return(z, p, ia[i]) 

Ziemlich schnell (i7):

 xx = np.random.randint(0, 5, 1000000) %timeit yy = rle(xx) 100 loops, best of 3: 18.6 ms per loop 

Mehrere Datentypen:

 rle([True, True, True, False, True, False, False]) Out[8]: (array([3, 1, 1, 2]), array([0, 3, 4, 5]), array([ True, False, True, False], dtype=bool)) rle(np.array([5, 4, 4, 4, 4, 0, 0])) Out[9]: (array([1, 4, 2]), array([0, 1, 5]), array([5, 4, 0])) rle(["hello", "hello", "my", "friend", "okay", "okay", "bye"]) Out[10]: (array([2, 1, 1, 2, 1]), array([0, 2, 3, 4, 6]), array(['hello', 'my', 'friend', 'okay', 'bye'], dtype='|S6')) 

Gleiche Ergebnisse wie Alex Martelli oben:

 xx = np.random.randint(0, 2, 20) xx Out[60]: array([1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1]) am = runs_of_ones_array(xx) tb = rle(xx) am Out[63]: array([4, 5, 2, 5]) tb[0][tb[2] == 1] Out[64]: array([4, 5, 2, 5]) %timeit runs_of_ones_array(xx) 10000 loops, best of 3: 28.5 µs per loop %timeit rle(xx) 10000 loops, best of 3: 38.2 µs per loop 

Etwas langsamer als Alex (aber immer noch sehr schnell) und viel flexibler.

Nur für den Fall, dass jemand neugierig ist (und da Sie MATLAB im Vorbeigehen erwähnt haben), hier ist ein Weg, um es in MATLAB zu lösen:

 threshold = 7; d = 10*rand(1,100000); % Sample data b = diff([false (d < threshold) false]); durations = find(b == -1)-find(b == 1); 

Ich bin nicht zu vertraut mit Python, aber vielleicht könnte dies helfen Ihnen einige Ideen. =)

Hier ist eine Lösung, die nur Arrays verwendet: Es nimmt ein Array mit einer Sequenz von Bools und zählt die Länge der Übergänge.

 >>> from numpy import array, arange >>> b = array([0,0,0,1,1,1,0,0,0,1,1,1,1,0,0], dtype=bool) >>> sw = (b[:-1] ^ b[1:]); print sw [False False True False False True False False True False False False True False] >>> isw = arange(len(sw))[sw]; print isw [ 2 5 8 12] >>> lens = isw[1::2] - isw[::2]; print lens [3 4] 

sw enthält ein wahres, wo es einen Schalter gibt, isw wandelt sie in isw . Die Gegenstände von isw werden dann paarweise in der lens subtrahiert.

Beachten Sie, dass, wenn die Sequenz mit einer 1 gestartet wurde, die Länge der 0s-Sequenzen zählen würde: Dies kann in der Indizierung behoben werden, um das Objektiv zu berechnen. Auch habe ich keine Eckfälle wie Sequenzen der Länge 1 getestet.


Vollständige Funktion, die Startpositionen und Längen aller True Subarrays zurückgibt.

 import numpy as np def count_adjacent_true(arr): assert len(arr.shape) == 1 assert arr.dtype == np.bool if arr.size == 0: return np.empty(0, dtype=int), np.empty(0, dtype=int) sw = np.insert(arr[1:] ^ arr[:-1], [0, arr.shape[0]-1], values=True) swi = np.arange(sw.shape[0])[sw] offset = 0 if arr[0] else 1 lengths = swi[offset+1::2] - swi[offset:-1:2] return swi[offset:-1:2], lengths 

Getestet für verschiedene bool 1D-Arrays (leeres Array, einzelne / mehrere Elemente, gerade / ungerade Längen, begonnen mit True / False , mit nur True / False Elementen).

 durations = [] counter = 0 for bool in b: if bool: counter += 1 elif counter > 0: durations.append(counter) counter = 0 if counter > 0: durations.append(counter) 
Python ist die beste Programmiersprache der Welt.