Re: Complement replacement

*To*: mathgroup at smc.vnet.net*Subject*: [mg58640] Re: [mg58608] Complement replacement*From*: "Carl K. Woll" <carl at woll2woll.com>*Date*: Mon, 11 Jul 2005 04:19:25 -0400 (EDT)*References*: <200507100912.FAA06500@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

----- Original Message ----- From: <konstantpi at mail15.com> To: mathgroup at smc.vnet.net Subject: [mg58640] [mg58608] Complement replacement > 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 > Here is a possibility that is faster than Complement on my machine for this particular problem: missing[list_] := Module[{len = Length[list], a}, a = Range[len]; a[[list]] = 0; DeleteCases[a, 0]] The above function scales as O(n), and Complement scales as O(n log n) due to sorting, so for large enough input my function ought to be faster. For example, with the data: n = 10^6; pp = Table[Random[Integer, {1, n}], {n}]; We have the following comparison: In[26]:= c1=Complement[Range[Length[pp]],pp];//Timing c2=missing[pp];//Timing c1===c2 Out[26]= {1.594 Second,Null} Out[27]= {0.625 Second,Null} Out[28]= True A further slight increase in speed ought to be possible if you compile DeleteCases[a,0] since a is a list of integers. For example, define deletezeros as: deletezeros = Compile[{{a, _Integer, 1}}, Module[{b, len, j}, len = Length[a]; b = a; j = 0; Do[ If[a[[i]] =!= 0, b[[++j]] = a[[i]]], {i, len}]; Take[b, j]]] Then, replacing DeleteCases[a,0] with deletezeros[a] approximately doubles the speed. Carl Woll Wolfram Research

**References**:**Complement replacement***From:*konstantpi@mail15.com