Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
How to turn sequence of a(K+x) consecutive elements into sequence of consecutive a*K elements and zeros

Subject: How to turn sequence of a(K+x) consecutive elements into sequence of consecutive a*K elements and zeros

From: Andrea

Date: 29 Dec, 2011 19:30:09

Message: 1 of 7

Hi,

I have an array formed of zeros and 1s, I need to modify it so that all the sequence of 1s composed of more than a*K (with "a" = positive integer) elements is reduced to a sequence of a*K 1s. I want to do this in the fastest possible way (hence without using any loop).

Example:
K = 3
1 0 0 1 1 1 1 0 1 1 1 1 1 1 1 0

should become

1 0 0 1 1 1 0 0 1 1 1 1 1 1 0 0


I had a look here:
http://www.mathworks.com/matlabcentral/newsreader/view_thread/271940

and I know how to get the start and end position of each sequence of 1s, and hence their lengths, but then I don't know how to modify the array to get the desired result.
Any ideas?

Thanks

Subject: How to turn sequence of a(K+x) consecutive elements into sequence of consecutive a*K elements and zeros

From: Roger Stafford

Date: 30 Dec, 2011 02:35:09

Message: 2 of 7

"Andrea" wrote in message <jdif41$qq7$1@newscl01ah.mathworks.com>...
> I have an array formed of zeros and 1s, I need to modify it so that all the sequence of 1s composed of more than a*K (with "a" = positive integer) elements is reduced to a sequence of a*K 1s. I want to do this in the fastest possible way (hence without using any loop).
- - - - - - - -
  The following is a rather contorted vectorization. If I were you I would consider a while-loop solution, Andrea.

  Let x be the given vector.

 t = diff([0,x,0]);
 f1 = find(t==1);
 f2 = find(t==-1)-f1;
 f2 = (f2>k).*(k*floor(f2/k))+(f2<=k).*f2+f1;
 y = zeros(1,size(x,2)+1);
 y(f1) = ones(1,size(f1,2));
 y(f2) = -ones(1,size(f2,2));
 y = y(1:size(x,2));
 y = cumsum(y);

Roger Stafford

Subject: How to turn sequence of a(K+x) consecutive elements into sequence of consecutive a*K elements and zeros

From: Matt J

Date: 30 Dec, 2011 15:48:07

Message: 3 of 7

"Andrea" wrote in message <jdif41$qq7$1@newscl01ah.mathworks.com>...
> Hi,
>
> I have an array formed of zeros and 1s, I need to modify it so that all the sequence of 1s composed of more than a*K (with "a" = positive integer) elements is reduced to a sequence of a*K 1s. I want to do this in the fastest possible way (hence without using any loop).
>
> Example:
> K = 3
> 1 0 0 1 1 1 1 0 1 1 1 1 1 1 1 0
>
> should become
>
> 1 0 0 1 1 1 0 0 1 1 1 1 1 1 0 0
=======================


With x the given vector:

xnew=strrep([x,0],[ones(1,K),0],[ones(1,K-1),0]);
  xnew(end)=[];

Subject: How to turn sequence of a(K+x) consecutive elements into sequence of consecutive a*K elements and zeros

From: Roger Stafford

Date: 30 Dec, 2011 21:24:08

Message: 4 of 7

"Matt J" wrote in message <jdkmfn$s3b$1@newscl01ah.mathworks.com>...
> xnew=strrep([x,0],[ones(1,K),0],[ones(1,K-1),0]);
> xnew(end)=[];
- - - - - - - -
  Andrea, the loop I referred to might look something like this:

 y = [x,0];
 c = 0;
 for p = 1:length(y)
  if y(p) == 1
   c = c + 1;
  else
   if c > k
    y(p+(-mod(c,k):-1)) = 0;
   end
   c = 0;
  end
 end
 y(end) = [];

You ought to compare its timing with any vectorized solution. It might surprise you.

  By the way, the vectorized solution I gave you could be simplified to:

t = diff([0,x,0]);
f1 = find(t==1);
f2 = find(t==-1)-f1;
f2 = f2-(f2>k).*mod(f2,k)+f1;
y = zeros(1,size(x,2)+1);
y(f1) = 1;
y(f2) = -1;
y(end) = [];
y = cumsum(y);

  Matt, as it stands I think your suggestion would reduce the length of the vector. Perhaps you meant this

 xnew=strrep([x,0],[ones(1,K),0],[ones(1,K-1),0,0]);

instead. However, as I understand Andrea's request, with say k = 10 a sequence of 19 consecutive ones should be replaced by 10 ones followed by 9 zeros, so even the above modification would not accomplish this. It would need to be performed k-1 times to be certain of success in all cases. (At least that's true with the way 'strrep' works on my antiquated system.)

Roger Stafford

Subject: How to turn sequence of a(K+x) consecutive elements into sequence of consecutive a*K elements and zeros

From: Matt J

Date: 30 Dec, 2011 22:52:08

Message: 5 of 7

"Roger Stafford" wrote in message <jdla5o$33p$1@newscl01ah.mathworks.com>...
>
  However, as I understand Andrea's request, with say k = 10 a sequence of 19 consecutive ones should be replaced by 10 ones followed by 9 zeros, so even the above modification would not accomplish this. It would need to be performed k-1 times to be certain of success in all cases. (At least that's true with the way 'strrep' works on my antiquated system.)
==================


Ah. Well then, here's another possibility:


 xchar=[0,char(x),0];


starts= strfind(xchar,char([0,1]));
stops = strfind(xchar,char([1,0]));
runlengths=stops-starts;
newstops=starts + max(floor(runlengths/K)*K,1);


%some trimming - could save computation
idx=newstops<stops;
starts=starts(idx);
stops=stops(idx);
newstops=newstops(idx);

xnew=x;
for ii=1:length(stops)
 xnew(newstops(ii):stops(ii))=0;
end

Subject: How to turn sequence of a(K+x) consecutive elements into sequence of consecutive a*K elements and zeros

From: Matt J

Date: 30 Dec, 2011 22:57:08

Message: 6 of 7

"Andrea" wrote in message <jdif41$qq7$1@newscl01ah.mathworks.com>...
>
> I want to do this in the fastest possible way (hence without using any loop).
==============

Not "hence without using any loop".
You really mean, "if need be, without using any loop"

There's a pretty good chance that looping will be faster in this case than any vectorized solution.

Subject: How to turn sequence of a(K+x) consecutive elements into sequence of consecutive a*K elements and zeros

From: Andrea

Date: 31 Dec, 2011 10:29:09

Message: 7 of 7

"Matt J" wrote in message <jdlfk3$ivv$1@newscl01ah.mathworks.com>...
> "Andrea" wrote in message <jdif41$qq7$1@newscl01ah.mathworks.com>...
> >
> > I want to do this in the fastest possible way (hence without using any loop).
> ==============
>
> Not "hence without using any loop".
> You really mean, "if need be, without using any loop"
>
> There's a pretty good chance that looping will be faster in this case than any vectorized solution.

Matt and Roger,

Thanks to both of you.

Matt, the arrays I'm dealing with are relatively big (1-2 million rows), that's why I assumed the vectorized version to be faster. But I guess the best approach would be to test both cases and find out empirically ;)

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us