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$
  • $\begingroup$ Is list one dimensional or are the l1,l2.... each lists themselves? $\endgroup$ – Jason B. Oct 15 '15 at 10:38
  • $\begingroup$ l1,l2,... are lists as well $\endgroup$ – T. Rihacek Oct 15 '15 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 '15 at 11:14
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$
  • $\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 '15 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 '15 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 '15 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 '15 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 '15 at 12:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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