RE: SsssComplement?
- To: mathgroup at smc.vnet.net
- Subject: [mg37880] RE: [mg37831] SsssComplement?
- From: "Wolf, Hartmut" <Hartmut.Wolf at t-systems.com>
- Date: Sat, 16 Nov 2002 01:15:51 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
>-----Original Message----- >From: Wolf, Hartmut To: mathgroup at smc.vnet.net >Sent: Friday, November 15, 2002 9:02 AM >To: 'Mozalev Vasil'; mathgroup at smc.vnet.net >Subject: [mg37880] RE: [mg37831] SsssComplement? > > > >>-----Original Message----- >>From: Mozalev Vasil [mailto:mvp at snklik.ryazan.ru] To: mathgroup at smc.vnet.net >>Sent: Thursday, November 14, 2002 12:12 PM >>To: mathgroup at smc.vnet.net >>Subject: [mg37880] [mg37831] SsssComplement? >> >> >>Hi. Excuse me for poor-quality English language. >>My question about "Complement" and "UnsortedComplement". >>Function " UnsortedComplement [list, listi] " working more slowly then >>function " Complement >>[list, listi] " because deletes elements "listi" behind many >>passes, whereas >>" Complement [list, >>listi] " it makes for one pass. >>What kind of procedure I can use to write " SssssComplement >>[list, list1] " >>for maintenance of >>removal elements "list1" from "list" without sorting, but for >one pass? >>The specified lists already are sorted before their processing >>by function " >>SssssComplement >>[list, list1] ". >>It is necessary for acceleration of accounts. >>Example for check of correctness of work of required function: >>SssssComplement [{1,3,5,7,10}, {3, 7,10}] should give >>{1,5}. >>But >>SssssComplement [{1,3,5,7,10}, {7,3,10}] should give >>{1,3,5}, as for one pass the number 3 will not leave. >>Thank you. >>Vasil. >> >> >> >> >> >> >> > >Vasil, > >in honour of Carl Woll's unforgetable OrderedUnion: >http://forums.wolfram.com/mathgroup/archive/1999/Jul/msg00085.html > > >OrderedComplement[l_List,ll___List]:= > Block[{i,Sequence}, > i[n_]:=n; > Scan[(i[#]=Sequence[])&, Union[ll]]; > i/@l] > > >In[2]:= OrderedComplement[{5,7,1,3,10},{10,7,3}] >Out[2]= {5,1} > >In[3]:= OrderedComplement[{5,7,1,3,10},{10},{7,3}] >Out[3]= {5,1} > >In[4]:= 0rderedComplement[{5,7,1,3,10}] >Out[4]= {5,7,1,3,10} > >("Ordered" here means, the existing order is not destroyed, >rather than re-ordered.) > > >Here also a more straightforward alternative solution: > >In[12]:= UnsortedComplement[l_List, ll___List] := > l[[ Sort[Flatten[Position[l, #] & /@ Complement[l, ll]]] ]] > >In[13]:= UnsortedComplement[{5, 7, 1, 3, 10}, {10, 7, 3}] >Out[13]= {5, 1} > >In[14]:= UnsortedComplement[{5, 7, 1, 3, 10}, {10}, {7, 3}] >Out[14]= {5, 1} > >In[15]:= UnsortedComplement[{5, 7, 1, 3, 10}] >Out[15]= {5, 7, 1, 3, 10} > >This may be advantageous when the complement is small (but the >lists were large). I didn't test however. > >-- >Hartmut Wolf > Essentially UnsortedComplement is a quadratic algorithm, such its range of applicability is rather narrow. Here now is an algorithm which like (the now obsolete) UnsortedComplement above uses built-in Complement and then restores order, but now is of linear Order (for the reconstruction phase); of course Complement -- though very fast -- is O[n log n] if n is the size of the input. UnsortedComplement[l_List, ll___List] := Block[{pos}, pos[_] := {}; MapIndexed[(pos[#1] = {pos[#1], #2}) &, l]; l[[Sort[Flatten[pos /@ Complement[l, ll]]] ]] ] Timings: In[2]:= x = Table[Random[Integer, 100000], {50000}]; y = Take[x, 40000]; In[4]:= z0 = Complement[x, y]; // Timing Out[4]= {0.481 Second, Null} In[6]:= z2 = OrderedComplement[x, y]; // Timing Out[6]= {11.236 Second, Null} In[8]:= z0 == Union[z2] Out[8]= True But In[9]:= Length[z0] Out[9]= 6336 In[10]:= Length[z2] Out[10]= 6661 In[26]:= z3 = UnsortedComplement[x, y]; // Timing Out[26]= {19.729 Second, Null} In[27]:= z2 == z3 Out[27]= True -- Hartmut Wolf