convert consecutive ones into alternating one/zero's

2012 11 27
5 个回答
回答已采纳
4 次查看（30 天）

2 个投票

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?

5 个评论
显示 3更早的评论 隐藏 3更早的评论

Jan
Jan 2012-11-27
Please explain the wanted procedure with enough details. Currently it is unlikely that we can guess the conversion rules exactly.
William Reinders
William Reinders 2012-11-27
编辑：Image Analyst 2012-11-27
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
Jan 2012-11-27
编辑：Jan 2012-11-27
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
Arthur 2012-11-27
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
Jan 2012-11-27
+1: Thanks for this interesting problem. Sometime I love the bit nudging.

请先登录，再进行评论。

请先登录，再回答此问题。

 采纳的回答

Matt Fig
Matt Fig 2012-11-27

2 个投票

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

5 个评论
显示 3更早的评论 隐藏 3更早的评论

Jan
Jan 2012-11-27
编辑：Jan 2012-11-27
Perhaps length(A) is evaluated repeatedly, or the JIT is smart enough to avoid this.
Matt Fig
Matt Fig 2012-11-27
编辑：Matt Fig 2012-11-27
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
Jan 2012-11-27
编辑：Jan 2012-11-27
+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
Matt Fig 2012-11-27
I compared exactly with your cleaned up FOR loop. (The one I commented on, not the MEX you later posted.)
Jan
Jan 2012-11-28
@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.

请先登录，再进行评论。

更多回答（4 个）

Sean de Wolski
Sean de Wolski 2012-11-27

1 个投票

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!
Jan
Jan 2012-11-27
编辑：Jan 2012-11-27

1 个投票

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.
Image Analyst
Image Analyst 2012-11-27

0 个投票

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
Jan
Jan 2012-11-27
编辑：Jan 2012-11-28

0 个投票

#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)

2 个评论
显示 无 隐藏 无

William Reinders
William Reinders 2012-11-28
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
Jan 2012-11-28
  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.

请先登录，再进行评论。

类别

在 帮助中心 和 File Exchange 中查找有关 Loops and Conditional Statements 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by