How to efficiently compute all the index distances of 1's in a huge list of 0's and 1's?

Question

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 }.

Answer 1

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.

Answer 2

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.

Answer 3

Differences@SparseArray[L]["AdjacencyLists"]

{4, 5, 3}

Answer 4

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.