Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2006
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2006

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Fastest method for comparing overlapping times in random time series

  • To: mathgroup at smc.vnet.net
  • Subject: [mg65054] Re: Fastest method for comparing overlapping times in random time series
  • From: Maxim <m.r at inbox.ru>
  • Date: Sun, 12 Mar 2006 23:59:19 -0500 (EST)
  • References: <dulspn$3an$1@smc.vnet.net>
  • Sender: owner-wri-mathgroup at wolfram.com

On Wed, 8 Mar 2006 06:15:19 +0000 (UTC), Prince-Wright, Robert G SEPCO  
<robert.prince-wright at shell.com> wrote:

> I have two lists, list1{ {t1,t1+dt1}, {t2,t2+dt2},..{ti,ti+dti}}, and
> list2, each representing 'time(i)' and corresponding 'time(i) +
> deltatime(i)'. The time(i) values are determined by an exponential
> inter-arrival time model, and the durations are a scaled uniform random
> variable. Both lists are ordered on time(i). You can think of list 1 as
> representing periods when System 1 is not working, and list 2 as the
> periods when System 2 is not working. Example lists are given as Cell
> Expressions below together with code to convert to a ticker-tape Plot
> (you may need to stretch the graphic to see clearly). The challenge is
> to develop a fast method for determining the periods when both Systems
> are not working, i.e. to create a list corresponding to the start and
> finish times of the overlaps.
>
>  Thus far I have only managed to use a Do loop which is very slow for  
> long lists!
>

If the coordinates of the points are machine numbers, the compiled code  
will be faster than IntervalIntersection:

In[1]:= f = Compile[{{L1, _Real, 2}, {L2, _Real, 2}},
   Module[{i1 = 1, i2 = 1, cnt = 0, cnt2 = 0, lt, rt,
       ans = Array[{0., 0.}&, Length@ L1 + Length@ L2]},
     While[i1 <= Length@ L1 && i2 <= Length@ L2,
       If[L1[[i1, 2]] < L2[[i2, 1]], i1++; Continue[]];
       If[L2[[i2, 2]] < L1[[i1, 1]], i2++; Continue[]];
       ans[[++cnt]] =
         {If[L1[[i1, 1]] > L2[[i2, 1]], L1[[i1, 1]], L2[[i2, 1]]],
          If[L1[[i1, 2]] < L2[[i2, 2]], L1[[i1++, 2]], L2[[i2++, 2]]]}
     ];
     {lt, rt} = ans[[1]];
     Do[
       If[ans[[i, 1]] < rt,
         If[ans[[i, 2]] > rt, rt = ans[[i, 2]]],
         ans[[++cnt2]] = {lt, rt}; {lt, rt} = ans[[i]]
       ],
       {i, 2, cnt}
     ];
     ans[[++cnt2]] = {lt, rt};
     Take[ans, cnt2]
]];

L1 = {#, # + 10^-5*Random[]}& /@ Sort@ Array[Random[]&, 10^5];
L2 = {#, # + 10^-5*Random[]}& /@ Sort@ Array[Random[]&, 10^5];

Timing[ans1 = IntervalIntersection @@ Interval @@@ {L1, L2};]
Timing[ans2 = f[L1, L2];]
List @@ ans1 === ans2

Out[4]= {1.453*Second, Null}

Out[5]= {0.313*Second, Null}

Out[6]= True

This assumes that the intervals are sorted but can overlap.

Maxim Rytin
m.r at inbox.ru


  • Prev by Date: Re: speed of evaluation of an instruction
  • Next by Date: Re: Mathematica and Education
  • Previous by thread: Re: Fastest method for comparing overlapping times in random time series
  • Next by thread: Outputs of the Limit function