Re: Fastest method for comparing overlapping times in random time series
- To: mathgroup at smc.vnet.net
- Subject: [mg64979] Re: [mg64935] Fastest method for comparing overlapping times in random time series
- From: ggroup at sarj.ca
- Date: Fri, 10 Mar 2006 05:15:10 -0500 (EST)
- References: <200603080559.AAA03078@smc.vnet.net>
- Reply-to: ggroup at sarj.ca
- Sender: owner-wri-mathgroup at wolfram.com
Robert,
I couldn't get your code to paste in without errors. In any case, I've
listed below my attempt that has no explicit For/Do/While loops. It
seems to be reasonably fast on short lists (on the order of 1000 time
intervals per list).
========== Begin Function ===========
compare[list1_, list2_] :=
Module[
{pos, list2pos, filtlist2pos, f, newintervals, myHead},
SetAttributes[pos, Listable];
pos[x_] := Module[{tmp},
tmp = Union[Flatten[list1], {x}];
tmp = First[Flatten[Position[tmp, x]]];
(tmp + 1)/2];
list2pos = Transpose[{pos /@ list2, list2}];
filtlist2pos =
Select[
list2pos,
#1[[1,2]] - #1[[1,1]] != 0 || #1[[1,1]] != IntegerPart[#1[[1,1]]] &
];
f[{{strt_Integer, end_}, l2int_}] :=
Module[
{l1int, lenl1int},
l1int = list1[[Range[strt, end]]];
lenl1int = Length[l1int];
If[ IntegerQ[end],
l1int,
Join[
l1int[[Range[1, lenl1int - 1]]],
{{l1int[[-1,1]], l2int[[2]]}}
]
] /. {} :> Sequence[]
];
f[{{strt_, end_}, l2int_}] :=
Module[
{l1int, lenl1int},
l1int = list1[[Range[strt - 1/2, end - 1/2]]];
lenl1int = Length[l1int];
If[ strt == end,
{l2int},
If[ !IntegerQ[end],
{
{l2int[[1]], l1int[[1,2]]},
l1int[[Range[2, lenl1int - 1]]],
{l1int[[-1,1]], l2int[[2]]}
},
{
{l2int[[1]], l1int[[1,2]]},
l1int[[Range[2, lenl1int]]]
}
] /. {} :> Sequence[]
]
];
newintervals = f /@ filtlist2pos;
Flatten[
newintervals /. {(a___)?NumericQ} :> myHead[a]
] /. myHead[a___] :> {a}
]
========== End Function ===========
Let's test it:
list1 = list2 = {};
n = 10^3;
For[i = 0, i <= n, i += Random[], AppendTo[list1, {i, i += 2*Random[]}]]
For[i = 0, i <= n, i += Random[], AppendTo[list2, {i, i += 2*Random[]}]]
Timing[compare[list1,list2];]
Out[84]=
{2.864Second, {675,649}}
Hope that helps
On Wednesday, March 8, 2006 at 12:59 AM, Prince-Wright, Robert G Sepco
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!
> 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
- References:
- Fastest method for comparing overlapping times in random time series
- From: "Prince-Wright, Robert G SEPCO" <robert.prince-wright@shell.com>
- Fastest method for comparing overlapping times in random time series