Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
How to turn sequence of a(K+x) consecutive elements into sequence of consecutive a*K elements and zeros
0 views
Skip to first unread message
Andrea
Dec 29, 2011, 2:30:09 PM12/29/11
to
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
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
Roger Stafford
Dec 29, 2011, 9:35:09 PM12/29/11
to
"Andrea" wrote in message <jdif41$qq7$1...@newscl01ah.mathworks.com>...
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
> 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
Matt J
Dec 30, 2011, 10:48:07 AM12/30/11
to
"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
=======================
>
> 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)=[];
Roger Stafford
Dec 30, 2011, 4:24:08 PM12/30/11
to
"Matt J" wrote in message <jdkmfn$s3b$1...@newscl01ah.mathworks.com>...
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
> xnew=strrep([x,0],[ones(1,K),0],[ones(1,K-1),0]);
> xnew(end)=[];
> 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;
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
Matt J
Dec 30, 2011, 5:52:08 PM12/30/11
to
"Roger Stafford" wrote in message <jdla5o$33p$1...@newscl01ah.mathworks.com>...
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
>
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.)
==================
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
Matt J
Dec 30, 2011, 5:57:08 PM12/30/11
to
> 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.
Andrea
Dec 31, 2011, 5:29:09 AM12/31/11
to
"Matt J" wrote in message <jdlfk3$ivv$1...@newscl01ah.mathworks.com>...
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 ;)
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 ;)
0 new messages