Moving window with cumulative sum less than a ref value and excluding certain windows

I have an array of 36000 cells, i want to break those arrays into windows of cumulative sum less than a reference value. and exclude few windows based on other parameters respective to this array based on index. For example A= [ 0.5 0.6 .45 .56 .056 .16 .18 .10 .15 .45 .36]; similarly other arrays of same length. Now window 1 should start with 1st value and end at sum less than 2 ( window{1} = [0.5 0.6 .45], sum = 1.55) second window has to start from 2nd value ( window{2} = [0.6 .45 .56 .056 .16], sum = 1.826). Similarly i need all possible windows for 36000 cells, while excluding those where value/sum of other arrays/windows of respective index. Index of these windows is also needed. I here wanted a moving window. Eg Index of my windows would be like [ 1 3] , [2 6], [3 9], [4 10], [5 11], [6 11], [ 7 11], [ 8 11], [9 11], [10, 11].

• If i don't wont to consider values in index 3,4, 8, i want to exclude windows which include these indexes.
• If i want to exclude windows whose corresponding array average is less than certain value. Ex: I've another B whose size is same as A. after breaking array A into windows, average of array B windows is less than a value (20) has to be excluded.

[John BG]

Ranjith

this is John BG (<mailto:[e-mail] [e-mail]>), I have corrected the sum for the complete data and reduced run time below 2 seconds, I mean for the 36000 long vector, please have a look at the added script.

The one that takes 20 minutes may be J Chilleri's

Would you please be so kind to acknowledge that my code works ok?

Let me know if you would like any modification.

Appreciating time and attention, awaiting answer

John BG

<mailto:[e-mail] [e-mail]>

[Image Analyst]

RANJITH, please attach some data. I'd like to know if your data is really in cells like you said, or if it's a regular double array. Cell arrays are very slow and inefficient memory hogs - the drawbacks to their being really flexible as to what kind of data they can hold. If you're using cells then I encourage you to see if you can use a standard numerical array, which will speed things up. I can't tell if you're using cells (like MATLAB definition, not Excel's definition) or standard arrays because you're using both braces (like cell arrays use) and brackets (like standard arrays use). But maybe you're using the term cell like Excel uses it - this would be "element" in MATLAB's terminology - I don't know which. Plus, attaching data would help out the people who are trying to solve your question.

[RANJITH REDDY KALLURI]

I here attach the data that needs to be breakdown into windows of sum less than 39.12 or a reference value.

Answer 1

[John BG]

Ranji

This is John BG <mailto:[e-mail] [e-mail]> , all together in one block

load Array.mat;
tic
A2=cumsum(A);
numA=numel(A);
n1=1;n2=1;
B=[0 0];
t0=38.19;
while n1<numA || n2<numA 
    while A(n1)==0 
        n1=n1+1;
        n2=n2+1; 
    end
    while A2(n2)-A2(n1)<t0  && n2<numA
        n2=n2+1;
        while A(n2)==0 
            n2=n2+1; 
        end
    end
    B=[B;n1 n2-1];
    n1=n1+1;
    n2=n1;
end
B(1,:)=[]

% masking

mask=[3 4 8];
d=0;
for n=mask
   for k=1:1:size(B,1)
       if intersect([B(k,1):1:B(k,2)],n)
          d=[d k];     
       end
   end
end
d(1)=[];
d=unique(d);d=sort(d);
B(d,:)=[];

reasons why I ask you to consider accepting my answer:

1. my code works, no errors like Jan Simon's Out(end,:)=[36800 36799]

2. my excluding mask section doesn't crash, like Simon's.

3. from 1.7 seconds to 0.5 seconds .. if it's really about cutting down time, C should be the language to use.

4. Ranji, If it's really about speed you may want to compile it, which will require the coder to get it all through C before building the .exe and then functions cumsum and find are going to add many more lines and end up taking more time than the few lines I have supplied.

5. the warning error that Jan Simon claims does not show up in MATLAB version R2016, it may happen in his MATLAB version R2009 but not in up to date MATLAB version.

6. his recommendation ' .. This is always a bad programming practize .. ' is the typical pointless remark that does not contribute to help solve the question.

[Jan]

Shouldn't the last line be [36800, 36800]? [36799, 36799] ignores the last element.

As said before: Your code crashes, if the input contains trailing zeros:

while A(n2)==0 
  n2=n2+1; 
end

From 1.7 to 0.5 seconds only by using pre-allocation and omit the zeros? This is a nice speed up. Feel free to insert the pre-allocation lines in your code to increase its quality.

The editor of R2016b shows the message in the lines "B=[B;n1 n2-1];" and "d=[d k];" as the orange marks in ths MLint-warning column on the rigt side:

 The variable 'B' appears to change size on every loop iteration.
 Consider pre-allocation for speed.

When the code for the masking is included also, your code needs 8.46 sec, and my suggestion 0.28 sec. The severe drawback of a missing pre-allocation is the exponential growing of the runtime: If the input array A has the double size, your code needs 55.3 sec already compared to 0.6 of mine. As you can see, pre-allocation is fundamental in programming and it does matter the solution here also. For more details search for "Schlemiel the Painter's algorithm", e.g. https://en.wikipedia.org/wiki/Joel_Spolsky:

 In software development, a Shlemiel the painter's algorithm
 (sometimes, Shlemiel the painter algorithm) is a method that is
 inefficient because the programmer has overlooked some
 fundamental issues at the very lowest levels of software design.

Therefore your statement "typical pointless remark" means, that you did not get the point.

Answer 2

[Andrei Bobrov]

I'm corrected, thank you Jan Simon.

A= [ 0.5 0.6 .45 .56 .056 .16 .18 .10 .15 .45 .36]' ;

out = zeros(numel(A),2);
n = numel(A);
t = 2;
for ii = 1:n
    z = cumsum(A(ii:n)) < t;
    out(ii,:) = [ii, find(z,1,'last') + ii - 1]  ;
end

[RANJITH REDDY KALLURI]

@Andrei Bobrov, your code is so fast. and the sum of each windows that i got here are little more than 39.12. i want them to be equal to/less than 39.12 Thanks in advance

[RANJITH REDDY KALLURI]

A small change in the above code works good. and A can be the array i've attached in the question.

A= [ 0.5 0.6 .45 .56 .056 .16 .18 .10 .15 .45 .36]' ;
out = zeros(numel(A),2);
n = numel(A);
t = 39.12;
for ii = 1:n
  z = cumsum(A(ii:n)) < t;
  out(ii,:) = [0,find(z,1,'last')-1]+ii;
end

[Jan]

You can reduce the length of the cumsum'ed vector, if you estimate a maximum possible length at first:

maxLen = t / min(A);
for ii = 1:n
  z = cumsum(A(ii:min(n, ii + maxLen))) < t;
  out(ii,:) = [ii, find(z, 1, 'last') - 1 + ii];
end

[RANJITH REDDY KALLURI]

@ Jan Simon , @Andrei , above code helps me to generate windows. I now need to exclude windows whose average value is less than 0.1473. and the windows has to rearrange.

[Andrei Bobrov]

A= [ 0.5 0.6 .45 .56 .056 .16 .18 .10 .15 .45 .36]' ;

t = 2;
tav = 0.1473;

n = numel(A);
wind = cell(n,1);
out = zeros(n,2);
lo = true(n,1);
for ii = 1:n
    jj = ii:n;
    tt = cumsum(A(ii:n));
    z = tt < t;
    iend = find(z,1,'last');
    lo(ii) = tt(iend)./jj(iend) >= tav;
    out(ii,:) = [ii,iend+ii-1];
    wind{ii} = A([ii:iend+ii-1]);
end
wind = wind(lo);
out = out(lo,:);

Answer 3

[John BG]

Let me split the question into 2:

1. generating window indices

A= [ 0.5 0.6 .45 .56 .056 .16 .18 .10 .15 .45 .36]

B={0}
for k=1:1:numel(A)
    s=0;n1=k ;n2=k
    while s<2
        s=s+sum(A([n1:n2]));
        if n2<numel(A)
            n2=n2+1;
        elseif n2>=numel(A)
            n2=numel(A);
        end
    end

      if n2<numel(A)
          B=[B [n1 n2-1 ]];
      elseif n2>=numel(A)
              B=[B [n1 n2]];
      end
  end

L=zeros(size(B,2)-2,2);
for k=2:1:size(B,2)-1
    L(k-1,:)=B{k}(:);
end

L contains the sought indices

L =
     1     3
     2     4
     3     5
     4     7
     5    11
     6    11
     7    11
     8    11
     9    11
    10    11

2.

Adding selectivity.

At this point I'm not sure whether you want to exclude any window that has in example index=3 then L would have rows 1 and 3 removed, or you also would like to have any window that implicitly has index 3, which then would mean that L row 2 would also be excluded

case 1: only excluding indices in given index, example 3:

[i  j]=find(L==3)
L(i,:)=[]
L =
     2     4
     4     7
     5    11
     6    11
     7    11
     8    11
     9    11
    10    11

case 2: excluding any window directly or implicitly referring a given index:

L=zeros(size(B,2)-2,2)  % restore L to initial result
for k=2:1:size(B,2)-1
    L(k-1,:)=B{k}(:)
end

d=0
for k=1:1:size(L,1)
    if intersect([L(k,1):1:L(k,2)],3)
       d=[d k];     
    end
end
d(1)=[];
L(d,:)=[]

L =
     4     7
     5    11
     6    11
     7    11
     8    11
     9    11
    10    11

case 1, using a mask:

mask=[3 4 8]

L=zeros(size(B,2)-2,2)  % restore L to initial result
for k=2:1:size(B,2)-1
    L(k-1,:)=B{k}(:)
end

mask=[3 4 8]

q=0
for k=1:1:length(mask)
    [i  j]=find(L==mask(k))
    q=[q i(:)']
end
q(1)=[]
q=sort(q)

L(q,:)=[]
 L =
     5    11
     6    11 
     7    11
     9    11
    10    11

case 2, using a mask:

L=zeros(size(B,2)-2,2)  % restore L
for k=2:1:size(B,2)-1
    L(k-1,:)=B{k}(:)
end
mask=[3 4 8]

d=0

for n=mask
   for k=1:1:size(L,1)
       if intersect([L(k,1):1:L(k,2)],n)
          d=[d k];     
       end
   end
end

d(1)=[];
d=unique(d);d=sort(d)
L(d,:)=[]
L =
     9    11
    10    11

if you find these lines useful would you please mark my answer as Accepted Answer?

To any other reader, if you find this answer of any help please click on the thumbs-up vote link,

thanks in advance for time and attention

John BG

<mailto:[e-mail] [e-mail]>

[RANJITH REDDY KALLURI]

Thank you John, I can use section 1 and case 2 using mask, but when i wanted to run with my array which is attached here and sum less than 38.19. I changed S < 38.19 in the while loop, but the windows that are generated doesn't match my condition.

[John BG]

My code is really fast, below 2 minutes and L is available, try this

t0=38.19;
% get the window indices
B={0};
for k=1:1:numel(A)
    s=0;n1=k ;n2=k;
    while s<t0
        s=s+sum(A([n1:n2]));
        if n2<numel(A)
            n2=n2+1;
        elseif n2>=numel(A)
            n2=numel(A);
        end
    end

      if n2<numel(A)
          B=[B [n1 n2-1 ]];
      elseif n2>=numel(A)
              B=[B [n1 n2]];
      end
  end

L=zeros(size(B,2)-2,2)
for k=2:1:size(B,2)-1
    L(k-1,:)=B{k}(:);
end

[John BG]

Ranjith

once you have calculated L with my previous lines, apply the mask with the following code:

mask=[3 4 8]
L2=L  % make a copy just in case
d=0

for n=mask
   for k=1:1:size(L2,1)
       if intersect([L2(k,1):1:L2(k,2)],n)
          d=[d k];     
       end
   end
end

d(1)=[];
d=unique(d);d=sort(d)

L2(d,:)=[]

please let me know when you get this working

regards

John BG

[e-mail]

[RANJITH REDDY KALLURI]

Thank you John, the code worked in less than 3 minutes, but when i sum the cells which i've got from array 'L'. but the sum i get is not at all close to 38.19. Can you once check it.

[John BG]

Ranji

This is John BG [e-mail]

I have corrected the sum and managed to reduce run time below 2 seconds, please have a look and let me know if now my answer qualifies as Accepted Answer:

load Array.mat;
tic
A2=cumsum(A);
numA=numel(A);
n1=1;n2=1;
B=[0 0];
t0=38.19;

while n1<numA || n2<numA 
    while A(n1)==0 
        n1=n1+1;
        n2=n2+1; 
    end
    while A2(n2)-A2(n1)<t0  && n2<numA
        n2=n2+1;
        while A(n2)==0 
            n2=n2+1; 
        end
    end
    B=[B;n1 n2-1];
    n1=n1+1;
    n2=n1;
end
B(1,:)=[]
toc

Elapsed time is 1.740256 seconds.

B
=
         421        4623
         422        4623
         423        4623
         424        4623
         425        4623
         426        4623
         427        4623
         428        4623
         429        4623
         430        4623
..

         36789       36799
         36790       36799
         36791       36799
         36792       36799
         36793       36799
         36794       36799
         36795       36799
         36796       36799
         36797       36799
         36798       36799
         36799       36799

please find attach the resulting variable (without masking [3 4 8] that you ask in 2nd part of your question) in attached file result1.mat variable name B, type double, size 21593x2.

Adding selectivity

1. only excluding indices contained in mask

    mask=[3 4 8]
    q=0
    for k=1:1:length(mask)
        [i  j]=find(B==mask(k));
        q=[q i(:)'];
    end
    q(1)=[];
    q=sort(q);
    B(q,:)=[];
    B

2. excluding any window directly or implicitly referring any given index in mask

mask=[3 4 8]
d=0
for n=mask
   for k=1:1:size(B,1)
       if intersect([B(k,1):1:B(k,2)],n)
          d=[d k];     
       end
   end
end
d(1)=[];
d=unique(d);d=sort(d)
B(d,:)=[]

Ranji

Because you probably want a longer mask I have only attached the initial selection in attached file result1.mat

Since my answer solves your question much faster than any other provided here, would you please be so kind to consider marking my answer as Accepted Answer?

thanks for time and attention, awaiting answer

John BG

<mailto:[e-mail] [e-mail]>

Answer 4

[John Chilleri]

Hello,

I tossed this together real quick so there might be unforeseen errors, but this should work:

% Given A
window = cell(36000,1);
window_index = cell(36000,1);
for i = 1:36000
  count = i;
  while (sum(A(i:count) < 2))
      if (count == 36000)
          count = count+1;
          break;
      end
      count = count + 1;
  end
  window{i} = A(i:count-1);
  window_index{i} = i:count-1;
end

% Deleting windows containing undesired indices
Undesired = [];
for i = 1:36000
  for j = 1:length(Undesired)
      if (sum(window_index{i} == Undesired(j)) == 0)
          window{i} = [];
          window_index{i} = [];
          break;
      end
  end
end

Note that you need to give A and fill in Undesired. Otherwise it will make the windows empty that have undesirable indices, so if you access them after "removal" they'll be empty.

Hope this helps!

[RANJITH REDDY KALLURI]

Thanks John, Your code is taking more than 20 minutes to create windows itself. I here attach the array i was trying to use. And the cumulative sum has to be less than 38.19.

Answer 5

[John BG]

Ranji

This is John BG [e-mail]

I have corrected the sum and managed to reduce run time below 2 seconds, please have a look and let me know if now my answer qualifies as Accepted Answer:

load Array.mat;
tic
A2=cumsum(A);
numA=numel(A);
n1=1;n2=1;
B=[0 0];
t0=38.19;
while n1<numA || n2<numA 
    while A(n1)==0 
        n1=n1+1;
        n2=n2+1; 
    end
    while A2(n2)-A2(n1)<t0  && n2<numA
        n2=n2+1;
        while A(n2)==0 
            n2=n2+1; 
        end
    end
    B=[B;n1 n2-1];
    n1=n1+1;
    n2=n1;
end
B(1,:)=[]
toc
Elapsed time is 1.740256 seconds.
B
=
         421        4623
         422        4623
         423        4623
         424        4623
         425        4623
         426        4623
         427        4623
         428        4623
         429        4623
         430        4623
..
         36789       36799
         36790       36799
         36791       36799
         36792       36799
         36793       36799
         36794       36799
         36795       36799
         36796       36799
         36797       36799
         36798       36799
         36799       36799

.

please find attach the resulting variable (without masking [3 4 8] that you ask in 2nd part of your question) in attached file result1.mat variable name B, type double, size 21593x2.

Adding selectivity

1. only excluding indices contained in mask

    mask=[3 4 8]
      q=0
      for k=1:1:length(mask)
          [i  j]=find(B==mask(k));
          q=[q i(:)'];
      end
      q(1)=[];
      q=sort(q);
      B(q,:)=[];
      B
2. excluding any window directly or implicitly referring any given index in mask

mask=[3 4 8]
d=0
for n=mask
   for k=1:1:size(B,1)
       if intersect([B(k,1):1:B(k,2)],n)
          d=[d k];     
       end
   end
end
d(1)=[];
d=unique(d);d=sort(d)
B(d,:)=[]

.

Ranji

Because you probably want a longer mask I have only attached the initial selection in attached file result1.mat

Since my answer solves your question much faster than any other provided here, would you please be so kind to consider marking my answer as Accepted Answer?

thanks for time and attention, awaiting answer

John BG

<mailto:[e-mail] [e-mail]>

[Jan]

@John BG: Matlab's editor shows an important message for your code: In "B=[B;n1 n2-1]" the array grows iteratively. This is always a bad programming practize. Use a pre-allocation instead:

% Before the loop:
B = zeros(numA, 2);
iB = 0;

% Instead of B=[B;n1 n2-1]:
iB = iB + 1;
B(iB, :) = [n1, n2-1];

% After the loop:
B = B(1:iB, :);

This reduces the runtime on my machine from 2.86 to 1.34 seconds.

The "while A(n2)==0" will fail if A contains trailing zeros.

At least under the old Matlab R2009a I can use currently, creating "A" dynamically by "load Array.mat" increases the runtime by a factor of 50. This allows the JIT acceleration to operate efficiently:

FileData = load('C:\Local\Array.mat');
A = FileData.A;

But this will most likely not matter the code of the OP, because the data are provided as file for the discussion in the forum only.

When the data contain a lot of zeros, removing them will accelerate the processing:

Index = find(A);
A = A(Index);
... as above
B = Index(B);  % Get original indices back

This gives an additional boost of 40% on my machine. See my answer.

Answer 6

[Jan]

The part for finding the intervals:

FileData = load('C:\Local\Array.mat');
A        = FileData.A;

Index = find(A);
AA    = A(Index);        % Ignore zeros in cumulative sum
A2    = cumsum(AA);
numAA = numel(AA);
Out   = zeros(numAA, 2);  % Pre-allocation
t0    = 38.19;
for n1 = 1:numAA
    n2 = n1;
    while A2(n2) - A2(n1) < t0 && n2 < numAA
        n2 = n2 + 1;
    end
    Out(n1, 1) = Index(n1);
    Out(n1, 2) = Index(n2) - 1;
end
Out(numAA, 2) = numel(A);  % Fix last element

This needs 0.57 sec on my machine compared to 2.86 sec of John BG's suggestion.

[EDITED] [EDITED2: Bugfix: "B"->"Out"]

exclude = [3, 4, 8];
mask    = false(size(Out, 1), 1);
for k = 1:numel(exclude)
  mask = mask | (Out(:, 1) >= exclude(k) & exclude(k) <= Out(:, 2));
end
Out(mask, :) = [];

[RANJITH REDDY KALLURI]

@Jan Simon, your code works faster for creating the windows, but i needed to exclude few windows. I've used @john code of masking. I've mixed two codes as per my requirement. As i cannot accept two answer's can you write code for excluding windows to accept your answer

[Jan]

See [EDITED]. Does this do what you want?

[John BG]

the last line of the answer of Jan Simon is not valid.

Out([end-10:end],:)
ans =
       36790       36799
       36791       36799
       36792       36799
       36793       36799
       36794       36799
       36795       36799
       36796       36799
       36797       36799
       36798       36799
       36799       36799
       36800       36799

it should be

B([end-10:end],:)
ans =
       36789       36799
       36790       36799
       36791       36799
       36792       36799
       36793       36799
       36794       36799
       36795       36799
       36796       36799
       36797       36799
       36798       36799
       36799       36799

and the Jan Simon's [EDITED] section to apply the mask crashes:

exclude = [3, 4, 8];
mask    = false(1, size(Out, 1));
for k = 1:numel(exclude)
  mask = mask | (B(:, 1) >= exclude(k) & exclude(k) <= B(:, 2));
end
B(mask, :) = [];
Error using  | 
Matrix dimensions must agree.

[Jan]

@John BG: [36799, 36799] seems not be correct also, because [36800, 36800] is the last element.

Thanks for finding this bug: While the output is called "Out" in my code, I used "B" here by accident. This is fixed now.