Gruppieren von zusammenhängenden Werten in einer Reihe mit ihrer Länge

Question

In numpy/scipy (oder reinem Python, wenn Sie bevorzugen), was wäre eine gute Möglichkeit, zusammenhängende Regionen in einem numply-Array zu gruppieren und die Länge dieser Regionen zu zählen?

Etwas wie folgt aus:

x = np.array([1,1,1,2,2,3,0,0,0,0,0,1,2,3,1,1,0,0,0]) 
y = contiguousGroup(x) 
print y 

>> [[1,3], [2,2], [3,1], [0,5], [1,1], [2,1], [3,1], [1,2], [0,3]] 

Ich habe versucht, dies mit Schleifen nur zu tun, aber es ist eine längere Zeit in Anspruch nimmt, als ich möchte (6 Sekunden) eine Liste mit etwa 30 Millionen Proben und 20000 angrenzend zu tun Regionen.

Edit:

Und nun für einige Geschwindigkeitsvergleiche (nur mit time.clock() und ein paar hundert Iterationen oder weniger, wenn sie in Sekunden).

Zuerst mein Python-Loop-Code an 5 Proben getestet.

Number of elements 33718251 
Number of regions 135137 
Time taken = 8.644007 seconds... 

Number of elements 42503100 
Number of regions 6985 
Time taken = 10.533305 seconds... 

Number of elements 21841302 
Number of regions 7619335 
Time taken = 7.671015 seconds... 

Number of elements 19723928 
Number of regions 10799 
Time taken = 5.014807 seconds... 

Number of elements 16619539 
Number of regions 19293 
Time taken = 4.207359 seconds... 

Und jetzt mit der vektorisierten Lösung von Divakar.

Number of elements 33718251 
Number of regions 135137 
Time taken = 0.063470 seconds... 

Number of elements 42503100 
Number of regions 6985 
Time taken = 0.046293 seconds... 

Number of elements 21841302 
Number of regions 7619335 
Time taken = 1.654288 seconds... 

Number of elements 19723928 
Number of regions 10799 
Time taken = 0.022651 seconds... 

Number of elements 16619539 
Number of regions 19293 
Time taken = 0.021189 seconds... 

Modified Ansatz gibt etwa gleiche Zeiten (vielleicht 5% langsamer im schlimmsten Fall)

Und jetzt mit dem Generator Ansatz von Kasramvd.

Number of elements 33718251 
Number of regions 135137 
Time taken = 3.834922 seconds... 

Number of elements 42503100 
Number of regions 6985 
Time taken = 4.785480 seconds... 

Number of elements 21841302 
Number of regions 7619335 
Time taken = 6.806867 seconds... 

Number of elements 19723928 
Number of regions 10799 
Time taken = 2.264413 seconds... 

Number of elements 16619539 
Number of regions 19293 
Time taken = 1.778873 seconds... 

Und jetzt seine numpythonische Version.

Wie auch immer ich denke, die Moral der Geschichte ist, dass numpy sehr gut ist.

Answer 1

Hier ist ein vektorisiert Ansatz -

idx = np.concatenate(([0],np.flatnonzero(x[:-1]!=x[1:])+1,[x.size])) 
out = zip(x[idx[:-1]],np.diff(idx)) 

Probelauf -

In [34]: x 
Out[34]: array([1, 1, 1, 2, 2, 3, 0, 0, 0, 0, 0, 1, 2, 3, 1, 1, 0, 0, 0]) 

In [35]: out 
Out[35]: [(1, 3), (2, 2), (3, 1), (0, 5), (1, 1), (2, 1), (3, 1), (1, 2), (0, 3)] 

---

Die Verkettung auf das gesamte Array teuer sein könnte. So wird eine modifizierte Version, die Verkettung auf der Gruppe tut Indizes Verschiebung eher könnte man vorgeschlagen, wie so -

idx0 = np.flatnonzero(x[:-1]!=x[1:]) 
count = np.concatenate(([idx0[0]+1],np.diff(idx0),[x.size-idx0[-1]-1])) 
out = zip(x[np.append(0,idx0+1)],count) 

Alternativ im letzten Schritt, wenn der Ausgang als 2D Array in Ordnung, wir, dass zipping vermeiden könnten und verwenden NumPy des column_stack, wie so -

out = np.column_stack((x[np.append(0,idx0+1)],count)) 

Answer 2

hier ist ein Numpyhonic-pythonic Ansatz:

In [192]: [(i[0], len(i)) for i in np.split(x, np.where(np.diff(x) != 0)[0]+1)] 
Out[192]: [(1, 3), (2, 2), (3, 1), (0, 5), (1, 1), (2, 1), (3, 1), (1, 2), (0, 3)] 

hier ist ein Generator basierter Ansatz itertools.groupby() mit:

In [180]: from itertools import groupby 
In [181]: [(k, sum(1 for _ in g)) for k, g in groupby(x)] 
Out[181]: [(1, 3), (2, 2), (3, 1), (0, 5), (1, 1), (2, 1), (3, 1), (1, 2), (0, 3)] 

Oder:

In [213]: mask = np.diff(x) != 0 

In [216]: np.column_stack((np.concatenate((x[mask], [x[-1]])), map(len, np.split(x, np.where(mask)[0]+1)))) 
Out[216]: 
array([[1, 3], 
     [2, 2], 
     [3, 1], 
     [0, 5], 
     [1, 1], 
     [2, 1], 
     [3, 1], 
     [1, 2], 
     [0, 3]]) 

Answer 3

Alles, was Sie können müssen, ist np.diff und ist ein wenig leichter zu lesen. Erstelle eine Maske ...

x = np.array([1,1,1,2,2,3,0,0,0,0,0,1,2,3,1,1,0,0,0]) 
mask = np.where(np.diff(x) != 0)[0] 
mask = np.hstack((-1, mask, len(x)-1)) 

zip(x[mask[1:]], np.diff(mask)) 

Das einfachste sein sollte vollständig vektorisiert zu verstehen und (nicht sicher zip) ...