Re: recode procedural algorithm to faster functional module

*To*: mathgroup at smc.vnet.net*Subject*: [mg44108] Re: recode procedural algorithm to faster functional module*From*: "Carl K. Woll" <carlw at u.washington.edu>*Date*: Thu, 23 Oct 2003 07:14:52 -0400 (EDT)*Organization*: University of Washington*References*: <bmqqcl$rjv$1@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

Robert, If we can assume that the bricks in a particular list do not overlap, then there is no need to check every brick in V1 with every brick in V2 as you do in your code, and I believe as everyone else in this thread does with their code. A much faster approach is then the following: pc2[v1_List, v2_List] := Module[{min = Min[v1, v2] - 1, max = Max[v1, v2] + 1}, v1f = Interpolation[ Transpose[{Flatten[{min, v1, max}], Flatten[Table[{1, 0}, {Length[v1] + 1}]]}], InterpolationOrder -> 0]; v2f = Interpolation[ Transpose[{-Flatten[{min, v2, max}], Flatten[Table[{0, 1}, {Length[v2] + 1}]]}], InterpolationOrder -> 0]; Round[Plus @@ v1f[v2[[All, 1]]] + Plus @@ v2f[-v1[[All, 1]]]]] The basic idea is that the Interpolating functions carry the information about where each brick in a particular list is, and we can use this function to find out which of the bricks in the other list overlap these bricks. The one tricky part is that the zeroth order interpolation treats the intervals as (a,b], so we have to be creative to come up with an interpolating function which treats the intervals as [a,b). For example, v1 = Table[{i - Random[]/3, i + Random[]/3}, {i, 1, 100}]; v2 = Table[{i - Random[]/3, i + Random[]/3}, {i, 1/2, 1000 + 1/2}]; yields lists where the bricks in the list do not overlap. With pc1 being your original function, we find: In[36]:= Timing[pc1[v1, v2]] Timing[pc2[v1, v2]] Out[36]= {2.312 Second, 26} Out[37]= {0.032 Second, 26} The function pc2 is almost two orders of magnitude faster in this example, so it ought to be faster than other proposed alternatives. If the bricks in a single list do overlap, then the interpolating function approach can still work, it would just require a slight modification (the interpolating function will have to return the number of bricks at any point). I also considered using the Interval function which I think was comparable in speed to the above approach, but the Interval function approach can not be modified to handle overlapping bricks in a single list. Carl Woll "Prince-Wright, Robert G SEPCO" <robert.prince-wright at shell.com> wrote in message news:bmqqcl$rjv$1 at smc.vnet.net... > > Can someone please help me recode this Module so it is less procedural > and hopefully runs a lot faster. The Lists V1 and V2 represent two time > series with 'bricks' laid out along them. The Bricks have varying length > set by v[[i]][[1]] and v[[i]][[2]] and the idea is to count the number > of times there is an overlap. I can only see the dumb procedural way of > taking each brick and checking if it overlaps in time with another! > > > > Concurrence[v1_List, v2_List,nsim_]:=Module [ > > {k=1,c=0}, > Do[ > Do[ > Which[ > v1[[i]][[1]] == v2[[k]][[1]], c=c+1, > v1[[i]][[1]] < v2[[k]][[1]] && v1[[i]][[2]] > v2[[k]][[1]], c=c+1, > v1[[i]][[1]] > v2[[k]][[1]] && v1[[i]][[1]] < v2[[k]][[2]], c=c+1 > ]; > (*Write[ strm1, {v1[[i]][[1]],v2[[i]][[1]],c}];*) > , {i,1,nsim} > ], {k,1,nsim} > ]; > c > ] > > I've have a PowerPoint illustration if this is unclear and can e-mail it. > > thanks > Robert Prince-Wright >