Re: List complement operator
- To: mathgroup at smc.vnet.net
- Subject: [mg85054] Re: List complement operator
- From: sashap <pavlyk at gmail.com>
- Date: Sat, 26 Jan 2008 04:58:44 -0500 (EST)
- References: <fn1ndi$97t$1@smc.vnet.net> <fn21s3$irs$1@smc.vnet.net>
On Jan 25, 7:46 pm, zac <replicator... at gmail.com> wrote:
> Thanks for all who replied.
>
> I've got several alternatives now, and would like to publish testing
> results, perhaps some of you are interested in them too. (I've made
> some modifications to the functions, like formatting the output to the
> desired format, etc.)
>
> (* Szabolcs *)
> f1[a_List, b_List] :=
> Join @@ (Table[#1, {#2}] & @@@
> Transpose@
> With[{u = Union[a, b]}, {u,
> Last /@ Sort@Tally@Join[a, u] -
> Last /@ Sort@Tally@Join[b, u]}]);
>
> (* Bob *)
> f2[a_List, b_List] :=
> Fold[Delete[#1, Position[#1, #2][[1, 1]]] &, a,
> Fold[DeleteCases[#1, #2] &, b, Complement[a, b]]];
>
> (* Daniel *)
> f3[a_List, b_List] := Module[{t},
> t = Join @@ (Split@Sort[#] & /@ {a, b});
> t = t /. x1 : {x_ ..} :> {x, Length[x1]};
> t = t //. {x1___, {x2_, x3_}, x4___, {x2_, x5_},
> x6___} :> {x1, {x2, x3 - x5}, x4, x6};
> Flatten@(Table[#[[1]], {#[[2]]}] & /@ Select[t, #[[2]] > 0 &])
> ];
>
> (* own *)
> f4[a_List, b__List] := Module[{tmp = a, pos},
> Scan[If[(pos = Position[tmp, #, 1, 1]) =!= {},
> tmp = Delete[tmp, pos[[1, 1]]]] &, Join[b]]; tmp];
>
> Results:
> 1. With test data:
>
> a = RDI[10] & /@ Range[1000];
> b = RDI[10] & /@ Range[1000];
>
> all functions return the same results (if sorted) except Bob's Fold-
> code, which fails. Since I don't have much time, and - to be honest -
> I could not understand fully his function, I did not try to solve the
> error.
> 2. Only the last function f4 returns the complement list in an
> unsorted way. This was not necessary, as I've stated it previously,
> although I'm interested in the way it can be made more efficient
> (because at the moment this piece of code labeled (* own *) is
> extremely sluggish)
> 3. Time results using test data:
>
> a = RDI[10] & /@ Range[1000000];
> b = RDI[10] & /@ Range[1000000];
>
> f1: 1.98sec
> f2: not tested due to some error
> f3: 1.125sec
> f4: more than 10 minutes
>
> Results speak for themselves. Both Szabolcs's and Daniel's code are
> very efficient, but sort data. Function f4 does not sort output, but
> is not usable for larger lists. Can anyone come up with an unsorted
> version of this list complement function?
>
> Thanks again for the suggestions and codes!
> Istvan
Under the assumption that lists a and b contain positive integers the
following
version is the fastest:
f5[a_List, b_List] :=
Block[{x},
Join @@ (ConstantArray @@@
DeleteCases[
List @@ (Total[(#2 x^#1 & @@@ Tally[a])] -
Total[(#2 x^#1 & @@@ Tally[b])]) /. {c_. x^(n_.) :> {n,
c}}, {_, _?NonPositive}])]
In[85]:= Timing[r1 = f1[a, b];]
Out[85]= {0.547, Null}
In[86]:= Timing[r3 = f3[a, b];]
Out[86]= {0.719, Null}
In[87]:= Timing[r5 = f5[a, b];]
Out[87]= {0.015, Null}
In[88]:= r1 === r3 === r5
Out[88]= True
Oleksandr Pavlyk