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: [mg64964] 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:14:56 -0500 (EST)
  • Organization: Goteborg University
  • Reply-to: <ingolf.dahl at telia.com>
  • Sender: owner-wri-mathgroup at wolfram.com

Hi Robert,
The fastest I can obtain is also using the Do command, but it seems to scale
quite good for large lists. First create two reasonable long lists:

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

To avoid building and rewriting of large lists in the memory, I write the
result to a file instead:

Timing[ resultfile= OpenWrite["C:\\Documents and Settings\\Your Name\\My
Documents\\Math\\PW.txt"]; 
WriteString[ resultfile,"overlaplist = {"]; 
list4= 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}]}]]; 
on1=False; on2=False; start=0; 
Do[ Switch[ list4[ [ i,2]],
1, on1=True; If[ on2, start= list4[[ i,1]]],
2, on1=False; If[ on2, WriteString[resultfile, {start, list4[[
i,1]]},",\n"]],
3, on2=True; If[ on1, start= list4[[ i,1]]],
4, on2=False; If[ on1, WriteString[resultfile, {start, list4[[
i,1]]},",\n"]]], { i, Length[list4]}];
WriteString[resultfile,"Sequence[]};"]; 
Close[resultfile]]

This take around 32 seconds on my computer, and seems to scale linearly. You
can then simply read in the result by 

<< "C:\\Documents and Settings\\Your Name\\My Documents\\Math\\PW.txt"

Best regards

Ingolf Dahl
Sweden


-----Original Message-----
From: Prince-Wright, Robert G SEPCO [mailto:robert.prince-wright at shell.com] 
To: mathgroup at smc.vnet.net
Subject: [mg64964] [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: General--Making the DisplayFormula style in ArticleModern look like Traditional
  • 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