13
$\begingroup$

I have two large lists: list1 and list2. I would like to select elements of list1 only if they appear in list2. Since the list1 has dimensions of (335000, 2) and list2 : (122000, 4), it's taking a very long time.

How could I speed up the process?

Select[list1, MemberQ[list2[[All, 2]], #[[1]]] &]
Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Intersection? $\endgroup$
    – shrx
    Jun 6, 2015 at 13:11
  • $\begingroup$ well Intersection helps but doesn't quite do it because I want to keep the whole element, not only the key that is to be found in list2... $\endgroup$
    – Cancan
    Jun 6, 2015 at 13:27
  • 1
    $\begingroup$ One should not have to decode your code to figure out format of lists - please add some simple list1/2 examples. $\endgroup$
    – ciao
    Jun 6, 2015 at 22:20
  • $\begingroup$ @ciao would you consider adding examples yourself, please? $\endgroup$
    – Mr.Wizard
    Sep 5, 2017 at 6:57
  • $\begingroup$ @Mr.Wizard - I don't know what you mean. $\endgroup$
    – ciao
    Sep 5, 2017 at 7:04

3 Answers 3

Reset to default
8
$\begingroup$

This should be pretty snappy:

With[{t = First@Transpose@#1, t2 = Transpose[#2][[2]]}, 
   Pick[#1, Replace[t, Dispatch[Thread[Rule[Intersection[t, t2], True]]], {1}]]] &[list1, list2]
Improve this answer
$\endgroup$
6
  • $\begingroup$ thanks ciao, it is really fast! $\endgroup$
    – Cancan
    Jun 8, 2015 at 20:38
  • $\begingroup$ What would I have change where if I wanted to match column 2 of list1 with column 3 of list2? $\endgroup$
    – Cancan
    Jun 8, 2015 at 20:40
  • $\begingroup$ @Cancan: ...Transpose[#1][[2]], t2 = Transpose[#2][[3]]..., etc. $\endgroup$
    – ciao
    Jun 8, 2015 at 20:59
  • 1
    $\begingroup$ @Cancan: Or perhaps more useful : With[{t = Transpose[#1][[#3]], t2 = Transpose[#2][[#4]]}, Pick[#1, Replace[t, Dispatch[ Thread[Rule[Intersection[t, t2], True]]], {1}]]] &[list1, list2, 2, 3] - so this has last two arguments being the cols. for lists 1/2... this form also can be used obviously for any size sublists pair of lists... $\endgroup$
    – ciao
    Jun 8, 2015 at 21:02
  • $\begingroup$ Thanks, this form is great! I tried to use it for selection based on 2 columns together but it didn't work: ...[list1, list2, {1,2},{2,4}], what would you recommend? Also, I tried to use it for selection based on a ! MemberQ pattern but it didn't work, how would you do it with this form? $\endgroup$
    – Cancan
    Jun 13, 2015 at 20:51
6
$\begingroup$

Perhaps not the fastest, but reasonably fast (requires V10+):

Select[Association[Thread[list2[[All, 2]] -> True]] @* First][list1]

A slightly slower version of this to use for earlier versions:

With[{rules = Dispatch[Thread[list2[[All, 2]] -> True]]},
   Select[list1, Replace[First[#], rules] &]
]
Improve this answer
$\endgroup$
5
  • $\begingroup$ thanks but I use V9... :( $\endgroup$
    – Cancan
    Jun 6, 2015 at 13:25
  • $\begingroup$ @Cancan I updated the answer with code that should work for you. $\endgroup$
    – Leonid Shifrin
    Jun 6, 2015 at 13:30
  • $\begingroup$ This was similar to my option!.. I lost by few minutes. :) +1 $\endgroup$
    – Murta
    Jun 8, 2015 at 11:59
  • $\begingroup$ thanks Leonid! it works but it is not as fast than ciao's answer, which is why I accepted his answer. $\endgroup$
    – Cancan
    Jun 8, 2015 at 20:41
  • 1
    $\begingroup$ @Cancan Sure, it is always proper to accept the best answer. I voted for that one, too. $\endgroup$
    – Leonid Shifrin
    Jun 8, 2015 at 21:37
3
$\begingroup$

One can make use of Nearest for this purpose (I should mention that the speed improvement may only occur in M11.1+). Here is a function that does this:

carl[l1_,l2_] := With[{nf = Nearest[l2[[All, 2]] -> "Index"]},
    Pick[
        l1,
        Unitize[Length /@ nf[l1[[All, 1]], {All, 0}]],
        1
    ]
]

The key idea is the use of the {All, 0} spec for the NearestFunction nf, that only returns a result for exact hits. Let's compare this to @ciao's approach (modified to be a function):

ciao[l1_, l2_] := With[{t = First@Transpose@l1, t2 = Transpose[l2][[2]]},
    Pick[
        l1,
        Replace[t, Dispatch[Thread[Rule[Intersection[t, t2],True]]], {1}]
    ]
]

data1 = RandomInteger[10^6, {335000,2}];
data2 = RandomInteger[10^6, {122000,4}];

r1 = ciao[data1, data2]; //RepeatedTiming
r2 = carl[data1, data2]; //RepeatedTiming

r1 === r2

{0.41, Null}

{0.17, Null}

True

So, a speed up of about 2.5.

Update

After further thought, it makes sense to apply NearestFunction to the other data list. So, here is a version that uses this approach:

carl2[l1_, l2_] := With[{nf = Nearest[l1[[All,1]]->"Index"]},
    l1[[Union @@ nf[l2[[All, 2]], {All, 0}]]]
]

Here is another speed comparison:

data1 = RandomInteger[10^6, {335000,2}];
data2 = RandomInteger[10^6, {122000,4}];

r1 = ciao[data1, data2]; //RepeatedTiming
r2 = carl[data1, data2]; //RepeatedTiming
r3 = carl2[data1, data2]; //RepeatedTiming

r1 === r2 === r3

{0.37, Null}

{0.17, Null}

{0.10, Null}

True

A nice speed up!

Improve this answer
$\endgroup$
1
  • $\begingroup$ Nice. +1 $\phantom{}$ $\endgroup$
    – ciao
    Sep 5, 2017 at 6:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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