Count the occurence of a number in between other numbers

I need to extract the number of zeros of the vector highlighted below.

x = [ 1 0 0 1 1 1 0 1 1 0 0 0 0 0 1 1 0 1 0]

My expected outcome is,

y = [2 1 5 1 1]

I need to get the number of 0s in between the 1s. I tried several "for" and "while" loops. But wasnt able to get this result.

Appreciate if anyone can help me out.

Answer 1

[Stephen23]

This is simpler and actually works for all horizontal vectors (unlike the accepted answer):

>> x = [ 1 0 0 1 1 1 0 1 1 0 0 0 0 0 1 1 0 1 0];
>> D = diff([false,x==0,false]);
>> find(D<0)-find(D>0)
ans =
     2     1     5     1     1

For a slightly faster version you can call find once:

>> F = find(diff([false,x==0,false]));
>> F(2:2:end)-F(1:2:end)
ans =
     2     1     5     1     1

EDIT: uses Jan's logical vector suggestion.

[madhan ravi]

+1 stephen: Thank you for getting into detail but I am not sure how this solution is faster could you explain?

[Stephen23]

"...I am not sure how this solution is faster could you explain?"

You are right, it turns out that of the answers that actually work without error, Jan's strfind solution is fastest. For example 10e5 iteration on R2012b:

Elapsed time is 0.840650 seconds. % your answer (fails in many cases)
Elapsed time is 0.790226 seconds. % my answer (one FIND)
Elapsed time is 1.205834 seconds. % Jan's DIFF answer
Elapsed time is 0.735474 seconds. % Jan's STRFIND answer

I removed that claim from my answer.

[madhan ravi]

Nice analysis stephen, like I stated those cases would be satisfied with one simple if condition . But all credits to Jan he molded (optimised) the accepted answer otherwise it would have taken a long time to get the result.

[Stephen23]

"...like I stated those cases would be satisfied with one simple if condition ."

Please show how that would work.

[Ashane Fernando]

Hi Stephen,

Thank you for pointing out the limitation of the previously accepted answer.

I think your answer looks very straight forward and easy.

Answer 2

[Jan]

Another solution:

x = [ 1 0 0 1 1 1 0 1 1 0 0 0 0 0 1 1 0 1 0];
y = [1, x, 1];
strfind(y, [0,1]) - strfind(y, [1,0])

[madhan ravi]

+1 Jan

Answer 3

[Jan]

With FEX: RunLength :

[B, N] = RunLength(x);
Result = N(B == 0)

If you do not have a C-compiler installed, use RunLength_M from the same submission.

Without RunLength:

x = [ 1 0 0 1 1 1 0 1 1 0 0 0 0 0 1 1 0 1 0]

d = [true, diff(x) ~= 0];   % TRUE if values change
b = x(d);                   % Elements without repetitions
n = diff(find([d, true]));  % Number of repetitions
Result = n(b == 0)

[Ashane Fernando]

Thank you very much Jan

Answer 4

[madhan ravi]

index=find(x==0); % edited after Jan’s comment
idx=find(diff(index)~=1);
R=[idx(1) diff(idx) numel(index)-idx(end)]

[Jan]

You can avoid the indirection over the cell: x(x==0) is a vector of zeros only, so there is no need to extract it from the original data. Then mat2cell creates a cell containing vectors of zeros only to measure the number of elements. But these numbers are available already:

index = find(x==0);
idx   = find(diff(index)~=1);
R     = [idx(1), diff(idx), numel(index)-idx(end)];

For the input x = randi([0,1], 1,1e5) this increases the processing speed by about a factor of 40.

[madhan ravi]

Ah thanks for noting that Jan. I always admire the way how you optimize a code.

[Jan]

It is valuable to see the changes, because this allows others to learn to the potential for improvements:

% Original version:
index = find(x==0);
idx   = find(diff(index)~=1);
F     = mat2cell(x(x==0), 1,    [idx(1) diff(idx) numel(index)-idx(end)]);
% This is the solution already: ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
R     = cellfun(@numel, F);

[madhan ravi]

Very true and infact the third argument is much faster than the original version.

[Jan]

According to my measurement your fixed version is slightly faster than my Matlab code, which wastes time with counting the 1s also.

[madhan ravi]

Good to know all the possibilities Jan. Thank you!

[Ashane Fernando]

Thank you very much Ravi and Jan

[Stephen23]

Why so complex? Simpler and faster:

>> x = [ 1 0 0 1 1 1 0 1 1 0 0 0 0 0 1 1 0 1 0];
>> D = diff([0,x==0,0]);
>> find(D<0)-find(D>0)
ans =
   2   1   5   1   1

[Jan]

@Stephen: Please post this as additional solution. The list of different approaches is intersting.

[Stephen23]

Note that this answer fails for many simple cases, e.g.:

Only ones

>> x = [1,1,1,1];
>> index=find(x==0);
>> idx=find(diff(index)~=1);
>> R=[idx(1) diff(idx) numel(index)-idx(end)]
Attempted to access idx(1); index out of bounds because numel(idx)=0.

Ony zeros

>> x = [0,0,0,0];
>> index=find(x==0);
>> idx=find(diff(index)~=1);
>> R=[idx(1) diff(idx) numel(index)-idx(end)]
Attempted to access idx(1); index out of bounds because numel(idx)=0.

Empty vector

>> x = [];
>> index=find(x==0);
>> idx=find(diff(index)~=1);
>> R=[idx(1) diff(idx) numel(index)-idx(end)]
Attempted to access idx(1); index out of bounds because numel(idx)=0.

Leading Zeros

>> x = [0,1,1,1];
>> index=find(x==0);
>> idx=find(diff(index)~=1);
>> R=[idx(1) diff(idx) numel(index)-idx(end)]
Attempted to access idx(1); index out of bounds because numel(idx)=0.

Trailing Zeros

>> x = [1,1,1,0];
>> index=find(x==0);
>> idx=find(diff(index)~=1);
>> R=[idx(1) diff(idx) numel(index)-idx(end)]
Attempted to access idx(1); index out of bounds because numel(idx)=0. 

Its use of indexing means that any special cases will need to be handled separately.

See my answer for simpler code that works for all of these cases.

[madhan ravi]

Just a simple if condition would satisfy those needs.

[Stephen23]

"Just a simple if condition would satisfy those needs."

There are several problems with that approach:

1. How do you know that your IF covers all of the special cases? Can you prove that you have thought of every special case?
2. Extra complexity makes code harder to understand and maintain, and is more libale to bugs.
3. It just shifts the problem: okay, so you can detect a special case, but then how do you deal with it? Solution: by writing code that handles that special case... in which case, you still have to solve the same problem.
4. It really would not be that simple. Make a list of the cases for which your code fails: how would you deal with them using one IF statement?

[madhan ravi]

Yes it turns out lots of conditions are required :D.

Answer 5

[Jan]

See Jos solution (link):

D = diff(find(diff([false, x==0, false])));
R = D(1:2:end);

A short test (yes, I know that timeit is more accurate):

A = ones(1, 1e5);
A(randperm(1e5, 5e4)) = 0;

tic   % My strfind method
for k = 1:100
  D = [false, A==0, false];
  R = strfind(D, [true, false]) - strfind(D, [false,true]);
end
toc   % 0.182 seconds

tic   % My general RunLength code:
for k = 1:100
  d = [true, diff(A) ~= 0];
  b = A(d);
  n = diff(find([d, true]));
  Result = n(b == 0);
end
toc   % 0.220 seconds

tic   % Stephen's 2 FIND
for k = 1:100
  D = diff([0, A==0, 0]);
  R = find(D<0) - find(D>0);
end
toc   % 0.190 seconds

tic   % Stephen's 1 FIND (with modification)
for k = 1:100
  D = find(diff([false, A==0, false]));   % 10% faster than [0, A==0, 0] !
  R = D(2:2:end) - D(1:2:end);
end
toc   % 0.161 seconds,  was 0.172 with [0, A==0, 0]

tic   % Jos
for k = 1:100
  D = diff(find(diff([false, A==0, false])));
  R = D(1:2:end);
end
toc   % 0.161 seconds

[false, A==0, false] creates a logical vector, while [0, A==0, 0] is a double vector, which is 8 times larger.

I'm going to create a C-MEX function for this task, which avoids the time consuming explicit creation of [false, A==0, false].

[Jos (10584)]

Nice, Jan!

I think this shows the power of the matlab community: we all can learn from it! :-)