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/