Re: List complement operator
- To: mathgroup at smc.vnet.net
- Subject: [mg85161] Re: List complement operator
- From: Mark Fisher <particlefilter at gmail.com>
- Date: Wed, 30 Jan 2008 06:14:33 -0500 (EST)
- References: <fn1ndi$97t$1@smc.vnet.net> <fn21s3$irs$1@smc.vnet.net>
On Jan 29, 5:39 am, Mark Fisher <particlefil... at gmail.com> wrote:
> On Jan 25, 8: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
>
> I like Daniel's version, but it doesn't seem to produce the correct
> result when applied to your original test data. (It includes the 8
> from list b.) However, a modification of his replacement rule fixes
> the problem. In addition by using Tally, the speed can be increased on
> integer lists (because Tally is blindingly fast on integer lists).
> Here's my slightly modified version:
>
> f3a[a_List, b_List] :=
> Flatten@(Table[#[[1]], {#[[2]]}] & /@
> Select[((Tally /@ {a, b}) //.
> {{x1___, {x2_, x3_}, x4___}, {x5___, {x2_, x6_}, x7___}} :>
> {{x1, {x2, x3 - x6}, x4}, {x5, x7}})[[1]],
> #[[2]] > 0 &])
>
> --Mark
The rule-based solutions (such as mine and Daniel's) bog down when the
number of alternatives increases. The following procedural code
maintains its speed even in that case.
SetSubtract[s1_List, s2_List] :=
Module[{t1, t2, n1, n2, i1, i2},
{t1, t2} = Sort[Tally[#]] & /@ {s1, s2};
{n1, n2} = Length /@ {t1, t2};
i1 = i2 = 1;
While[
i1 <= n1 && i2 <= n2,
Which[
t1[[i1, 1]] === t2[[i2, 1]],
t1[[i1, 2]] -= t2[[i2, 2]];
i1++; i2++,
OrderedQ[{t1[[i1, 1]], t2[[i2, 1]]}],
i1++,
True,
i2++
]
];
Flatten[Table[#[[1]], {#[[2]]}] & /@ Select[t1, #[[2]] > 0 &], 1]
]
--Mark