Re: Re: Efficient way to merge lists--Programming help
- To: mathgroup at smc.vnet.net
- Subject: [mg12872] Re: Re: Efficient way to merge lists--Programming help
- From: "Allan Hayes" <hay at haystack.demon.cc.uk>
- Date: Wed, 17 Jun 1998 00:28:14 -0400
- References: <6ll172$elg$1@dragonfly.wolfram.com> <6lqolf$o3r@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
I have been unsuccesfully trying to email the following to Carl Woll and
Daniel Lichtblau for over a week now - it just disappears and later
pops up again in my out tray.
As Carl's code contains a generally useful observation about hashing and
my rule based version uncovered a find example of using Dispatch to
speed up replacement, I have taken the libery of posting the email that
Carl's sent to me (below *********) and my reply:
Carl,
Thank you for sorting this out and for the very useful observation about
hashing.
This prompted me to look at the corresponding replacement rule code and
to use Dispatch. Here are the results (I have include two fairly
general techniques for limiting replacement to where I want it to take
place).
repair[1][rough_, fine_] := (*your code*) Module[{f,g,h},
f[{x_,y_,z_}] := g[x,y] = z;
f /@ fine;
a_g := Sequence[];
h := {#1,#2,First[{g[#1,#2],#3}]}&;
Apply[h,rough,{1}]
]
repair[2][rough_,fine_]:=
Module[{k,r,R ,F},
R=k@@rough;F = k@@fine;
r=Dispatch[List@@(F/.{x___,z_}:>({x}:>z))];
List@@(R/.{x___,z_}:>{x,{x}/.r/._List->z}) ]
repair[3][rough_,fine_]:=
Module[{r,k,R,F},
{R ,F}= Apply[k,{rough,fine},{2}];
r=Dispatch[F/.k[x___,z_]:> ({x}:>z)];
R/. k[x___,z_]:>{x, {x}/.r/._List:>z} ]
I used your tests
Do[
R[n]= Flatten[Table[{i,j,Random[Real,89]},{i,n},{j,n}],1];
F[n]= Flatten[Table[{i,j,Random[Real,99]},{i,20},{j,20}],1],
{n,2,20,2}
];
With the results
TableForm[
Table[
( Do[repair[i][R[n],F[n]],{10}];//Timing//First)/Second,
{n,2,20,2},
{i,1,3}
],
TableHeadings->{Table[n,{n,2,20,2}], Table[repair[i],{i,1,3}]} ]
repair[1] repair[2] repair[3] 2 1.16 0.33 0.33
4 1.15 0.33 0.33
6 1.54 0.33 0.38
8 1.26 0.33 0.44
10 1.27 0.44 0.43
12 1.27 0.49 0.55
14 1.26 0.55 0.61
16 1.32 0.66 0.65
18 1.38 0.71 0.77
20 1.43 0.82 0.88
Thanks again,
Allan
**********************************************************************
-----Original Message-----
From: Carl Woll <carlw at fermi.phys.washington.edu> To:
mathgroup at smc.vnet.net
Subject: [mg12872] Re: Re: Efficient way to merge lists--Programming help
>Hi Alan,
>
>I think we are trying to solve slightly different problems. The problem I
>tried to solve was as follows:
>
>Given
>1) A matrix of triples {x,y,z} (called rough) not necessarily
>consisting of unique entries {x,y,_}. For example
>
>{ { {1,2,.3}, {1,2,.4} },
> { {2,3,.4}, {3,4,.5} } }
>
>This is why my Apply statement had {2}, and not {1}.
>
>2) An array of triples (called fine), which are distinct, and where
>{x,y,_} is not necessarily contained in rough.
>
>I think the problem you tried to solve was different in the following
>respects.
>
>a) Your rough was an array of triples, not a matrix.
>b) The triples in your rough array were all distinct, that is you didn't
>have more than one element that matched {x,y,_}.
>c) Your fine array was a subset of rough. That is, if {x,y,_} was a member
>of fine, than it was also a member of rough.
>
>At any rate, you didn't see my final version.
>
>repair1[rough_, fine_] := Module[{f,g,h},
> f[{x_,y_,z_}] := g[x,y] = z;
> f /@ fine;
> a_g := Sequence[];
> h := {#1,#2,First[{g[#1,#2],#3}]}&;
> Apply[h,rough,{1}]]
>
>I compared the two on the following test case.
>
>fine = Flatten[Table[{i,j,Random[Real,89]},{i,n},{j,n}],1];
>rough= Flatten[Table[{i,j,Random[Real,99]},{i,20},{j,20}],1];
>
>When n < 7, your function is faster, and when n > 6, my function is
>faster.
>
>The key to the speed improvement when compared to my previous attempt is
>that definitions like
>
>g[x,y]=z
>
>can be retrieved using hashing methods, which is not true for definitions
>like
>
>g[x,y,_]:={x,y,z}
>
>It's an amusing toy problem, isn't it?
>
>Carl Woll
>Dept of Physics
>U of Washington
>
>On Wed, 10 Jun 1998, Allan Hayes wrote:
>
>>
>> Carl Woll wrote in message <6ll172$elg$1 at dragonfly.wolfram.com>...
>> >Hi Daniel,
>> >
>> >As you said, we can now compare timings of different solutions. I gave a
>> >slightly different solution than yours, and it had an error. Also,
>> >after comparing my fixed solution with yours, I realized how to speed
>> >it up slightly. My tests show that the following solution is slightly
>> >faster than yours.
>> >
>> >repair[rough_, fine_] := Module[{f,g,result},
>> > f[{a_,b_,c_}] := g[a,b,_] = {a,b,c};
>> > f /@ fine;
>> > result = Apply[g, rough, {2}];
>> > g = List;
>> > result
>> >]
>> > ...................[cut] ...........
>>
>> Carl,
>> It looks as if you need {1}instead of {2} in line 4.
>> g still has to do a lot of searching.
>> The following variant is about twice as quick on my tests (its important
to
>> limit the search by Position)
>>
>> repair2[rough_, fine_] :=
>> Module[{f, r=rough},
>> f[s:{a___,_}] :=
>> r[[First[Position[r,{a,_},{1},1,Heads->False]]]] = s;
>> f /@ fine;
>> r
>> ]
>>
>> Other variants, like using positions in both lists don't seem to be of
much
>> benefit.
>>
>> Allan
>> -------------------------------------------------------------
>> Allan Hayes
>> Training and Consulting
>> Leicester UK
>> http://www.haystack.demon.co.uk
>> hay at haystack.demon.co.uk
>> voice: +44 (0)116 271 4198
>> fax: +44(0)116 271 8642
>>
>>
>>
>
>