convert consecutive ones into alternating one/zero's

I need to convert a vector consisting of ones and zero's such that consecutive blocks of 1's will be replaced by alternating ones and zeros. Example:

[0 1 0 1 0 0 1 1 0 1 1 1 1 0 1] needs to be converted to:

[0 1 0 1 0 0 1 0 0 1 0 1 0 0 1]

Of course that can be done in a loop, but I'm looking for a vectorized way of accomplishing this. Any ideas?

[Jan]

Please explain the wanted procedure with enough details. Currently it is unlikely that we can guess the conversion rules exactly.

[William Reinders]

Maybe the best way to explain what I'm looking for is to write down how the desired result would be accomplished if I were to use a loop:

flags = [  < sequence of 0's and 1's here > ];
for i = 1:length(flags)-1
  if flags(i)==1 && flags(i+1)==1
    flags(i+1)=0; 
  end
end

[Jan]

Yes, William, now the problem is well defined.

Please search in the forum for instructions to format code. This has been explained several times in different locations.

[Arthur]

It is maybe more elegant to vectorize it, but do you really need it? The loop you suggest yourself is very easy to understand, and fast. For 1e6 flags it took my pc less then 40 ms. So I'd just go for the loop....

[Jan]

+1: Thanks for this interesting problem. Sometime I love the bit nudging.

Answer 1

[Matt Fig]

I would be surprised to find you could beat this loop:

ii = 2;

while ii<=length(A)
    if A(ii-1) && A(ii)
        A(ii) = 0;
        ii = ii + 2;
    else
        ii = ii + 1;
    end
end

[Jan]

Perhaps length(A) is evaluated repeatedly, or the JIT is smart enough to avoid this.

[Matt Fig]

When high density is assumed (A = rand(1,2e8)>.05;), this is significantly faster than the FOR loop. Predefining L=length(A) does not improve time one bit.

Elapsed time is 10.331379 seconds.
Elapsed time is 6.242883 seconds.

Of course a C-mex would be even faster!

[Jan]

+1: Nice speedup! Did you compare with the cleaned loop in my answer?

The MEX has the drawback, that it cannot perform the changes inplace, such that it has a larger memory consumption.

[Matt Fig]

I compared exactly with your cleaned up FOR loop. (The one I commented on, not the MEX you later posted.)

[Jan]

@Matt Fig: In the discussion about the performance of "Matlab compared to C" I claimed: "...performance is not an inherent feature of the language, but the programmer has to exploit the inner structure of problem...". Your WHILE approach is an excellent example: The behaviour of the system is used to avoid unneeded computations. A straight-forward loop approach cannot be "fast" in general. It is the job of the programmer to exploit the possibilities to avoid unnecessary work.

Answer 2

[Sean de Wolski]

One of many ways:

double(regexprep(char([0 1 0 1 0 0 1 1 0 1 1 1 1 0 1]),char([1 1]),char([1 0])))

hint This is certainly not the best way!

Answer 3

[Jan]

Compare the timings with this cleaned loop method:

for k = 2:length(flags)
  if flags(k-1) && flags(k)
    flags(k) = 0;
  end
end

Note, that the JIT accelerator can profit from using one command per line only.

[EDITED] I assume the program is noticably faster when flag is a logical array.

[Matt Fig]

+1 see the WHILE loop version too.

Answer 4

[Image Analyst]

Do you have the Image Processing Toolbox, because this is fairly easy if you have it, though you'd still need at least one for loop over each connected component but not two for loops like your brute force method would:

m = [0 1 0 1 0 0 1 1 0 1 1 1 1 0 1]

blobs = regionprops(logical(m), 'PixelIdxList');
for blobNumber = 1 : length(blobs)
  thisBlobsIndexes = blobs(blobNumber).PixelIdxList
  m(thisBlobsIndexes(2:2:end)) = 0;
end
% Print out
m

Answer 5

[Jan]

#include "mex.h"

void mexFunction(int nlhs, mxArray *plhs[], int nrhs, const mxArray *prhs[]) {
 mxLogical *In, *Out;
 mwSize i, n;

   if (!mxIsLogical(prhs[0])) {
      mexErrMsgTxt("Input must be a logical vector.");
   }

   In      = (mxLogical *) mxGetData(prhs[0]);
   n       = mxGetNumberOfElements(prhs[0]);
   plhs[0] = mxCreateLogicalMatrix(1, n);
   Out     = (mxLogical *) mxGetData(plhs[0]);

   /* The FOR loop approach: */
   /* Out[0] = In[0];
    * for (i = 1; i < n; i++) {
    *  if (In[i]) {
    *     if (!Out[i - 1]) {
    *        Out[i] = true;
    *     }
    *  }
    *}
    */

   /* Matt Fig's faster WHILE: */
   i = 2;
   while (i < n) {
      if (In[i] && !In[i - 1]) {
         Out[i] = true;
         i     += 2;
      } else {
         i++;
      }
   }

   return;
  }

Timings:

• Test data: A = rand(1, 1e8) > 0.05;
• Matlab 2009a/64, Win7, Core2Duo
• MEXed FOR loop: 0.49 sec
• MEXed WHILE loop: 0.28 sec
• Matlab WHILE: 1.26 sec
• Matlab FOR: 1.90 sec
• Original Matlab FOR: 2.33 sec (if A(i)==1 && A(i+1)==1)

[William Reinders]

Thanks for your elaborate answer. Just for my understanding: What causes the original Matlab FOR to be so much slower than the Matlab WHILE ?

[Jan]

1. The comparison with 1 in A(i)==1 && A(i+1)==1 consumes time. Using A(i) && A(i+1) is faster already.
2. When the while loop sets a value to 0, it avoids testing the following element, because it is not needed. If all elements of the inputs are non-zero, Matt Fig's method omits half of the tests.
3. In the Matlab version, the speedup of the loop is below the theoretical limit. I assume, the JIT acceleration handles the FOR loop more efficiently due to the fixed stepsize. In the MEXed version, the WHILE approach is 40% faster, which is near to the naiv expectations.