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
>