Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Re: recode procedural algorithm to faster functional module

• To: mathgroup at smc.vnet.net
• Subject: [mg44059] Re: [mg44034] recode procedural algorithm to faster functional module
• From: "Peter Pein" <nospam at spam.no>
• Date: Sun, 19 Oct 2003 01:11:20 -0400 (EDT)
• References: <200310180712.DAA28079@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

Hi Robert,
I renamed your function procConcurrence and tried the following:

In[1]:=
procConcurrence[v1_List, v2_List] := Module[{c = 0}, 
   Do[Do[Which[
   v1[[i]][[1]] == v2[[k]][[1]], c++,
   v1[[i]][[1]] < v2[[k]][[1]] && v1[[i]][[2]] > v2[[k]][[1]], c++,
   v1[[i]][[1]] > v2[[k]][[1]] && v1[[i]][[1]] < v2[[k]][[2]], c++],
   {i, Length[v1], 1, -1}], {k, Length[v2], 1, -1}]; c]

In[2]:=
(* This function replaces every element of v1 by a boolean list,
   which indicates whether the el. of v1 overlaps corresponding
   elements of v2. Then all the 'True's are counted.
*)
Concurrence[v1_List, v2_List] := Count[
    v1 /. {a_?AtomQ, b_} ->
        (v2 /. {c_?AtomQ, d_} -> (a <= c < b || c < a < d)), 
    True, 2]

In[3]:=
(*Test *)
#[{{1, 2}, {4, 5},     {7, 8},     {9.2, 9.3}, {11.1, 11.2}},
   {{1, 2}, {4.1, 4.9}, {7.2, 8.2}, {9, 10},    {11.3, 11.4}}] & /@
{Concurrence, procConcurrence}

Out[4]=
{4, 4}

In[5]:=
(#1[{{1, 3.5}}, {{2, 3}, {4, 5}}] & ) /@ {Concurrence, procConcurrence}

Out[5]=
{1, 1}

In[6]:=
v1 = Table[{i - Random[], i + Random[]}, {i, 100}]; 
v2 = Table[{i - Random[], i + Random[]}, {i, 1000}]; 

In[8]:=
(Timing[#1[v1, v2]] & ) /@ {Concurrence, procConcurrence}
(Timing[#1[v2, v1]] & ) /@ {Concurrence, procConcurrence}

Out[8]=
{{3.435 Second, 202}, {21.14 Second, 202}}
Out[9]=
{{3.405 Second, 202}, {21.111 Second, 202}}

...and you're right: it _is_ faster :-))

Peter

-- 
Peter Pein, Berlin
petsie at arcAND.de
replace && by || to write to me


----- Original Message ----- 
From: "Prince-Wright, Robert G SEPCO" <robert.prince-wright at shell.com>
To: mathgroup at smc.vnet.net
Subject: [mg44059] [mg44034] recode procedural algorithm to faster functional module


> 
> 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
> 

• References:
  • recode procedural algorithm to faster functional module
    • From: "Prince-Wright, Robert G SEPCO" <robert.prince-wright@shell.com>