11
$\begingroup$

Although I am an experienced C programmer, I am somewhat new to functional programming. Therefore I am a bit embarrassed to ask questions regarding such a simple problem. Any how...

I have a huge list of 0's and 1's (with many more 0's than 1's) with about 10,000 elements. I want to compute all index distances between consecutive 1's, and from that list build an histogram. Any efficient ideas?

For instance: Consider the list L={ 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0}.

The distances list would be D={ 4, 5, 3 }.

$\endgroup$
  • 6
    $\begingroup$ Differences@Position[1]@L or take a look at SparseArray and "Nonzeropositions": 100661 $\endgroup$ – Kuba Sep 10 '16 at 11:32
14
$\begingroup$

For a sparse list:

list = RandomChoice[{0.8, 0.2} -> {0, 1}, 10000];

Flatten[Differences@SparseArray[list]["NonzeroPositions"]]

Less efficient than the SparseArray method, but still performs nicely:

(* alternative #1 *)
Values@KeyDrop[Counts[Accumulate@list], 0]

(* alternative #2 *)
With[{l = Accumulate@list}, BinCounts[l, {1, l[[-1]], 1}]]

The performance ratio (greater or less than 1) between these last two will depend on the sparse density and length of the list.

$\endgroup$
10
$\begingroup$

Considering your L:

diff = Differences @ Flatten @ Position[L, 1]

{4, 5, 3}

Also, Flatten may not be applied to Position but to Differences, or it may not be applied at all - then diff will be a list of single-element (i.e., differences) lists.

A list of $10^4$ elements is easily handled by Mathematica: it takes only 0.004 seconds to provide diff in this case. For a list of size $10^8$ it takes 15.5 sec on my machine.

And btw, D is a built-in command so don't use it as a name of something. A safe practice it to always use lowercase names and variables.

NOTE: Xavier's approach using SparseArray with "NonzeroPositions" is $\sim 6$ times faster.

$\endgroup$
7
$\begingroup$
Differences@SparseArray[L]["AdjacencyLists"]

{4, 5, 3}

$\endgroup$
3
$\begingroup$

After not much researching I found a one line solution myself, which I post now:

Histogram[Differences[Flatten[Position[L, 1]]]]

will do the trick.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.