[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
Prev by Date:
**Re: AW: Re: Page breaks and numbers don't seem to work**
Next by Date:
**RE: Sort by buried element in list**
Previous by thread:
**Re: faster sublist checking**
Next by thread:
**Re: faster sublist checking**
| |