Re: Complement replacement
- To: mathgroup at smc.vnet.net
- Subject: [mg58633] Re: Complement replacement
- From: konstantpi at mail15.com
- Date: Sun, 10 Jul 2005 16:52:01 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
thanks very much for the answers, my previous question was submitted, because at first i do not know about the Complement function, i know that a function like this must be in the Union, Intersection family, but somehow i have not noticed the Complement in the documentation so i wrote my old way program: pp = Table[Random[Integer, {1, 1000}], {i, 1000}]; r = Table[i,{i,1000}]; (lst = {}; Do[If[MemberQ[pp, r[[i]]] == False, lst = Join[lst, {r[[i]]}]; ] , {i, 1, Length[pp]}]; lst = Union[lst, lst];) // Timing {0.22 Second, Null} on P4 2 GHz 128k cache 256M ram after i have written my letter i have discovered the Complement function, and noticed its speed, so i keep my original message to compare different strategies and methods which may presented by this group marvelous contributors Thanks for all From: Andrzej Kozlowski <akozlowski at gmail.com> ( Add to address To: mathgroup at smc.vnet.net book) Subject: [mg58633] Re: [mg58608] Complement replacement On 10 Jul 2005, at 18:12, konstantpi at mail15.com wrote: > 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 > > Perhaps you should explain why you do not want to use Complement as it will be very hard if not impossible to match its performance. Indeed, on ny machine I get: In[1]:= pp=Table[Random[Integer, {1, 1000}], {i, 1000}]; In[2]:= a=Complement[Range[1000],pp];//Timing Out[2]= {0.001657 Second,Null} while using the most obvious alternative: In[3]:= b=Select[Range[1000],Not[MemberQ[pp,#]]&];//Timing Out[3]= {0.408538 Second,Null} In[4]:= Union[b]==a Out[4]= True The difference in performance is huge. There are a number of ways that give a better performance but I can't find any that beets Complement. Here s one that is at least better than the most obvious way above. First define a function f: SetAttributes[f, Listable] Scan[(f[#]=Sequence[])&,pp];//Timing {0.020849 Second,Null} f[x_] := x (note that evaluating this defintion itself takes more time than running Complement) now: In[8]:= c=f[Range[1000]];//Timing Out[8]= {0.008274 Second,Null} In[9]:= Union[c]==a Out[9]= True Andrzej Kozlowski Chiba, Japan > Peter Pein <petsie at dordos.net>: > 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/ >