Ermittelt die Länge der Sequenzen von identischen Werten in einer numpy Array (Lauflängencodierung)

Question

In einem pylab Programm (das wahrscheinlich auch ein Matlab-Programm sein könnte) Ich habe eine numpy Reihe von Zahlen, die Entfernungen: d[t] ist die Abstand zum Zeitpunkt t (und die Zeitspanne von meinen Daten len(d) Zeiteinheiten).

Die Ereignisse, die ich interessiert bin, wenn der Abstand unter einem bestimmten Schwellenwert ist, und ich möchte die Dauer dieser Ereignisse berechnen. Es ist einfach eine Reihe von booleans mit b = d<threshold zu bekommen, und das Problem kommt auf die Reihenfolge der Längen der True nur Worte in b zu berechnen. Aber ich weiß nicht, wie das effizient zu tun (dh numpy Primitiven verwendet wird), und ich griff das Array zu gehen und manuelle Änderungserkennung zu tun (dh Zähler initialisieren, wenn der Wert von false auf true geht, erhöhen Zähler solange Wert True und die Ausgabe der Zähler auf die Sequenz, wenn Wert auf false zurückgeht). Aber das ist ungeheuer langsam.

Wie efficienly erkennt diese Art von Sequenzen in numpy Arrays?

Im Folgenden finden Sie einige Python-Code, der mein Problem zeigt: der vierte Punkt eine sehr lange Zeit in Anspruch nimmt 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 '.'

Answer 1

Während nicht Primitiven numpy, itertools Funktionen sind oft sehr schnell, so zu tun geben diesem eine Chance (und messen Zeiten 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 tun müssen, kann nur verwenden Liste (runs_of_ones (Bits)), natürlich; aber vielleicht eine Liste Verständnis könnte geringfügig schneller sein noch:

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

Der Umzug in "numpy-native" Möglichkeiten, was ist:

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

Auch hier: achten Sie darauf, Benchmark-Lösungen gegen jeden anderen in realistisch-for-you Beispiele

Answer 2

Voll numpy vektorisiert und generische RLE für jedes Array (funktioniert mit Streichern, booleans etc auch).

Ausgänge 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.asarray(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])

Pretty 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'))

Die gleiche Ergebnis 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.

Answer 3

Hier ist eine Lösung unter Verwendung von nur Arrays. Es eine Anordnung nimmt eine Folge von bools und zählt die Länge der Übergänge mit

>>> 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 eine wahre, wo ein Schalter ist, isw sie in Indizes umwandelt. Die Elemente von isw werden dann paarweise in lens subtrahiert wird.

Beachten Sie, dass, wenn die Sequenz mit einer 1 gestartet wäre es, die Länge der 0er-Sequenzen zählen: Dies kann in der Indizierung fixiert werden Linse zu berechnen. Auch habe ich nicht getestet Eckfällen solche Sequenzen der Länge 1.

---

Volle Funktion, die Positionen und Längen aller True-Sub-Arrays zurückgibt starten.

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

Getestete für verschiedene bool 1D-Arrays (Leer-Anordnung; einzelne / mehrere Elemente; gerade / ungerade Längen; begann mit True / False; mit nur True / False Elemente)

.

Answer 4

Für den Fall, jemand ist neugierig (und da Sie MATLAB beiläufig erwähnt), hier ist eine Möglichkeit, 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 allzu vertraut mit Python, aber vielleicht könnte dies hilft Ihnen ein paar Ideen. =)

Answer 5

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)