SubsetQ challenge
- To: mathgroup at smc.vnet.net
- Subject: [mg27281] SubsetQ challenge
- From: Rob Pratt <rpratt at email.unc.edu>
- Date: Sat, 17 Feb 2001 03:30:56 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
I would like a fast implementation of a function SubsetQ[s1,s2] that
returns True if s1 is a subset of s2, False otherwise. For simplicity,
assume that s1 and s2 are already sorted and Length[s1] <= Length[s2]. I
have already tried the following:
Complement[s1,s2]=={};
Complement[s1,s2]==={};
Length[Complement[s1,s2]]==0;
Union[s1,s2]==s2;
Union[s1,s2]===s2;
Length[Union[s1,s2]]==Length[s2];
s1==Intersection[s1,s2];
s1===Intersection[s1,s2];
Length[s1]==Length[Intersection[s1,s2]];
And@@(MemberQ[s2,#]&/@ s1);
I have done a few timing tests. The first nine versions are comparable in
speed, but the tenth version (using MemberQ) takes about twice as long as
the others.
Rob Pratt
Department of Operations Research
The University of North Carolina at Chapel Hill
rpratt at email.unc.edu
http://www.unc.edu/~rpratt/