Mathematica 9 is now available
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: [mg64981] Re: [mg64935] Fastest method for comparing overlapping times in random time series
  • From: "Ingolf Dahl" <ingolf.dahl at telia.com>
  • Date: Fri, 10 Mar 2006 05:15:12 -0500 (EST)
  • Sender: owner-wri-mathgroup at wolfram.com

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