Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: Re: List complement operator

• To: mathgroup at smc.vnet.net
• Subject: [mg85047] Re: [mg85032] Re: List complement operator
• From: János <janos.lobb at yale.edu>
• Date: Fri, 25 Jan 2008 05:05:08 -0500 (EST)
• References: <fn1ndi$97t$1@smc.vnet.net> <fn21s3$irs$1@smc.vnet.net> <200801240949.EAA15085@smc.vnet.net>

On Jan 24, 2008, at 4:49 AM, zac 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
>
>

Istv=E1n,

Here is a plain algorithmic newbie approach that keeps the order

In[83]:=
While[Length[b] > 0,
   b1 = First[b];
    If[MemberQ[a, b1],
     a = DeleteCases[a, b1, 2,
       1], Null];
    b = Rest[b]; ]
Print[a];
 =46rom In[83]:=
{1, 1, 3, 5, 5, 5, 6, 7}

I am on 5.2, so I do not have RDI to check for speed.  with toy data 
it is {0.00033 Second, Null} on a G5.

Best,

J=E1nos

----------------------------------------------
Trying to argue with a politician is like lifting up the head of a 
corpse.
(S. Lem: His Master Voice)

• References:
  • Re: List complement operator
    • From: zac <replicatorzed@gmail.com>