Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2005
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2005

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

Search the Archive

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/


  • Prev by Date: Re: MultiLink.exe, MultiLinkServer.exe
  • Next by Date: Re: Complement replacement
  • Previous by thread: Re: Complement replacement
  • Next by thread: Re: Re: Complement replacement