Grouping continguous values in a numpy array with their length
<p>In numpy / scipy (or pure python if you prefer), what would be a good way to group contiguous regions in a numpy array and count the length of these regions?</p>

<p>Something like this:</p>

<pre><code>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

&gt;&gt; [[1,3], [2,2], [3,1], [0,5], [1,1], [2,1], [3,1], [1,2], [0,3]]
</code></pre>

<p>I have tried to do this just with loops however it takes a longer time than I would like (6 seconds) to do a list with about 30 million samples and 20000 contiguous regions. </p>

<p>Edit:</p>

<p>And now for some speed comparisons (just using time.clock() and a few hundred iterations, or less if it is in seconds). </p>

<p>Firstly my python loop code tested on 5 samples. </p>

<pre><code>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...
</code></pre>

<p>And now with Divakar's vectorized solution.</p>

<pre><code>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...
</code></pre>

<p>Modified approach gives roughly same times (maybe 5% slower at worst)</p>

<p>And now with with the generator approach from Kasramvd.</p>

<pre><code>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...
</code></pre>

<p>And now his numpythonic version.</p>

<pre><code>Number of elements  33718251
Number of regions  135137
Time taken = 0.286336 seconds...

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

Memory error sample 3 (too many regions)

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

Number of elements  16619539
Number of regions  19293
Time taken = 0.084963 seconds...
</code></pre>

<p>Anyway I think the moral of the story is that numpy is very good. </p>

<p>here is a Numpyhonic-pythonic approach:</p>

<pre><code>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)]
</code></pre>

<p>Here is a generator based approach using <code>itertools.groupby()</code>:</p>

<pre><code>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)]
</code></pre>

<p>Or :</p>

<pre><code>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]])
</code></pre>

python arrays performance numpy