[Date Index] [Thread Index] [Author Index]

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