Re: Complement replacement

• To: mathgroup at smc.vnet.net
• Subject: [mg58619] Re: Complement replacement
• From: Peter Pein <petsie at dordos.net>
• Date: Sun, 10 Jul 2005 16:51:37 -0400 (EDT)
• References: <daqosi\$6d8\$1@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

```konstantpi at mail15.com schrieb:
> 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
>
Please tell us why you want to do so.

Cleaning up and generating testing data (I took a million values instead
of thousand for distinguishable timings):

In[1]:= Clear[n, pp, missing];
n = 10^6;
pp = Table[Random[Integer, {1, n}], {n}];

just as reference timing:

First[Timing[missing[1] = Complement[Range[n], pp]; ]]
Out[4]=
0.844*Second

Sort the random list joined with the whole range, sort and split this
list and get the unique elements:

In[5]:=
First[Timing[missing[2] =
Cases[Split[Sort[Join[pp, Range[n]]]], {x_Integer} :> x];
]]
Out[5]=
1.875*Second

Method 'mind the gap' ;-) :
Build ranges out of the gaps in the random list:

In[6]:=
First[Timing[missing[3] =
Inner[Range, Drop[#1, -1] + 1, Drop[#1, 1] - 1, Join]&
[Union[pp, {0, n + 1}]];
]]
Out[6]=
1.609*Second

Verification:

In[7]:=
SameQ @@ missing /@ {1, 2, 3}
Out[7]=
True

--
Peter Pein
Berlin
http://people.freenet.de/Peter_Berlin/

```