# How to perform logical AND on intervals of contiguous locations

116 views (last 30 days)
Arturo Camacho Lozano on 23 Sep 2020 at 23:44
Commented: Arturo Camacho Lozano on 30 Sep 2020 at 23:07
I have the following problem. Let's say I have the arrays
x = logical([0, 1, 0,0, 1,1, 0,0,0, 1,1,1, 0])
y = logical([0, 1, 1,0, 1,1, 0,1,0, 1,0,1, 0])
Array X has three intervals of 1's with indices 2:2, 5:6, and 10:12. I want to apply an "interval AND" operation to X, based on Y, in the following sense: for each interval of ones in X, if any element in Y is zero in that interval, the whole interval is zeroed, i.e., Z = intervalAND(X,Y) should be the same as
z = logical([0, 1, 0,0, 1,1, 0,0,0, 0,0,0, 0])
Let me explain. Since all(Y(2:2)) = 1, it produces ones in Z(2:2). The same happens in the second interval (5:6): Both Y(5) and Y(6) are true, producing ones in Z. However, there is a zero in Y(10:12) which zeroes the whole interval Z(10:12).
I know how to do it with a for loop:
d = diff(x);
pos = find(d == 1);
neg = find(d == -1);
z = x;
for k = 1:length(neg)
interval = pos(k)+1 : neg(k);
if ~all(y(interval))
z(interval) = false;
end
end
However, I need to vectorize it to make it run faster (I am working with huge arrays). Does someone know how to compute Z without using a for/while loop?

Show 1 older comment
Arturo Camacho Lozano on 24 Sep 2020 at 0:33
To make it simpler, I explained it using an array, but x is actually a column of a matrix X of size 2000 times 100 (approx.). The script produces many matrices like that one. To give you an idea of the problem, whatever is inside the for loop is being called 40 million times (in a 4 minutes song, which is the application). I would prefer not using a mex routine, because Matlab is being used only for prototyping.
James Tursa on 24 Sep 2020 at 0:38
Is the algorithm running on each column individually, or running across the entire matrix as a whole? I.e., does the 1's logic extend across columns?
Arturo Camacho Lozano on 24 Sep 2020 at 0:54
Each column is independant. The same column vector Y is applied to all columns, though.

Bruno Luong on 24 Sep 2020 at 6:40
Edited: Bruno Luong on 25 Sep 2020 at 5:35
x = logical([0, 1, 0,0, 1,1, 0,0,0, 1,1,1, 0])
y = logical([0, 1, 1,0, 1,1, 0,1,0, 1,0,1, 0])
code without loop or groupping, on my bench test about 3 time faster than Stephen's accumarray solution
i = find(diff([0 x 0]));
n = histc(find(~y), i);
j = [1;-1]*(n(1:2:end)==0);
if x(end)
i(end)=[];
j(end)=[];
end
z = logical(cumsum(accumarray(i(:),j(:),[length(x),1])));

Arturo Camacho Lozano on 25 Sep 2020 at 23:33
What is the advantage (if any) of the latter? (The code looks more complex and verbose.)
Bruno Luong on 26 Sep 2020 at 6:01
Faster. It does not create unecessary elements to accumulate then removed.
The one before is still OK if you prefer readable code.
Arturo Camacho Lozano on 30 Sep 2020 at 23:07
Thanks four answer. This implementation works way faster than other proposed implementations that use "splitapply". Besides, it was easy to port to the target language (Python).

Mohammad Sami on 24 Sep 2020 at 1:31
You can group based on the values of x.
gid = cumsum(x ~= circshift(x,1));
if(gid(1) == 0)
gid = gid + 1;
end
a = splitapply(@min,y,gid);
z = a(gid);

#### 1 Comment

Arturo Camacho Lozano on 25 Sep 2020 at 15:55
Great! It needs a small adjusment, though. The second argument to splitapply should be x&y:
a = splitapply(@min, x&y, gid);
Let me clarify. If we change the fourth element of Y to 1, i.e.
x = logical([0, 1, 0,0, 1,1, 0,0,0, 1,1,1, 0])
y = logical([0, 1, 1,1, 1,1, 0,1,0, 1,0,1, 0])
the output should be the same as before:
z = logical([0, 1, 0,0, 1,1, 0,0,0, 0,0,0, 0])
because there was already a 0 in that position of X.

Matt J on 25 Sep 2020 at 0:34
Using group1s from
>> xg=group1s(x)+1;
>> yg=splitapply(@all,y,xg);
>> z=yg(xg)
z =
1×13 logical array
0 1 0 0 1 1 0 0 0 0 0 0 0