Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: Efficient way to merge lists--Programming help

• To: mathgroup at smc.vnet.net
• Subject: [mg12730] Re: [mg12708] Efficient way to merge lists--Programming help
• From: Daniel Lichtblau <danl>
• Date: Thu, 4 Jun 1998 02:52:15 -0400
• References: <199806030620.CAA14325@smc.vnet.net.>
• Sender: owner-wri-mathgroup at wolfram.com

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

• References:
  • Efficient way to merge lists--Programming help
    • From: Joel Cannon <cannon@alpha.centenary.edu>