Mathematica Stack Exchange is a question and answer site for users of Wolfram Mathematica. It only takes a minute to sign up.
Sign up to join this community
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).
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.
Pick doesn't give the same answer as the others, see this: pastebin.com/raw.php?i=RxU0ribV
$\endgroup$
e1 before, not the product of the counts. The updated Pick is still the fastest for integers though.
$\endgroup$
MemberQ[#, e1] && MemberQ[#, e2] & from OP's method with SubsetsQ[#,{e1,e2}]& or ContainsAll[#,{e1,e2}]& - simply atrocious results
$\endgroup$
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$
listone dimensional or are thel1,l2....each lists themselves? $\endgroup$l1,l2,...are lists as well $\endgroup$Caseslooks roughly twice as fast when using lists of lists of integers ande1e2also integers. $\endgroup$