Count consecutive positions with the same value

Question

I want to program a function that counts the successive positions with the same value:

In[]= ConsecutiveValues[{1, 1, 1, 1, 2, 2, 1, 0}]
Out[]= {4, 2, 1, 1}

In fact, I can program this using loops and such, but I have the feeling that there is a nicer, more Mathematicaesque way to do it.

Thanks!

Answer 1

Most straightforward method

Use Split:

consecutiveValues[l_List] := Length /@ Split[l]

This is both fast and simple

Using linked lists

Note that patterns are by themselves not necessarily very slow, if constructed efficiently. Below is a recursive version, based on linked lists, which is about 5 times slower than the above Split-based version on large lists (which is not bad for purely top-level implementation), but has correct asymptotic complexity (linear):

toLinkedList[l_List] := Fold[{#2, #1} &, {}, Reverse@l]

Clear[cValsRec];
cValsRec[l_List] := cValsRec[toLinkedList@l, {{}, 0}];
cValsRec[{}, counts_] := Most@Flatten[counts];
cValsRec[{val_, tail : {val_, _List}}, {prev_List, count_}] :=
    cValsRec[tail, {prev, count + 1}];
cValsRec[{val_, tail_List}, {prev_List, count_}] :=
    cValsRec[tail, {{prev, count + 1}, 0}];

You use it as

cValsRec[{1, 1, 1, 1, 2, 2, 1, 0}]

The above function is properly tail-recursive in Mathematica sense. Note that for large lists, you may want to wrap the call in Block[{$IterationLimit = Infinity},...].

This is not the first time that I promote the use of linked lists. In my opinion, they are underused in Mathematica. Generally, they can very often be used for problems involving ragged lists, and /or the need of some look-ahead behavior in list processing, as an idiomatic (and often faster) alternative to procedural loops. The advantage of linked lists is that they bring reasonable (for the top-level code), and easily predictable performance, can be coded straightforwardly, and the code is declarative (easy to understand). And in some cases, the use of linked lists leads to dramatic performance improvements.

The need for speed

It is possible to beat Split-based method, performance-wise. Here is how:

ClearAll[cvalsAlt];
cvalsAlt[l_List] :=
 With[{pos = 
         Flatten[
            SparseArray[
               Unitize[Subtract @@ Partition[l, Length[l] - 1, 1]]
            ]["NonzeroPositions"]]
        },
    Differences[{0}~Join~pos~Join~{Length[l]}]
 ]

According to my benchmarks, this method is 4-5 times faster than the one based on Split.

Answer 2

Leonid's answer is very straightforward and I doubt it can be beat. Nevertheless, here's another approach using pattern matching and rule replacements to get the same result:

consecutiveValues[l_List] := l /. x_Integer :> {x, 1} //. 
    {h___, {x_, i_}, {x_, j_}, t___} :> {h, {x, i + j}, t} /. {_, x_} :> x

Answer 3

I cannot beat Split but if that function did not exist I might use:

f=
 Reap[
   Fold[If[# == #2, i++; #, Sow[i]; i = 1; #2] &, "!", # ~Append~ "!"]
 ][[2, 1, 2;;]] &;

f @ {1, 1, 1, 1, 2, 2, 1, 0}

{4, 2, 1, 1}

"!" is an arbitrary object that will not appear in the list.

Or, taking a pattern based approach at the expense of performance I might use:

f = # /. {x : Longest[p_ ..], y___} :> Prepend[f@{y}, Length@{x}] &;

f @ {1, 1, 1, 1, 2, 2, 1, 0}

{4, 2, 1, 1}