RE: Fast way to select those elements from a list that are in another

• To: mathgroup at smc.vnet.net
• Subject: [mg87083] RE: Fast way to select those elements from a list that are in another
• From: "Andrew Moylan" <andrew.j.moylan at gmail.com>
• Date: Mon, 31 Mar 2008 02:05:04 -0500 (EST)
• References: <frt574\$sj8\$1@smc.vnet.net> <47EFACC1.90909@gmail.com>

```Unfortunately, Pick[a, Thread[a == b]] doesn't perform the same task. In
your example, s3 typically evaluates to Sequence[]. That's why s1===s2===s3
subsequently evaluates to true:

s1===s2===s3
>> SameQ[s1,s2,Sequence[]]
>> SameQ[s1,s2]
>> True

This brings up an interesting quirk: you can only use SameQ to verify that
two things are identical if you can be sure that none of them is Sequence[]!

-----Original Message-----
From: Jean-Marc Gulliet [mailto:jeanmarc.gulliet at gmail.com]
Sent: Monday, 31 March 2008 2:08 AM
To: Andrew Moylan; mathgroup at smc.vnet.net
Subject: [mg87083] Re: Fast way to select those elements from a list that are in
another

Andrew Moylan wrote:

> Two lists of integers:
>
> {a, b} = Table[RandomInteger[10000, 1000], {2}];
>
> Which elements from a are in b?
>
> Select[a, MemberQ[b, #] &]; // Timing
>>> {0.351, Null}
>
> It takes about 0.351 seconds (on my slow laptop). Specialised
> functions for related tasks, such as Intersection[a, b], are much
> faster:
>
> Intersection[a, b]; // Timing
>>> {0., Null}
>
> Using Intersection, here's a somewhat faster way to select those
> elements from a that are in b:
>
> With[
>    {c = Intersection[a, b]},
>    Select[a, MemberQ[c, #] &]
>    ]; // Timing
>>> {0.09, Null}
>
> Is there a better, faster way to do this?

Andrew,

I have came up with the following, which is, I believe, the fastest among
all solutions that have been posted (as of today):

For instance,

{a, b} = Table[RandomInteger[10000, 1000], {2}];

s1 = Select[a, MemberQ[b, #] &]; // Timing // First

s2 = With[{c = Intersection[a, b]}, Select[a, MemberQ[c, #] &]]; //
Timing // First

s3 = Pick[a, Thread[a == b]]; // Timing // First

s1 === s2 === s3

(*

0.127442

0.01327

0.000111

True

*)

Regards,
--
Jean-Marc

```

• Prev by Date: Re: floating point issue
• Next by Date: Separate input/output files
• Previous by thread: Re: Fast way to select those elements from a list that are in another
• Next by thread: floating point issue