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/