Re: Re: recode procedural algorithm to faster functional module
- To: mathgroup at smc.vnet.net
- Subject: [mg44064] Re: [mg44059] Re: [mg44034] recode procedural algorithm to faster functional module
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Mon, 20 Oct 2003 01:13:32 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Actually in this sort of situation a procedural algorithm will be at
least as fast if it is compiled.
Using your own codes with the only difference made by compilation,
procConcurrence now wins. at least on my machine.
procConcurrence = Compile[{{v1, _Real, 2}, {v2, _Real, 2}}
, 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]];
v1=Table[{i-Random[],i+Random[]},{i,100}];
v2=Table[{i-Random[],i+Random[]},{i,1000}];
(Timing[#1[v1, v2]] & ) /@ {Concurrence, procConcurrence}
(Timing[#1[v2, v1]] & ) /@ {Concurrence, procConcurrence}
{{2.08 Second,181},{1.79 Second,181}}
{{2. Second,181},{1.76 Second,181}}
Andrzej Kozlowski
Yokohama, Japan
http://www.mimuw.edu.pl/~akoz/
http://platon.c.u-tokyo.ac.jp/andrzej/
On Sunday, October 19, 2003, at 02:11 PM, Peter Pein wrote:
> 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
> To: mathgroup at smc.vnet.net
> Subject: [mg44064] [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
>>
>
>
>