Re: Re: Efficient way to merge lists--Programming help
- To: mathgroup at smc.vnet.net
- Subject: [mg12740] Re: [mg12730] Re: [mg12708] Efficient way to merge lists--Programming help
- From: Carl Woll <carlw at fermi.phys.washington.edu>
- Date: Fri, 5 Jun 1998 02:04:19 -0400
- Sender: owner-wri-mathgroup at 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
]
Carl Woll
Dept of Physics
U of Washington
On Thu, 4 Jun 1998, Daniel Lichtblau wrote:
> Joel Cannon wrote:
> >
> > Cam someone suggest better ways to accomplish the following?
> >
> > I have two lists containing triplets--test is a rectangular array of
> > triplets {x,y,z} (e.g. Dimensions {4,40,3}) and test2 is an array of
> > triplets (e.g. Dimensions {50,3}). test2 is to replace equivalent
> > elements in test (when the x and y values are equal--the test2 z values
> > have been calculated more accurately).
> >
> > The task can be understood to be:
> >
> > 1. Given a triplet {x_i,y_i,z_i} from test2, find the position in test
> > which has the same {x_i,y_i,_}.
> >
> > 2. Replace the element in test by the triplet from test2.
> >
> > I resorted to a loop after I decided that it would take me too much time
> > to figure out a better, more elegant solution. Here is what I did:
> >
> > For[i=1,i<=Length[test2],i++,
> > test = ReplacePart[test,test2[[i]],
> > test//Position[#,{test2[[i]][[1]],test2[[i]][[2]],_}]& //Flatten]];
> >
> > Thanks for any help.
> >
> > ------------------------------------------------------------------------------
> > Joel W. Cannon | (318)869-5160 Dept. of
> > Physics | (318)869-5026 FAX Centenary College of
> > Louisiana | P. O. Box 41188 |
> > Shreveport, LA 71134-1188 |
> >
>
>
> One way is just to use simple replacement rules. I'll create some
> triples, use Union to discard those that replicate {x,y} coordinates.
> I'll also create a matrix of data.
>
> triples = Table[
> {Random[Integer,10],Random[Integer,10],Random[Real,86]}, {50}];
> triples = Union[triples, SameTest->(Drop[#1,-1]===Drop[#2,-1]&)] data =
> Table[
> {Random[Integer,10],Random[Integer,10],Random[Real,99]},
> {4}, {40}];
>
> Now we create a list of rules and do the relacement.
>
> Clear[rules1];
> rules1 = triples /. {x_,y_,z_} -> ({x,y,_}->{x,y,z}); data2 = data /.
> rules1;
>
> For larger sets this is not necessarily efficient because it relies on
> alot of pattern matching. You could instead set up a loop to hash the
> replacement triples, then loop over the data doing the replacements.
> These "loops" are perhaps best achieved using Table (but see what other
> respondents have to say). I use Module to encapsulate all local
> variables except rule (the "head" for our hash table entries). So this
> variable needs to be cleared before use. If you don't believe that, try
> debugging this without clearing it. The In/Out numbers below give some
> measure of how long it took me to catch on.
>
> Clear[rule];
> Module[{x,y,z},
> Table[{x,y,z}=triples[[j]]; rule[x,y] = z,
> {j,Length[triples]}]];
>
> repair[data_] := Module[{x,y,z,z2},
> Table[
> {x,y,z} = data[[j,k]];
> If [NumberQ[z2 = rule[x,y]], {x,y,z2}, {x,y,z}],
> {j,Length[data]}, {k,Length[data[[1]]]}]
> ]
>
> data3 = repair[data];
>
> In[90]:= data2===data3
> Out[90]= True
>
>
> To compare speed I'll try this on a larger example.
>
> newdata = Table[
> {Random[Integer,10],Random[Integer,10],Random[Real,99]},
> {40}, {4000}];
>
> In[17]:= Timing[newdata2 = newdata /. rules1;] Out[17]= {51.41 Second,
> Null}
>
> In[18]:= Timing[newdata3 = repair[newdata];] Out[18]= {17.02 Second,
> Null}
>
> In[19]:= newdata3===newdata2
> Out[19]= True
>
> Alternatively we can map a pure function over the data. This is a hair
> faster still.
>
> In[30]:= Timing[newdata4 = Map[
> If [NumberQ[z=rule[#[[1]],#[[2]]]], {#[[1]],#[[2]],z}, #]&,
> newdata, 2];]
> Out[30]= {16.23 Second, Null}
>
> In[31]:= newdata4 === newdata3
> Out[31]= True
>
>
> Now that I've turned this into a comparative timing test I expect you'll
> get some responses that are measurably faster still.
>
>
> Daniel Lichtblau
> Wolfram Research
>