Thread Subject: Split a monotonic array

I have a strict sorted array such as

A = [ 8 17 24 29 33 36 39 45 56 64 ]

I would like to split this array into non-overlapping parts such that: in each part A is bracketed in a interval not larger than a given length said dmax=30.

So in the above I would have

A1 = [ 8 17 24 ]
A2 = [ 29 29 33 36 39 45 ]
A3 = [ 56 64 ]

I have tried free algorithms to split A and return the indexes
- Engine1: two while loops that run linearly on A
- Engine2: replaced the inner loop by FIND
- Engine3: use interp1 and while loop (favorite now, but not entirely happy)

My array A has a dimension of 10^5 - 10^6.

Can you find a better or faster way to split it? Thanks.

Here is what I tested.

% Data
A =cumsum(round(2+10*rand(1,1E5)));
dmax = 30

% Engine 1, nested while loop
tic
startidx=zeros(size(A));
A(end+1)=Inf;
next=1;
counter=1;
while next<length(A)
    startidx(counter)=next;
    upper=A(next)+dmax;
    next=next+1;
    while A(next)<=upper
        next = next+1;
    end
    counter=counter+1;
end
A(end)=[];
startidx(counter:end)=[];
lastidx=[startidx(2:end)-1 length(A)];
toc % 0.505895 seconds.

% Engine 2, while loop with find
tic
startidx=zeros(size(A));
last=1;
A(end+1)=Inf;
next=1;
counter=1;
while next<length(A)
    startidx(counter)=next;
    upper=A(next)+dmax;
    i=find(A(next:end)>upper,1,'first');
    next=i+next-1;
    counter=counter+1;
end
A(end)=[];
startidx(counter:end)=[];
lastidx=[startidx(2:end)-1 length(A)];
toc % 19.047071 seconds.

% Engine 3, interp1
tic
upper=A+dmax;
iupper=interp1(A, (1:length(A)), upper);
iupper=floor(iupper)+1;
startidx=zeros(size(A));
counter=1;
startidx(counter)=1;
s=1;
while s<=length(iupper)
    s=iupper(s);
    counter=counter+1;
    startidx(counter)=s;
end
startidx(counter:end)=[];
lastidx=[startidx(2:end)-1 length(A)];
toc % 0.075530 seconds.

% Bruno

Bruno Luong wrote:
> I have a strict sorted array such as
> A = [ 8 17 24 29 33 36 39 45 56 64 ]
> I would like to split this array into non-overlapping parts such that: in each
> part A is bracketed in a interval not larger than a given length said dmax=30.
> So in the above I would have
> A1 = [ 8 17 24 ]
> A2 = [ 29 29 33 36 39 45 ]
> A3 = [ 56 64 ]

idx = cumsum([1, diff(A) > dmax]);

Then A(K) goes in to B{idx(K)}
(though I haven't given the loop to make that happen ;-) )

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gdg54q$3e1$1@fred.mathworks.com>...
> I have a strict sorted array such as
>
> A = [ 8 17 24 29 33 36 39 45 56 64 ]
>
> I would like to split this array into non-overlapping parts such that: in each part A is bracketed in a interval not larger than a given length said dmax=30.
>
> So in the above I would have
>
> A1 = [ 8 17 24 ]
> A2 = [ 29 29 33 36 39 45 ]
> A3 = [ 56 64 ]

How do you justify breaking these points
into 3 pieces with a window of width 30?

It seems that a window of width 30 would
span from 8-36, and a second window
would span the rest of the way. So what
rules will you define?

John

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <gdgdq9$g9a$1@fred.mathworks.com>...
>
> It seems that a window of width 30 would
> span from 8-36, and a second window
> would span the rest of the way. So what
> rules will you define?
>

You are right John, for dmax=30 it should be

A1: [ 8 17 24 29 33 36 ]
A2: [39 45 56 64]

The results I gave correspond to dmax=20. Sorry about the confusion.

Bruno

Walter Roberson <roberson@hushmail.com> wrote in message <T6OKk.2593$JT3.2410@newsfe03.iad>...

>
> idx = cumsum([1, diff(A) > dmax]);
>

Hi Walter,

Ah no, that is not I want. What I want is split so that the difference between last and the first element all each parts is smaller than dmax. Not the different between two consecutive elements.

Bruno

PS: Application: This is for sequential memmapfile reading,. I read a random records (indexed by A) from a large file and I want to avoid working with a large memory block.

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gdg54q$3e1$1@fred.mathworks.com>...
> I have a strict sorted array such as
>
> A = [ 8 17 24 29 33 36 39 45 56 64 ]
>
> I would like to split this array into non-overlapping parts such that: in each part A is bracketed in a interval not larger than a given length said dmax=30.
>
> So in the above I would have
>
> A1 = [ 8 17 24 ]
> A2 = [ 29 29 33 36 39 45 ]
> A3 = [ 56 64 ]
>
> I have tried free algorithms to split A

Are you willing to use histc to bin the elements?

[junk,bins] = histc(A,A(1):dmax:A(end));

John

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gdg54q$3e1$1@fred.mathworks.com>...
> I have a strict sorted array such as
>
> A = [ 8 17 24 29 33 36 39 45 56 64 ]
>
> I would like to split this array into non-overlapping parts such that: in each part A is bracketed in a interval not larger than a given length said dmax=30.
>
> So in the above I would have
>
> A1 = [ 8 17 24 ]
> A2 = [ 29 29 33 36 39 45 ]
> A3 = [ 56 64 ]
>

Hi Bruno,

here is a one-liner

A = [ 8 17 24 29 33 36 39 45 56 64 ]
dmax = 20
C = mat2cell(A,1,diff(unique([0 floor(interp1(A,1:numel(A),A(1)+d:d:A(end))) numel(A)])))

Note that A should be monotonic, and the result is a cell array instead of N distinct variables.

hth
Jos

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <gdhtid$fb4$1@fred.mathworks.com>...
>
> Are you willing to use histc to bin the elements?
>
> [junk,bins] = histc(A,A(1):dmax:A(end));
>

Hi John,

Not sure how it would affect the performance of my application, because it might be not optimal since the number of bins is larger, thus later my application calls more memmapfile than it needs to.

Bruno

"Jos " <DELjos@jasenDEL.nl> wrote in message <gdhtkr$g3c$1@fred.mathworks.com>...

> >
>
> Hi Bruno,
>
> here is a one-liner
>
> A = [ 8 17 24 29 33 36 39 45 56 64 ]
> dmax = 20
> C = mat2cell(A,1,diff(unique([0 floor(interp1(A,1:numel(A),A(1)+d:d:A(end))) numel(A)])))
>

Hi Jos,

What is your "d"? I tried d=dmax but it does seem to give the same splitting than mine.

Bruno

"Jos " <DELjos@jasenDEL.nl> wrote in message <gdhtkr$g3c$1@fred.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gdg54q$3e1$1@fred.mathworks.com>...
> > I have a strict sorted array such as
> >
> > A = [ 8 17 24 29 33 36 39 45 56 64 ]
> >
> > I would like to split this array into non-overlapping parts such that: in each part A is bracketed in a interval not larger than a given length said dmax=30.
> >
> > So in the above I would have
> >
> > A1 = [ 8 17 24 ]
> > A2 = [ 29 29 33 36 39 45 ]
> > A3 = [ 56 64 ]
> >
>
> Hi Bruno,
>
> here is a one-liner
>
> A = [ 8 17 24 29 33 36 39 45 56 64 ]
> dmax = 20
> C = mat2cell(A,1,diff(unique([0 floor(interp1(A,1:numel(A),A(1)+d:d:A(end))) numel(A)])))
>
> Note that A should be monotonic, and the result is a cell array instead of N distinct variables.
>
> hth
> Jos
>

after some re-thinking this will only work for certain types of input. Here's a safer approach:

i = 1 ;
j = i+1 ;
k = 1 ;
clear C
while j <= numel(A)
    if (A(j)-A(i)) > d,
        C{k} = A(i:j-1) ;
        k = k + 1 ;
        i = j ;
    end
    j = j + 1 ;
end
if i<numel(A),
    C{k} = A(i:end) ;
end

hth
Jos