MathGroup Archive 2008

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

Search the Archive

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


  • Prev by Date: Re: Find Upper Neighbor in a list
  • Next by Date: Re: NMinimize Error In Evaluation
  • Previous by thread: Re: List complement operator
  • Next by thread: Re: List complement operator