Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

A common thing to want to do with data is to combine it (at least I thought this was a common thing). In SQL there is the idea of table joins "select id,v1,v2 from A,B where A.id=B.id" kind of thing. I'm trying to do a join like this using Mathematica, i.e. retrieve table A from the Internet, retrieve table B from the Internet, combine, do stuff with the resulting joined columns.

My First effort was this:

(* Simulate tables *)
a = Table[{x, RandomReal[]}, {x, 1, 1000}];
b = Table[{x, RandomReal[]}, {x, 1, 1000}];
(* Use this simple match function for now *)
RMatch[x_] := x[[1]] == x[[3]];
Length[Part[
   Select[Flatten[Outer[Function[{x, y}, Join[x, y]], a, b, 1], 1], 
    RMatch], All, {1, 2, 4}]] // Timing
{1.906250, 1000}

This works, but is way too slow. Imagine if it was 100,000 rows each; the program may never finish. Also this will take up a lot of memory; creating a temporary list of rows that is NxM in size.

So I tried an iterative approach instead:

(* Simulate tables *)
a = Table[{x, RandomReal[]}, {x, 1, 1000}];
b = Table[{x, RandomReal[]}, {x, 1, 1000}];
(* Use this simple match function for now *)
RMatch[x_, y_] := x[[1]] == y[[1]];
RJoin[a_, b_, match_] := Block[
  {lena = Length[a], lenb = Length[b], arow, brow, i, j},
  Flatten[Reap[
     For[i = 1, i <= lena, ++i,
      arow = a[[i]];
      For[j = 1, j <= lenb, ++j,
       brow = b[[j]];
       If[match[arow, brow], Sow[Join[arow, brow]]
        ]
       ]
      ]
     ][[2]], 1
   ]
  ]
Length[Select[RJoin[a, b, RMatch], 
   Function[{x}, x[[1]] == x[[3]]]]] // Timing
{2.562500, 1000}

This will use much less memory, but is even slower.

Is this something that just isn't appropriate for Mathematica i.e. do this using a different tool, output the table and work with that instead? That would be a shame, but it seems that it may be necessary.

Update:

Thanks to the great answers below I decided to give up on the general case and focus on unique ID matching, which is the situation that arises the most. Following Verbeia and Michael E2's examples I came up with a version that is fast and readable.

(* Simulate tables *)
a = Table[{x, RandomReal[]}, {x, 1, 1000000, 2}];
b = Table[{x, RandomReal[]}, {x, 1, 1000000, 3}];

RJoin[a_, b_] := Block[{f},
  Do[
    f[x[[1]]] = x[[2]],
    {x, a}
    ];
   Cases[b /. {x_, y_} -> {x, y, f[x]}, {_, _, _Real}]
  ]

(* Use and time *)
Length[RJoin[a, b]] // Timing
{1.750000, 166667}

That's 1.75 seconds to join two tables with almost a million rows total. This is mildly faster than Michael E's version which took 4.2 seconds on my computer.

When I need a more general case I plan to use Java to process the data, but this should handle most of my cases.

Update 2

I managed to simplify and speed up the arbitrary matching case a little bit

(*Simulate tables*)
a = Table[{x, RandomReal[]}, {x, 1, 1000, 1}];
b = Table[{x, RandomReal[]}, {x, 1, 1000, 1}];

(*Use this simple match function for now*)
RMatch[x_, y_] := x[[1]] == y[[1]];

RJoin[a_, b_, match_] :=
 Flatten[
  Reap[Do[
      If[match[x, y],
       Sow[{x[[1]], x[[2]], y[[2]]}];
       ],
      {x, a}, {y, b}
      ];
    ][[2]]
  , 1]
Length[RJoin[a, b, RMatch]] // Timing
{1.359375, 1000}
share|improve this question
    
This isn't a duplicate of this? –  Murta Sep 10 '13 at 1:56
    
I think the difference is that this one (I think) assumes unique keys. At least that's what I understand a SQL table id to be. –  Verbeia Sep 10 '13 at 2:00
    
I'm not assuming unique keys. I'm not assuming 'keys' at all. I'm want to be able to apply an arbitrary condition. My example is just that - an example. Imagine a condition like measuring distance between two points and selecting those below a certain limit. That kind of arbitrary and flexible thing. This is no big deal for relational databases for hundreds of thousands of rows. –  Ian Schumacher Sep 10 '13 at 2:19
    
Murta - I think that question and answer can be applied to my situation. Hopefully you can forgive me for not seeing "Vlookup function as Excel in Mathematica" as being the same as my question. I would never think to search for such a thing. –  Ian Schumacher Sep 10 '13 at 2:37
    
Well, the question was written in terms of things with matching id's, so please forgive me that it was not clear to me that you had something more general in mind. But different criteria would suggest a different approach, including your Outer one. –  Verbeia Sep 10 '13 at 2:50
show 5 more comments

5 Answers 5

up vote 9 down vote accepted

This one is fairly fast. I used GatherBy to collect like data rows and kept the ones that matched another. (I assumed that the id entries of a and b are unique in each table.) The appropriate entries are then extracted.

On 10000/5000 entries:

a = Table[{x, RandomReal[]}, {x, 1, 10000}];
b = Table[{x, RandomReal[]}, {x, 1, 10000, 2}];
Flatten[Cases[GatherBy[a~Join~b, First], {_, _}], {{1}, {2, 3}}][[All, {1, 2, 4}]] //
  Timing // First
(* 0.014554 *)

On 100,000/50,000 entries (roughly linear growth):

a = Table[{x, RandomReal[]}, {x, 1, 100000}];
b = Table[{x, RandomReal[]}, {x, 1, 100000, 2}];
Flatten[Cases[GatherBy[a~Join~b, First], {_, _}], {{1}, {2, 3}}][[All, {1, 2, 4}]] //
  Timing // First
(* 0.175955 *)

The output on a small data set looks like this:

a = Table[{x, RandomReal[]}, {x, 1, 10}];
b = Table[{x, RandomReal[]}, {x, 1, 10, 2}];
Flatten[Cases[GatherBy[a~Join~b, First], {_, _}], {{1}, {2, 3}}][[All, {1, 2, 4}]]
(* {{1, 0.74066, 0.69329}, {3, 0.80351, 0.420397}, {5, 0.239924, 0.806693},
    {7, 0.665209, 0.0483077}, {9, 0.705487, 0.737412}} *)

By comparison Verbeia's version is roughly of quadratic growth and rather slower:

a = Table[{x, RandomReal[]}, {x, 1, 1000}];
b = Table[{x, RandomReal[]}, {x, 1, 1000, 2}];
(Join[{##}, Cases[b, {#1, _}][[All, 2]]] & @@@ a) /. {_, _} -> Sequence[] //
  Timing // First
(* 0.065370 *)

a = Table[{x, RandomReal[]}, {x, 1, 10000}];
b = Table[{x, RandomReal[]}, {x, 1, 10000, 2}];
(Join[{##}, Cases[b, {#1, _}][[All, 2]]] & @@@ a) /. {_, _} -> Sequence[] //
  Timing // First
(* 5.736539 *)

Update

Below I present two faster functions, based on a similar idea: if the data Join[a, b] were sorted on the IDs, rows to be joined would end up next to each other. I used Ordering and Differences to determine the rows with the same ID. When sorted, a difference in IDs of zero indicates two rows to be joined. SparseArray and ArrayReshape seem fairly fast here, but they're not compilable. For the compiled version, Position and Partition were used instead. On packed arrays, both have comparable speeds.

I avoid sorting the whole database, since moving all that memory around will take time.

I'm assuming that the IDs are numeric. Indeed, to get the speed below, the data have to be numeric. The speed is dependent on using packed arrays. The compiled function assumes the IDs can be represented by Real numbers.

mJoin2[a_, b_] := 
  With[{data = a ~Join~ b,
        ids = a[[All, 1]] ~Join~ b[[All, 1]],
        ncols = Last @ Dimensions @ a},
   With[{ordering = Ordering[ids]}, 
    With[{adj = SparseArray[1 - Unitize @ Differences @ ids[[ordering]]]["AdjacencyLists"]},
     ArrayReshape[
        data[[ ordering[[Flatten @ Transpose @ {#, # + 1} &@ adj]] ]],
        {Length @ adj, 4}
      ][[All, Join[Range@ncols, Range[2 + ncols, 2 ncols]]]]
     ]]];

mJoin3 = Compile[{{a, _Real, 2}, {b, _Real, 2}},
   Module[{data, ids, ordering, joinID, ncols},
    data = a ~Join~ b;
    ids = a[[All, 1]] ~Join~ b[[All, 1]];
    ncols = Last @ Dimensions @ a;
    ordering = Ordering[ids];
    joinID = Flatten @ Position[Unitize @ Differences @ ids[[ordering]], 0];
    Partition[
      Flatten[
       data[[
         Flatten @ Transpose @ {ordering[[joinID]], ordering[[1 + joinID]]}
         ]]],
      2 ncols
      ][[All, Join[Range @ ncols, Range[2 + ncols, 2 ncols]]]]
    ]
   ];

Comparison

$HistoryLength = 0;

a = Table[{N@x, RandomReal[]}, {x, 1, 2000000, 3}];
b = Table[{N@x, RandomReal[]}, {x, 1, 2000000, 2}];

(m3 = mJoin3[a, b]) // Length // Timing     (* Michael E2 compiled *)
(m2 = mJoin2[a, b]) // Length // Timing     (* Michael E2 SparseArray method *)
(m1 = Flatten[                              (* Michael E2 original *)
       Cases[GatherBy[a~Join~b, First], {_, _}], {{1}, {2, 3}}][[All, {1, 2, 4}]]) //
         Length // Timing
(i2 = RJoin[b, a]) // Length // Timing      (* Ian S. -- first update *)

{0.177294, 333334}
{0.210489, 333334}
{2.890227, 333334}
{5.517205, 333334}

m1 == m2 == m3 == i2
(* True *)

On non-packed arrays mJoin2 slows down. The compiled function mJoin3 converts the Integer indices to Real and packs the arrays when it is called, which causes a slight slowdown.

a = Table[{x, RandomReal[]}, {x, 1, 2000000, 3}];
b = Table[{x, RandomReal[]}, {x, 1, 2000000, 2}];

(m3 = mJoin3[a, b]) // Length // Timing
(m2 = mJoin2[a, b]) // Length // Timing

{0.220412, 333334}
{0.580442, 333334}

Note: My original solution can be a bit of a memory hog. I believe it was slower in Ian Schumacher's test because it filled the RAM and led to some swapping.

share|improve this answer
    
Oh even better! And much better complexity growth behavior as well, which I neglected to investigate for Verbeia's answer. –  Ian Schumacher Sep 10 '13 at 4:41
    
Clever. Good approach. Gives me more ideas. –  Ian Schumacher Sep 11 '13 at 23:31
    
Really nice use of Ordering here. I wonder if there is an efficient way to apply it to your own question. Although it makes little overall difference Flatten[{adj, adj + 1}, {2, 1}] is faster than Flatten @ Transpose @ {#, # + 1} &@ adj BTW. –  Mr.Wizard Sep 16 '13 at 20:00
add comment

I might have misunderstood what it is you are trying to do, but I would have thought that Cases would be a better option, and that looping approach was not ideal.

Here is a one-liner that seems to do what I think you want. Firstly, if you are looking for an index that is in both lists, then you only need to iterate over one list and find the indices that are also present in the other list.

Here is a better test dataset, since not all of the indices in a are in b.

a = Table[{x, RandomReal[]}, {x, 1, 1000}]; 
b = Table[{x, RandomReal[]}, {x, 1, 1000, 2}];

And here is my function:

(Join[{##}, Cases[b, {#1, _}][[All, 2]]] & @@@ a) /. 
  {_, _} ->   Sequence[]

This goes through each element of a and selects all the elements of b that have the same index (first part), and keeps only the second part, which is the value. That's what the Part specification [[All,2]] is doing. I Join that with the corresponding actual a element, and then delete, using a replacement rule, the ones that are only two elements long, since that means that no element of b actually matched.

I tested it on the long dataset above and got the following output:

{{1, 0.177197, 0.569452}, {3, 0.980658, 0.544697}, {5, 0.507622, 
  0.634173}, {7, 0.645986, 0.820293}, {9, 0.215669, 0.803831}, {11, 
  0.460078, 0.293823}, {13, 0.520429, 0.813139}, {15, 0.679199, 
  0.48138}...

It took about 0.1 seconds on my three-year-old PC.

share|improve this answer
    
This looks interesting for cases where I want to join on an ID. I'll look at it more. I would also like to handle arbitrary join conditions, but joining on an ID is very common and useful of course. I'll keep it in the toolkit for those cases for sure. Thanks. –  Ian Schumacher Sep 10 '13 at 2:25
add comment

Using the function SelectEquivalents defined here

a = Table[{x, RandomReal[]}, {x, 1, 10000}];
b = Table[{x, RandomReal[]}, {x, 1, 10000, 2}];

SelectEquivalents[{a,b},
    MapLevel->2,
    TagElement->First,
    TransformElement->(#[[2]]&),
    TransformResults->(Join[{#1},#2]&),
    FinalFunction->(Select[#,Length@#>2&]&)
]//Timing//First

 (*0.11*)

This can have the advantage to be reusable and adaptable to a variety of cases (once you understand the SelectEquivalents function, use Print for this), as the different important operations are separate.

share|improve this answer
    
Interesting. Worth studying. I tried it with a million data points (using //Length //Timing and offsets of 2 and 3 to have a fair comparison with my results). It took 38 seconds on my machine. Quite usable, but not the current performance winner. –  Ian Schumacher Sep 10 '13 at 18:19
add comment

Using and Sow and Reap:

Flatten[Reap[Join[Map[Sow @@ Reverse[#] &, {a, b}, {2}]], Intersection[b[[All, 1]],a[[All,1]]],
    Join[{#1}, #2] &][[2]], 1]

Uses the first column as tags and elements with common tags are "reaped". Try Verbeia's test data.

share|improve this answer
    
Nice, but there seems to be an error. Try a = Table[{x, RandomReal[]}, {x, 1, 100, 2}]; b = Table[{x, RandomReal[]}, {x, 1, 100, 3}]; for example. –  Ian Schumacher Sep 10 '13 at 14:42
    
@IanSchumacher thank you. I have corrected the code to deal with this, i.e intersection (common) identifiers –  ubpdqn Sep 11 '13 at 2:25
add comment

As commented by @IanSchumacher this solution is more appropriate for a left. Using vLookup3 from here we have:

a = Table[{x, RandomReal[]}, {x, 1, 10000}];
b = Table[{x, RandomReal[]}, {x, 1, 10000, 2}];
vLookup3[a, b] // AbsoluteTiming // First

0.041213

for a inner join you can do:

DeleteCases[vLookup3[a, b],{__,Null}]
share|improve this answer
    
This give many nulls (i.e. it appears to be a left outer join rather than the desired inner join). I ran this with x,1,1000000,2 and x,1,1000000,3 and measuring the time and length I got {2.015625, 500000}, which is what I would expect for a left outer join that results in nulls. It's very fast, but still slightly slower than the solution I posted that does an inner join. Maybe you can alter it to have it do an inner join? –  Ian Schumacher Sep 11 '13 at 3:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.