MathGroup Archive 1998

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

Search the Archive

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
> 



  • Prev by Date: Re: Absolute coordinates in Mathematica
  • Next by Date: Multiplication or separate expressions when evaluating lines in a cell?
  • Previous by thread: Re: Efficient way to merge lists--Programming help
  • Next by thread: Re: Re: Efficient way to merge lists--Programming help