Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2003
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2003

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

Search the Archive

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


  • Prev by Date: Re: Re: Re: Running The Combinatorica GraphEditor
  • Next by Date: Re: Re: Re: Running The Combinatorica GraphEditor
  • Previous by thread: Re: recode procedural algorithm to faster functional module
  • Next by thread: Re: recode procedural algorithm to faster functional module