       Re: Complement replacement

• To: mathgroup at smc.vnet.net
• Subject: [mg58633] Re: Complement replacement
• From: konstantpi at mail15.com
• Date: Sun, 10 Jul 2005 16:52:01 -0400 (EDT)
• Sender: owner-wri-mathgroup at wolfram.com

```thanks very much for the answers,
my previous question was submitted, because at first i do not know
about the Complement function, i know that a function like this must
be in the Union, Intersection family, but somehow i have not noticed
the Complement in the documentation so i wrote my old way program:

pp = Table[Random[Integer, {1, 1000}], {i, 1000}];
r = Table[i,{i,1000}];
(lst = {}; Do[If[MemberQ[pp, r[[i]]] == False,
lst = Join[lst, {r[[i]]}];
]
, {i, 1, Length[pp]}];
lst = Union[lst, lst];) // Timing

{0.22 Second, Null}
on P4 2 GHz 128k cache 256M ram

after i have written my letter i have discovered the Complement
function, and noticed its speed, so i keep my original message to
compare different strategies and methods which may presented by this
group marvelous contributors
Thanks for all

To: mathgroup at smc.vnet.net
book)
Subject: [mg58633]  Re: [mg58608] Complement replacement

On 10 Jul 2005, at 18:12, konstantpi at mail15.com wrote:

> hi
> in the list:
> pp=Table[Random[Integer, {1, 1000}], {i, 1000}];
> how could i know which numbers from 1 to 1000 does not exist in the
> pp List.
> but without using:
> Complement[Table[i,{i,1000}],pp]
> regards
>
>

Perhaps you should explain why you do not want to use Complement as
it will be very hard if not impossible to match its performance.
Indeed, on ny machine I get:

In:=
pp=Table[Random[Integer, {1, 1000}], {i, 1000}];

In:=
a=Complement[Range,pp];//Timing

Out=
{0.001657 Second,Null}

while using the most obvious alternative:

In:=
b=Select[Range,Not[MemberQ[pp,#]]&];//Timing

Out=
{0.408538 Second,Null}

In:=
Union[b]==a

Out=
True

The difference in performance is huge. There are a number of ways
that give a better performance but I can't find any that beets
Complement. Here s one that is at least better than the most obvious
way above. First define a function f:

SetAttributes[f, Listable]

Scan[(f[#]=Sequence[])&,pp];//Timing

{0.020849 Second,Null}

f[x_] := x

(note that evaluating this defintion itself takes more time than
running Complement)

now:

In:=
c=f[Range];//Timing

Out=
{0.008274 Second,Null}

In:=
Union[c]==a

Out=
True

Andrzej Kozlowski

Chiba, Japan

> Peter Pein <petsie at dordos.net>:

> Please tell us why you want to do so.
>
> Cleaning up and generating testing data (I took a million values
> of thousand for distinguishable timings):
>
> In:= Clear[n, pp, missing];
>   n = 10^6;
>   pp = Table[Random[Integer, {1, n}], {n}];
>
> just as reference timing:
>
>   First[Timing[missing = Complement[Range[n], pp]; ]]
> Out  0.844*Second
>
> Sort the random list joined with the whole range, sort and split
this
> list and get the unique elements:
>
> In:  First[Timing[missing     Cases[Split[Sort[Join[pp, Range
[n]]]],
> {x_Integer} :> x];
> ]]
> Out  1.875*Second
>
> Method 'mind the gap' ;-) :
>  Build ranges out of the gaps in the random list:
>
> In:First[Timing[missing   Inner[Range, Drop[#1, -1] + 1, Drop
[#1, 1]
> - 1, Join]&
>     [Union[pp, {0, n + 1}]];
> ]]
> Out  1.609*Second
>
> Verification:
>
> In:  SameQ @@ missing /@ {1, 2, 3}
> Out  True
>
>
>
> --
> Peter Pein
> Berlin
> http://people.freenet.de/Peter_Berlin/
>

```

• Prev by Date: Re: GraphEdit.m & JavaGraphics.m
• Next by Date: Re: Re: Wrong Integral result for a Piecewise function
• Previous by thread: Re: Complement replacement
• Next by thread: Mathematica: how to set the format of binary numbers in plotting?