RE: Re: faster sublist checking
- To: mathgroup at smc.vnet.net
- Subject: [mg48927] RE: [mg48719] Re: faster sublist checking
- From: "Wolf, Hartmut" <Hartmut.Wolf at t-systems.com>
- Date: Thu, 24 Jun 2004 05:35:43 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
- Thread-topic: [mg48719] Re: faster sublist checking
>-----Original Message----- >From: Ray Koopman [mailto:koopman at sfu.ca] To: mathgroup at smc.vnet.net >Sent: Friday, June 11, 2004 9:53 AM >To: mathgroup at smc.vnet.net >Subject: [mg48927] [mg48719] Re: faster sublist checking > > >gimbo20032003 at libero.it (giorgio borghi) wrote in message >news:<ca6hlt$fgj$1 at smc.vnet.net>... >> which is the faster implementantion of function that checks if a list >> A is a sublist of B. es: A={3,4,5} B={1,2,3,4,5,6,7} gives True? > >In[1]:= B = Table[Random[Integer],{1*^4}]; > >In[2]:= A = Table[Random[Integer],{10}] >Out[2]= {1,0,0,1,1,0,1,0,0,0} > >This is equivalent to Jens-Peer's probably-shortest solution: > >In[3]:= MatchQ[B,{__,Sequence@@A,__}] //Timing >Out[3]= {17.2419 Second,True} > >This is almost as short, and much faster: > >In[4]:= MemberQ[Partition[B,Length[A],1],A] //Timing >Out[4]= {0.999832 Second,True} > > Ray, to me your timings appear somewhat mysterious: In[37]:= B = Table[Random[Integer], {1*^6}]; A = Table[Random[Integer], {10}] Out[38]= {1, 0, 1, 1, 0, 1, 0, 0, 0, 1} Tests: In[39]:= MemberQ[Partition[B, Length[A], 1], A] // Timing Out[39]= {2.453 Second, True} In[40]:= Position[Partition[B, Length[A], 1], A, 1, 1] // Timing Out[40]= {2.824 Second, {{567}}} (This was my first thought, it also gives the Position of the first occurrance, only slightly slower) But Jens idea (and my second thought: pattern matching ought to be quite fast here) gives: In[41]:= MatchQ[B, Join[{___}, A, {___}]] // Timing Out[41]= {0.13 Second, True} Well, I have In[44]:= $Version Out[44]= "4.1 for Microsoft Windows (November 2, 2000)" although In[46]:= Developer`PackedArrayQ[Partition[B, Length[A], 1]] Out[46]= True But what a difference in Timing! In[47]:= 17.2419/0.999832 * 2.453/0.13 Out[47]= 325.396 I'm not sure, but perhaps it's me who should upgrade. No, no, just found it: In[48]:= B1 = Developer`FromPackedArrayQ[B]; In[49]:= A1 = Developer`FromPackedArrayQ[A]; In[50]:= MemberQ[Partition[B1, Length[A1], 1], A1] // Timing Out[50]= {0.14 Second, False} Which on my machine, my version, is of the same order, which appears reasonable (to me). See here, what a hindrance packed arrays might be. But still cannot quite understand your observation. -- Hartmut Wolf