5
$\begingroup$

I have a list of lists

list={l1,l2,l3,l4,...};

and two elements e1,e2. I want to select from lists l1,l2,l3,... those containing elements e1,e2.

I tried

Select[list, MemberQ[#, e1] && MemberQ[#, e2] &];

but it's too slow (as list may be quite large and I have a lot of e1,e2 combinations).

$\endgroup$
3
  • $\begingroup$ Is list one dimensional or are the l1,l2.... each lists themselves? $\endgroup$
    – Jason B.
    Oct 15, 2015 at 10:38
  • $\begingroup$ l1,l2,... are lists as well $\endgroup$
    – T. Rihacek
    Oct 15, 2015 at 10:41
  • $\begingroup$ Cases looks roughly twice as fast when using lists of lists of integers and e1 e2 also integers. $\endgroup$
    – LLlAMnYP
    Oct 15, 2015 at 11:14

1 Answer 1

5
$\begingroup$

Here's a mild improvement:

list = RandomInteger[{0, 9}, {50, 5}];
e1 = 1; e2 = 2;
Cases[list, {___, e1, ___, e2, ___} | {___, e2, ___, e1, ___}] // AbsoluteTiming
Select[list, MemberQ[#, e1] && MemberQ[#, e2] &] // AbsoluteTiming

{0.000227842, {{1, 2, 6, 5, 5}, {1, 9, 9, 1, 2}, {6, 1, 2, 8, 1}, {5, 2, 8, 2, 1}, {0, 0, 9, 1, 2}, {1, 2, 2, 4, 2}, {7, 7, 1, 9, 2}, {6, 0, 1, 2, 9}, {0, 0, 8, 2, 1}, {9, 5, 1, 2, 0}, {8, 1, 5, 2, 9}}}

{0.000355521, {{1, 2, 6, 5, 5}, {1, 9, 9, 1, 2}, {6, 1, 2, 8, 1}, {5, 2, 8, 2, 1}, {0, 0, 9, 1, 2}, {1, 2, 2, 4, 2}, {7, 7, 1, 9, 2}, {6, 0, 1, 2, 9}, {0, 0, 8, 2, 1}, {9, 5, 1, 2, 0}, {8, 1, 5, 2, 9}}}

Cases, as you can see, is slightly faster. Sadly the improvement is less than a factor of two.

Here's a much faster solution:

list = RandomInteger[{0, 9}, {50000, 5}];
e1 = 1; e2 = 2;
Pick[list, Unitize@(Count[#, e1] Count[#, e2] & /@ list), 1]
(* output omitted *)

Comparisons:

Select[list, MemberQ[#, e1] && MemberQ[#, e2] &] // 
  AbsoluteTiming // First
Cases[list, {___, e1, ___, e2, ___} | {___, e2, ___, e1, ___}] // 
  AbsoluteTiming // First
Pick[list, Unitize@(Count[#, e1] Count[#, e2] & /@ list), 1] // 
  AbsoluteTiming // First

(* 0.252361 *)

(* 0.133419 *)

(* 0.0178847 *)

About 15 times faster than Select/MemberQ.

The situation changes when I tried this with symbolic elements in the list:

Clear[a, b, c, d, e, f, g, h, i, j]
list = RandomChoice[{a, b, c, d, e, f, g, h, i, j}, {50000, 5}];
e1 = a; e2 = b;

Select[list, MemberQ[#, e1] && MemberQ[#, e2] &] // 
  AbsoluteTiming // First
Cases[list, {___, e1, ___, e2, ___} | {___, e2, ___, e1, ___}] // 
  AbsoluteTiming // First
Pick[list, Unitize@(Count[#, e1] Count[#, e2] & /@ list), 1] // 
  AbsoluteTiming // First

(* 0.158247 *)

(* 0.0228719 *)

(* 0.23266 *)

This time Cases is the fastest.

$\endgroup$
6
  • $\begingroup$ The method using Pick doesn't give the same answer as the others, see this: pastebin.com/raw.php?i=RxU0ribV $\endgroup$
    – Jason B.
    Oct 15, 2015 at 12:01
  • $\begingroup$ You are right, thanks for the heads up. The culprit is a necessary pair of parentheses. It does not seem to affect the timing. Editing now. $\endgroup$
    – LLlAMnYP
    Oct 15, 2015 at 12:14
  • $\begingroup$ @JasonB fixed. It was unitizing only the count of e1 before, not the product of the counts. The updated Pick is still the fastest for integers though. $\endgroup$
    – LLlAMnYP
    Oct 15, 2015 at 12:17
  • $\begingroup$ I was looking at this one too, and if you are interested in some really slow methods, try replacing the MemberQ[#, e1] && MemberQ[#, e2] & from OP's method with SubsetsQ[#,{e1,e2}]& or ContainsAll[#,{e1,e2}]& - simply atrocious results $\endgroup$
    – Jason B.
    Oct 15, 2015 at 12:19
  • 2
    $\begingroup$ Oh yeah, this new-found Contains-whatever functionality is terrible. I went through those too along the way. I do wonder, why patterns are so fast with symbols though and why Pick suffers a slowdown $\endgroup$
    – LLlAMnYP
    Oct 15, 2015 at 12:22

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.