# Efficiently extracting an array subset given a separate array

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

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.

-
Have a look at this: A fast implementation in Mathematica for Position2D –  Mr.Wizard Jan 15 '13 at 14:56

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]],
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).

-
This solution is elegant and FAST! I was thinking that I should label the positions in array1 as is done in memberPositions but thought it would hinder performance. I was certainly wrong. I did make a minor amendment to the solution, though. I Mapped the memberpositions to {{1,2}} rather than {1,2} to explicitly require that both the first and second column of any given row matches the a row in the other array. Otherwise, I might collect unwanted rows, such as {string7, 145745, a} if it were in array1 but not in array2. –  Christopher Bowman Jan 15 '13 at 18:34
I used array1[[Intersection @@ Map[memberPositions[array1[[All, #]], array2[[All, #]]] &, {{1, 2}}]]] –  Christopher Bowman Jan 15 '13 at 18:36
@ChristopherBowman Sorry, I don't get your objection. The Intersection takes care of possible extra rows, so this should work. Your modification is quite elegant though, and you can remove the Intersection@@ part with it, I think. –  Leonid Shifrin Jan 15 '13 at 18:39
To give others an idea of the incredible speed, Pick takes over 25 minutes for array1 size 1.5 million rows and array2 size of 8700. Shifrins' solution takes 3.47 seconds. I've also performed the solution on my total dataset (array1 has 19.7 million rows, array2 has 175,000 rows) and it took 121 seconds. Breaking array1 down into 21 chunks, it takes 72.1 seconds. This is tested on V6.0, Intel Corei7 x4 2.4GHz, 8GB RAM. I didn't test whuber's solution as I have V6.0 on this computer. –  Christopher Bowman Jan 15 '13 at 18:46
Yes, the Intersection is not needed with the modifition, but the Mapped result will need to be Flattened. The reason the Intersection does not work, at least in my case, is that memberPositions is first mapped to select all stringN and then mapped to select all integers K without requiring that the strict combination of {stringN, K} be present. Thus, if array1 = {{string1, 145745, a},{string2, 56546, a},{string3, 56546, b},{string3, 246, b},{string7, 145745, a},{string7, 12355, b}} and array2 = {{string1, 145745, 3.14324},{string3, 56546, -0.34319},{string7, 12355, 0.23535}} –  Christopher Bowman Jan 15 '13 at 19:28

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}}

-
Another approach (I did not think of Intersection) with the same result would be Cases[array1, _?(MemberQ[array2[[All, {1, 2}]], #1[[{1, 2}]]] &)] but both these results differ from the result he posted above (and that I don't understand) –  Pinguin Dirk Jan 15 '13 at 13:43
@PinguinDirk I suppose that there is a typo in the results defined by the OP, there is no {string7, 12355, a} element in array1. –  VLC Jan 15 '13 at 13:51
I agree, let's wait for some reaction –  Pinguin Dirk Jan 15 '13 at 13:54
@PinguinDirk Sorry for the confusion. VLC is correct in that I made a mistake, which has been corrected above. Previously, there was not {string7, 12355, a} element in array1, but there should have been and it is there now. Also, I have tried Select, Cases, and Position in various combinations identical or similar to yours, but, unfortunately, those setups are dismally slower than the Pick command I've implemented so far, around 1 order of magnitude slower at best. –  Christopher Bowman Jan 15 '13 at 16:10
I also thought to use Intersection but then realized that, since array2[[All,{1,2}]] is a subset of array1[[All,{1,2}]], the Intersection is already simply array2[[All,{1,2}]]. –  Christopher Bowman Jan 15 '13 at 16:19

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]}}}

-
+1. You can use SplitBy if you are explicitly sorting them before –  Rojo Jan 15 '13 at 14:46