Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Re: List complement operator

• To: mathgroup at smc.vnet.net
• Subject: [mg85032] Re: List complement operator
• From: zac <replicatorzed at gmail.com>
• Date: Thu, 24 Jan 2008 04:49:15 -0500 (EST)
• References: <fn1ndi$97t$1@smc.vnet.net> <fn21s3$irs$1@smc.vnet.net>

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

• Follow-Ups:
  • Re: Re: List complement operator
    • From: János <janos.lobb@yale.edu>