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

**Re: reading files**

**Help: What is \Muserfunction generated with Splice?**

**Re: Re: Efficient way to merge lists--Programming help**

**Problems with mathlink (and TWJ_ExtendGraphics) (fwd)**