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