Re: Generalizing Complement to handle multiple occurrences of elements
- To: mathgroup at smc.vnet.net
- Subject: [mg112458] Re: Generalizing Complement to handle multiple occurrences of elements
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Thu, 16 Sep 2010 05:59:41 -0400 (EDT)
Mark Coleman wrote:
> Greetings,
>
> I'm wondering how one can efficiently generalize the built-in
> Complement function to return multiple occurrences of elements. For
> instance, the current version generates
>
> a={1,2,2,3,4,4,4,4}
> b={3,5,7}
>
> Complement[a,b]={1,2,4}
>
> I'm looking for a way to define
>
> myComplement[a,b]={1,2,2,4,4,4,4}
>
> My current code is very inefficient!
>
> Thanks,
>
> Mark
>
Could use DeleteCases. Except it is currently a bit slow if the second
list is large. Here is a variant that is faster. (I was asked this
in-house not too long ago, hence already had code available.)
deleteCasesPatternFree[l1_List, l2_List] := Module[
{hh, seq},
Map[(hh[#] = True) &, l2];
Table[
If[TrueQ[hh[l1[[j]]]], seq, l1[[j]]], {j, Length[l1]}] /.
seq -> Sequence[]
]
Example:
n = 5;
l1 = RandomInteger[10^n, 2*10^n];
l2 = RandomInteger[10^n, 5*10^(n-1)];
In[12]:= Timing[res2 = deleteCasesPatternFree[l1,l2];]
Out[12]= {0.525921, Null}
In the development kernel this is quite fast, so I'll show that as well.
In[13]:= Timing[res1 = DeleteCases[l1, Alternatives @@ l2];]
Out[13]= {0.114982, Null}
In[14]:= res1===res2
Out[14]= True
Daniel Lichtblau
Wolfram Research