Re: A SubListQ function?
- To: mathgroup at smc.vnet.net
- Subject: [mg28549] Re: [mg28546] A SubListQ function?
- From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
- Date: Fri, 27 Apr 2001 03:56:04 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Of the three examples you give, the first is correct and in my opinion very
efficient (perhaps unbeatable), the second is wrong, and the third very
inefficient.
You can easily see that the second one is wrong, e.g.:
In[1]:=
ContainedQ[a_, b_] := Intersection[a, b] === a
In[2]:=
ContainedQ[{2, 1}, {1, 2, 3}]
Out[2]=
False
Of course you need to Sort a on the right hand side, which will slow down
your code. Still, even with Sort on the right hand side this beats your last
example by a big margin. As I said, the complement approach seems to me very
efficient and I will be very surprised if any one can beat it. Even the
second method will be hard to beat. Here are some test results in which I
include also one attempt I have tried (the only one). (My attempt assumes
that your lists do not contain Boolean values False and True as elements! If
this was really a problem one could easily deal with it but it seems to me
so unlikely I shan't bother).
In[1]:=
ContainedQ[1][a_List, b_List] := Complement[a, b] === {}
In[2]:=
ContainedQ[2][a_, b_] := Intersection[a, b] === Sort[a]
In[3]:=
ContainedQ[3][a_List, b_List] :=
Or @@ (a /. Dispatch[Thread[Rule[b, False]]]) === False
In[4]:=
ContainedQ[4][a_, b_] := And @@ (MemberQ[b, #] & /@ a)
My ContainedQ[3] fails well short of the first two in the case when a is a
sublist of b:
In[5]:=
b = Table[Random[], {5000}];
In[6]:=
a = Take[b, {2000, 4000}];
In[7]:=
(ContainedQ[#][a, b] // Timing) & /@ Range[4]
Out[7]=
{{0.0166667 Second, True}, {0.0333333 Second, True}, {0.183333 Second,
True}, {28.5 Second, True}}
However when a is not a sublist of b ContainedQ[3] seems to catch with the
ContainedQ[2] and is just slightly behind ContainedQ[1], for this range of
values anyway (and on my old 266 mghz Mac!):
a = Append[a, dog];
In[9]:=
(ContainedQ[#][a, b] // Timing) & /@ Range[4]
Out[9]=
{{0.133333 Second, False}, {0.166667 Second, False}, {0.166667 Second,
False}, {28.9333 Second, False}}
--
Andrzej Kozlowski
Toyama International University
JAPAN
http://platon.c.u-tokyo.ac.jp/andrzej/
http://sigma.tuins.ac.jp/
on 01.4.26 8:21 AM, AGUIRRE ESTIBALEZ Julian at mtpagesj at lg.ehu.es wrote:
> Given two lists a and b, how can I find if a is contained in b? I have
> tried
>
> Complement[a, b] == {}
>
> Intersection[a, b] == a
>
> And@@(MemberQ[#,b]&/@a)
>
> They work, but are not very efficient. Is there a better way?
>
> Thanks in advance,
>
> Julian Aguirre
> Universidad del Pais Vasco
>
>
>