MathGroup Archive 2006

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

Search the Archive

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


Hi Robert again,
Here is another, more "functional" variant of my solution. Here no file is
written. It has approximately the same speed as the one I have sent earlier.

Prepare 2 lists of 500000 pairs:

list1 = Partition[Sort[Table[Random[Real, 
       {0, 10000}], {1000000}]], 2]; 
list2 = Partition[Sort[Table[Random[Real, 
       {0, 10000}], {1000000}]], 2]; 

Define a routine for the task:

bothon[list1_, list2_] := Module[{on1, on2, start}, 
   on1 = False; on2 = False; 
    (Switch[#1[[2]], 1, on1 = True; 
        If[on2, start = #1[[1]]]; Sequence @@ {}, 2, 
       on1 = False; If[on2, {start, #1[[1]]}, 
         Sequence @@ {}], 3, on2 = True; 
        If[on1, start = #1[[1]]]; Sequence @@ {}, 4, 
       on2 = False; If[on1, {start, #1[[1]]}, 
         Sequence @@ {}]] & ) /@ 
     Sort[Join[list1 /. {{0, 0} -> Sequence[], 
         {a1_Real, a2_Real} :> Sequence[{a1, 1}, 
           {a2, 2}]}, list2 /. {{0, 0} -> Sequence[], 
         {a1_Real, a2_Real} :> Sequence[{a1, 3}, 
           {a2, 4}]}]]]

If we call this function, and measure the time,

Timing[outlist = bothon[list1, list2]; ]

then I get 37 seconds on my computer.

You might check

Length[outlist] 

should give approx 500000, and

Sum[outlist[[i,2]] - outlist[[i,1]], 
  {i, Length[outlist]}]

should be approx 2500.

Best regards

Ingolf Dahl
Sweden

> -----Original Message-----
> From: Prince-Wright, Robert G SEPCO 
To: mathgroup at smc.vnet.net
> [mailto:robert.prince-wright at shell.com] 
> Sent: den 8 mars 2006 07:00
> To: mathgroup at smc.vnet.net
> Subject: [mg64981] [mg64935] Fastest method for comparing overlapping 
> times in random time series
> 
> 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!
> 
>  Bob
> 
>  Cell[BoxData[{
>      RowBox[{
>        RowBox[{"list1", " ", "=", " ",
>          RowBox[{"{",
>            RowBox[{
>              RowBox[{"{",
>                RowBox[{"0", ",", "0"}], "}"}], ",",
>              RowBox[{"{",
>                RowBox[{
>                "0.05645798683319917", ",", "0.15645798683319917"}],
>                "}"}], ",",
>              RowBox[{"{",
>                RowBox[{
>                "1.9882365926946939", ",", 
> "2.088236592694694"}], "}"}],
>               ",",
>              RowBox[{"{",
>                RowBox[{
>                "2.5208302083752088", ",", 
> "2.620830208375209"}], "}"}],
>               ",",
>              RowBox[{"{",
>                RowBox[{"4.331157770365525", ",", 
> "4.431157770365525"}],
>                 "}"}], ",",
>              RowBox[{"{",
>                RowBox[{"4.625648172106303", ",", 
> "4.725648172106303"}],
>                 "}"}], ",",
>              RowBox[{"{",
>                RowBox[{"5.175487639085017", ",", 
> "5.275487639085017"}],
>                 "}"}], ",",
>              RowBox[{"{",
>                RowBox[{
>                "5.1757438469277615", ",", 
> "5.275743846927761"}], "}"}],
>               ",",
>              RowBox[{"{",
>                RowBox[{"6.045682258365966", ",", 
> "6.145682258365966"}],
>                 "}"}], ",",
>              RowBox[{"{",
>                RowBox[{"6.095852116064159", ",", 
> "6.195852116064159"}],
>                 "}"}], ",",
>              RowBox[{"{",
>                RowBox[{
>                "7.9785370986659725", ",", 
> "8.078537098665972"}], "}"}],
>               ",",
>              RowBox[{"{",
>                RowBox[{"8.631481926529762", ",", 
> "8.731481926529762"}],
>                 "}"}], ",",
>              RowBox[{"{",
>                RowBox[{
>                "11.838817248234044", ",", "11.938817248234043"}],
>                "}"}], ",",
>              RowBox[{"{",
>                RowBox[{
>                "13.011561605316217", ",", "13.111561605316217"}],
>                "}"}], ",",
>              RowBox[{"{",
>                RowBox[{
>                "13.602685790907218", ",", "13.702685790907218"}],
>                "}"}], ",",
>              RowBox[{"{",
>                RowBox[{
>                "13.951488709158799", ",", "14.051488709158798"}],
>                "}"}], ",",
>              RowBox[{"{",
>                RowBox[{
>                "14.442239019684102", ",", "14.542239019684102"}],
>                "}"}], ",",
>              RowBox[{"{",
>                RowBox[{"18.18754842266018", ",", 
> "18.28754842266018"}],
>                 "}"}], ",",
>              RowBox[{"{",
>                RowBox[{
>                "19.375961049552153", ",", "19.475961049552154"}],
>                "}"}], ",",
>              RowBox[{"{",
>                RowBox[{
>                "19.390901816384638", ",", 
> "19.49090181638464"}], "}"}],
>               ",",
>              RowBox[{"{",
>                RowBox[{
>                "19.762843010650133", ",", "19.862843010650135"}],
>                "}"}], ",",
>              RowBox[{"{",
>                RowBox[{"22.75130803880397", ",", 
> "22.85130803880397"}],
>                 "}"}], ",",
>              RowBox[{"{",
>                RowBox[{"22.979236664808898", ",", 
> "23.0792366648089"}],
>                 "}"}], ",",
>              RowBox[{"{",
>                RowBox[{"23.21093816763214", ",", 
> "23.31093816763214"}],
>                 "}"}], ",",
>              RowBox[{"{",
>                RowBox[{
>                "23.964317142793327", ",", 
> "24.06431714279333"}], "}"}],
>               ",",
>              RowBox[{"{",
>                RowBox[{
>                "26.51374055268468", ",", 
> "26.613740552684682"}], "}"}],
>               ",",
>              RowBox[{"{",
>                RowBox[{
>                "27.177131249507614", ",", "27.277131249507615"}],
>                "}"}], ",",
>              RowBox[{"{",
>                RowBox[{"29.54136486314523", ",", 
> "29.64136486314523"}],
>                 "}"}], ",",
>              RowBox[{"{",
>                RowBox[{
>                "31.098216517356434", ",", "31.198216517356435"}],
>                "}"}], ",",
>              RowBox[{"{",
>                RowBox[{"32.51349069353667", ",", 
> "32.61349069353667"}],
>                 "}"}], ",",
>              RowBox[{"{",
>                RowBox[{
>                "32.58757836961991", ",", 
> "32.687578369619914"}], "}"}],
>               ",",
>             RowBox[{"{",
>                RowBox[{"34.95030403897159", ",", 
> "35.05030403897159"}],
>                 "}"}], ",",
>              RowBox[{"{",
>                RowBox[{
>                "35.26403635444476", ",", 
> "35.364036354444764"}], "}"}],
>               ",",
>              RowBox[{"{",
>                RowBox[{"36.54408072628277", ",", 
> "36.64408072628277"}],
>                 "}"}], ",",
>              RowBox[{"{",
>                RowBox[{
>                "37.015277949570155", ",", 
> "37.11527794957016"}], "}"}],
>               ",",
>              RowBox[{"{",
>                RowBox[{
>                "37.795100012257365", ",", "37.895100012257366"}],
>                "}"}], ",",
>              RowBox[{"{",
>                RowBox[{"38.27044933105397", ",", 
> "38.37044933105397"}],
>                 "}"}], ",",
>              RowBox[{"{",
>                RowBox[{"38.31393209217171", ",", 
> "38.41393209217171"}],
>                 "}"}]}], "}"}]}], ";"}], "\n",
>      RowBox[{
>        RowBox[{"list2", " ", "=", " ",
>          RowBox[{"{",
>            RowBox[{
>              RowBox[{"{",
>                RowBox[{"0", ",", "0"}], "}"}], ",",
>              RowBox[{"{",
>                RowBox[{
>                "0.42154338890169607", ",", "0.521543388901696"}],
>                "}"}], ",",
>              RowBox[{"{",
>                RowBox[{
>                "1.1782644371038296", ",", "1.2782644371038296"}],
>                "}"}], ",",
>              RowBox[{"{",
>                RowBox[{"2.844174260820493", ",", 
> "2.944174260820493"}],
>                 "}"}], ",",
>              RowBox[{"{",
>                RowBox[{"3.570085400452066", ",", 
> "3.670085400452066"}],
>                 "}"}], ",",
>              RowBox[{"{",
>                RowBox[{"6.504639588394373", ",", 
> "6.604639588394373"}],
>                 "}"}], ",",
>              RowBox[{"{",
>                RowBox[{
>                "6.5244845034642225", ",", 
> "6.624484503464222"}], "}"}],
>               ",",
>              RowBox[{"{",
>                RowBox[{"7.879515215234381", ",", 
> "7.979515215234381"}],
>                 "}"}], ",",
>              RowBox[> {"{",
>                RowBox[{
>                "12.599440581844581", ",", 
> "12.69944058184458"}], "}"}],
>               ",",
>              RowBox[{"{",
>                RowBox[{
>                "16.603408911827003", ",", "16.703408911827005"}],
>                "}"}], ",",
>              RowBox[{"{",
>                RowBox[{
>                "19.625732658966356", ",", "19.725732658966358"}],
>                "}"}], ",",
>              RowBox[{"{",
>                RowBox[{
>                "20.830464854375997", ",", "20.930464854375998"}],
>                "}"}], ",",
>              RowBox[{"{",
>                RowBox[{"21.65632426653098", ",", 
> "21.75632426653098"}],
>                 "}"}], ",",
>              RowBox[{"{",
>                RowBox[{
>                "21.994565267587653", ",", "22.094565267587654"}],
>                "}"}], ",",
>              RowBox[{"{",
>                RowBox[{"23.95348262109657", ",", 
> "24.05348262109657"}],
>                 "}"}], ",",
>              RowBox[{"{",
>                RowBox[{"25.33071396888203", ",", 
> "25.43071396888203"}],
>                 "}"}], ",",
>              RowBox[{"{",
>                RowBox[{
>                "25.810443407423513", ",", "25.910443407423514"}],
>                "}"}], ",",
>              RowBox[{"{",
>                RowBox[{"27.41242954052623", ",", 
> "27.51242954052623"}],
>                 "}"}], ",",
>              RowBox[{"{",
>                RowBox[{
>                "28.07577726500833", ",", 
> "28.175777265008332"}], "}"}],
>               ",",
>              RowBox[{"{",
>                RowBox[{
>                "31.04163569364224", ",", 
> "31.141635693642243"}], "}"}],
>               ",",
>              RowBox[{"{",
>                RowBox[{
>                "31.58601183335223", ",", 
> "31.686011833352232"}], "}"}],
>               ",",
>              RowBox[{"{",
>                RowBox[{"31.91119940453042", ",", 
> "32.01119940453042"}],
>                 "}"}], ",",
>              RowBox[{"{",
>                RowBox[{"32.44696426260659", ",", 
> "32.54696426260659"}],
>                 "}"}], ",",
>              RowBox[{"{",
>                RowBox[{"33.33470549081387", ",", 
> "33.43470549081387"}],
>                 "}"}], ",",
>              RowBox[{"{",
>                RowBox[{
>                "33.581270424444966", ",", 
> "33.68127042444497"}], "}"}],
>               ",",
>              RowBox[{"{",
>                RowBox[{"37.4575318812475", ",", "37.5575318812475"}],
>                "}"}], ",",
>              RowBox[{"{",
>                RowBox[{
>                "40.498880046256836", ",", 
> "40.59888004625684"}], "}"}],
>               ",",
>              RowBox[{"{",
>                RowBox[{
>                "42.474827869621585", ",", "42.574827869621586"}],
>                "}"}], ",",
>              RowBox[{"{",
>                RowBox[{"44.3179122203761", ",", "44.4179122203761"}],
>                "}"}], ",",
>              RowBox[{"{",
>                RowBox[{"44.39485423325631", ",", 
> "44.49485423325631"}],
>                 "}"}], ",",
>              RowBox[{"{",
>                RowBox[{
>                "47.25615015895674", ",", 
> "47.356150158956744"}], "}"}],
>               ",",
>              RowBox[{"{",
>                RowBox[{
>                "47.449131960092615", ",", "47.549131960092616"}],
>                "}"}], ",",
>              RowBox[{"{",
>                RowBox[{"49.45600875724248", ",", 
> "49.55600875724248"}],
>                 "}"}], ",",
>              RowBox[{"{",
>                RowBox[{
>                "49.60497888777778", ",", 
> "49.704978887777784"}], "}"}],
>               ",",
>              RowBox[{"{",
>                RowBox[{"55.36445877465127", ",", 
> "55.46445877465127"}],
>                 "}"}], ",",
>              RowBox[{"{",
>                RowBox[{
>                "56.39947939964122", ",", 
> "56.499479399641224"}], "}"}],
>               ",",
>              RowBox[> {"{",
>                RowBox[{"56.90643725229687", ",", 
> "57.00643725229687"}],
>                 "}"}], ",",
>              RowBox[{"{",
>                RowBox[{"59.75193443619297", ",", 
> "59.85193443619297"}],
>                 "}"}]}], "}"}]}], ";"}], "\[IndentingNewLine]",
>      RowBox[{
>        RowBox[{"lines1", " ", "=", "  ",
>          RowBox[{
>            RowBox[{
>              RowBox[{"Line", "[",
>                RowBox[{"{",
>                  RowBox[{
>                    RowBox[{"{",
>                      RowBox[{
>                        RowBox[{"#", "[",
>                          RowBox[{"[", "1", "]"}], "]"}], ",", "0"}],
>                      "}"}], ",",
>                    RowBox[{"{",
>                      RowBox[{
>                        RowBox[{"#", "[",
>                          RowBox[{"[", "2", "]"}], "]"}], ",", "0"}],
>                      "}"}]}], "}"}], "]"}], "&"}], " ", "/@", " ",
>            "list1"}]}], ";"}], "\n",
>      RowBox[{
>        RowBox[{"lines2", " ", "=", "  ",
>          RowBox[{
>            RowBox[{
>              RowBox[{"Line", "[",
>                RowBox[{"{",
>                  RowBox[{
>                    RowBox[{"{",
>                      RowBox[{
>                        RowBox[{"#", "[",
>                          RowBox[{"[", "1", "]"}], "]"}], ",", "0.1"}],
>                      "}"}], ",",
>                    RowBox[{"{",
>                      RowBox[{
>                        RowBox[{"#", "[",
>                          RowBox[{"[", "2", "]"}], "]"}], ",", "0.1"}],
>                      "}"}]}], "}"}], "]"}], "&"}], " ", "/@", " ",
>            "list2"}]}], ";"}], "\n",
>      RowBox[{
>        RowBox[{"Show", "[",
>          RowBox[{
>            RowBox[{"Graphics", "[",
>              RowBox[{"{",
>                RowBox[{
>                  RowBox[{"Thickness", "[", "0.01", "]"}], ",", " ",
>                  "Blue", ",", " ", "lines1", ",", " ", "Red", 
> ",", " ",
>                   "lines2"}], "}"}], " ", "]"}], ",", " ",
>            RowBox[{"AspectRatio", "\[Rule]", " ",
>              RowBox[{"1", "/", "100"}]}]}], "]"}], ";"}]}], "Input",
>    GeneratedCell->False,
>    CellAutoOverwrite->False]
> 
> 
>  Robert Prince-Wright
>  Risk Management Engineer, EP Americas
>  Shell Exploration & Production Company
>  Woodcreek, 200 North Dairy Ashford
>  Houston, TX 77079, USA
> 
>  Tel: +1 281 544 3016
>  Fax: +1 281 544 2238
>  Shell MeetMe Tel. +1 713 423 0600, Participant Code 62709127
>  Email: robert.prince-wright at shell.com
>  Internet: http://www.shell.com
> 
> 



  • Prev by Date: Re: Fastest method for comparing overlapping times in random time series
  • Next by Date: Re: Fastest method for comparing overlapping times in random time series
  • Previous by thread: Re: Fastest method for comparing overlapping times in random time series
  • Next by thread: Re: Fastest method for comparing overlapping times in random time series