9
$\begingroup$

Can I say this is a bad performance from the new V10 function SubsetQ?

Here are some tests comparing it to Complement[l2, l1] === {}

count1[data_,list_]:=Module[{r},
   r=SubsetQ[#,list]&/@data;
   Counts[r]
]

count2[data_,list_]:=Module[{r},
    r=Complement[list,#]==={}&/@data;
    Counts[r]
]

Small columns test:

$HistoryLength = 0;
data = RandomInteger[100, {100000, 10}];
list = {4, 3, 2, 1};

count1[data, list] // AbsoluteTiming
count2[data, list] // AbsoluteTiming

{2.760775, <|False -> 99995, True -> 5|>} {0.450933, <|False -> 99995,True -> 5|>}

Large columns test:

$HistoryLength=0;
data=RandomInteger[100,{100000,100}];
list={4, 3, 2, 1};

count1[data,list]//AbsoluteTiming
count2[data,list]//AbsoluteTiming

{3.345720, <|False -> 97745, True -> 2255|>} {0.910420, <|False -> 97745, True -> 2255|>}

Update:

Still slow in V10.1

$\endgroup$
2
  • 2
    $\begingroup$ Filed as a possible speed issue. I believe it will get investigated. $\endgroup$ Oct 6, 2014 at 17:58
  • $\begingroup$ @DanielLichtblau Tks. $\endgroup$
    – Murta
    Oct 6, 2014 at 20:14

2 Answers 2

8
$\begingroup$

SubsetQ is implemented in top-level using Complement[a, b] === {}. It has some overhead because it has to treat associations specially, plus it has to go through the requisite error-handling rigmarole. But has the same time complexity in the length of the first argument:

enter image description here

But this is on the shortlist of functions to reimplement in C when we have time. There are other patients that are more worthy of the "Vitamin C" treatment, however :).

$\endgroup$
1
  • 1
    $\begingroup$ Tks for the explanation. An Hashed Operator form for SubsetQ (IntersectingQ and so on) would be really welcome. $\endgroup$
    – Murta
    Oct 6, 2014 at 22:03
1
$\begingroup$

EDIT

After comments from RunnyKine...

Just another approach and timing:

subs[u_, v_] := Length@Intersection[u, v] == Length@v

Performance:

 BenchmarkPlot[{count1[#, list] &, count2[#, list] &, 
 Tally@Map[Function[x, subs[x, list]], #] &}, 
 RandomInteger[100, {100000, #}] &, PowerRange[1, 1000], 
 "IncludeFits" -> True, Frame -> True]

enter image description here

$\endgroup$
2
  • 1
    $\begingroup$ See the comment below Mr. Wizard's answer in relation to the weird exponential fits in your timings. $\endgroup$
    – RunnyKine
    Oct 6, 2014 at 11:59
  • $\begingroup$ @RunnyKine thank you! see edit...still something problematic with count1 $\endgroup$
    – ubpdqn
    Oct 6, 2014 at 12:08

Your Answer

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

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