Efficiently extracting an array subset given a separate array

Question

I have two arrays. The first array consists of tens of millions of rows and three columns with a string, a number, and a string.

array1 = {{string1, 145745, a}, {string2, 56546, a}, {string3, 56546, b},
          {string3, 246, b}, {string7, 12355, a}, {string7, 12355, b}}

The second array has hundreds of thousands of rows but also consists of three columns but with a string, a number, and a number.

array2 = {{string1, 145745, 3.14324}, {string3, 56546, -0.34319}, {string7, 12355, 0.23535}}

In array2, the first two elements of each row matches the first two elements of a row (or, at most, two rows) in array1. In other words, array2[[All,{1,2}]] is a subset of array1[[All,{1,2}]].

The goal is to take from array1 all the rows that have matching rows in array2 (when comparing only the first two columns from each array). For example, from the two given arrays above, the final result would be

result = {{string1, 145745, a},{string3, 56546, b},{string7, 12355, a},{string7, 12355, b}}

The fastest command I've come up with is

m=Dimensions[array2][[1]];
Do[
Pick[array1,array1[[All,{1,2}]],array2[[i,{1,2}]]]//Sow
,{i,m}
]//Reap

but this is still too slow. This is a simple problem, but I am really looking for the fastest method possible.

Any ideas?

EDIT

Previously, I erroneously had

array1 = {{string1, 145745, a}, {string2, 56546, a}, {string3, 56546, b},
          {string3, 246, b}, {string7, **145745**, a}, {string7, 12355, b}}

which should have been

array1 = {{string1, 145745, a}, {string2, 56546, a}, {string3, 56546, b},
          {string3, 246, b}, {string7, **12355**, a}, {string7, 12355, b}}

This has been corrected above.

Answer 1

Here is the realization of hashing mentioned by @whuber, and it is based on a modified and faster version of MemberPositions function discussed here. The current version is based on some code due to Norbert Pozar. Here it is:

memberPositions[x_List, y_List] :=
   Module[{tag},
      Pick[
        Range[Length[x]], 
        Replace[x, Dispatch[Thread[Rule[Intersection[x, y], tag]]], {1}], 
        tag
      ]
   ];

It finds positions in x where some elements contained in y are present. Here is a simple example:

memberPositions[{1,3,5,7,9},{3,9}]

(* {2,5} *)

Despite the experiences of @whuber with Dispatch- based code, this particular code seems to scale well. The actual solution is then (thanks to the OP for correcting my original somewhat incorrect code):

array1[[memberPositions[array1[[All, {1, 2}]], array2[[All, {1, 2}]]]]]

Taking the benchmark examples from the code of @whuber with n1=10^5, n2=2*10^4, this solution is speed - equivalent to his. To see that we get the same results, one would have to act with Flatten[#,1]& on the result of @whuber.

For the OP's original arrays I get:

(* 
   {{string1, 145745, a}, {string3, 56546, b}, 
    {string7, 12355, a}, {string7, 12355, b}}
*)

which seems to be a right answer.

I was not able to check with the larger arrays, since the code of @whuber appears to be quite memory-hungry (as he mentioned himself) and my 6GB were not enough. My guess is that the culprit is GatherBy, which seems to have quadratic memory use as a function of array's size. For his sizes of arrays, my code finished in 2.5 seconds (all this tested on V8.0, AMD Phenom II X4 2.8 GHz, 6GB RAM).

Answer 2

In many systems an efficient straightforward way to do this is to scan the sorted join of the two arrays for duplicates: with arrays of sizes $n_1$ and $n_2$, this is a $O\left((n_1+n_2)\log(n_1+n_2)\right)$ solution.

A Mathematica implementation (which is quick and dirty because for simplicity and clarity of exposition it assumes the elements of the first array will always sort before the elements of the second array) is

Rest /@ Select[GatherBy[Sort[array1~Join~array2], Most], Length[#] > 1 &]

The timing for $n_1=10^4$, $n_2=2 \times 10^3$ is $0.05$ seconds. Scaling this up to $n_1=10^6$, $n_2=2\times 10^5$ costs around $6$ to $9$ seconds (the absolute timing varies for some reason), in line with our expectation of near-linear performance in the total size of the problem.

Unfortunately, scaling this up by another order of magnitude creates an out-of-memory condition on this machine (the kernel tried to commit 20 GB but had only 12 GB available). This can be efficiently solved by breaking the first array into pieces of about a million elements each and applying this solution repeatedly, then reassembling the pieces. (This is embarrassingly parallel.) The timing increases to $O(n_1/10^6(10^6 + n_2)\log(10^6+n_2))$ which is barely greater than before: expect the whole operation to complete within a few minutes on a single core.

---

A more elegant way is to hash the elements of the target array (array2) and then scan across the source array (array1) for matches. An efficient hash will give a $O(n_1 \log(n_2))$ algorithm or, given enough RAM and few collisions, $O(n_1)$ (but with a modestly large implicit coefficient depending on how complex the elements of the target array are). I tried this using Dispatch and it worked well on small problems but did not scale up at all.

---

In any event, here's the timing code

n1 = 10^6;
n2 = 2 10^5;
array1 = Array[{"a", #, "z"} &, n1];
array2 = {"a", #, # Pi} & /@ RandomSample[Range[n1], n2];
Length[result = Rest /@ Select[GatherBy[Sort[array1~Join~array2], Most], Length[#] > 1 &]] 
    // AbsoluteTiming

{6.1100102, 200000}

and an example of the output, which is a list of lists of matching elements from array2:

result[[1 ;; 10]]

{{{"a", 3, 3 [Pi]}}, {{"a", 5, 5 [Pi]}}, ... {{"a", 39, 39 [Pi]}}}

Answer 3

Something along this line:

array1[[#]] & /@ 
 Flatten[Position[array1[[All, {1, 2}]], #] & /@ 
   Intersection[array1[[All, {1, 2}]], array2[[All, {1, 2}]]]]

{{string1, 145745, a}, {string3, 56546, b}, {string7, 12355, b}}

If array2 is a subset of array1 we don't even need Intersection:

array1[[#]] & /@ 
  Flatten[Position[array1[[All, {1, 2}]], #] & /@ 
    array2[[All, {1, 2}]]]

{{string1, 145745, a}, {string3, 56546, b}, {string7, 12355, b}}

As an alternative:

Select[array1, (MemberQ[array2[[All, {1, 2}]], #1[[{1, 2}]]] &)]

{{string1, 145745, a}, {string3, 56546, b}, {string7, 12355, b}}

Or, as suggested by Pinguin Dirk:

Cases[array1, _?(MemberQ[array2[[All, {1, 2}]], #1[[{1, 2}]]] &)]

{{string1, 145745, a}, {string3, 56546, b}, {string7, 12355, b}}