Re: Re: Fast way to select those elements from a list

• To: mathgroup at smc.vnet.net
• Subject: [mg86818] Re: [mg86806] Re: Fast way to select those elements from a list
• From: danl at wolfram.com
• Date: Sat, 22 Mar 2008 00:52:39 -0500 (EST)
• References: <frt574\$sj8\$1@smc.vnet.net> <47E23A75.7030909@gmail.com>

```> To clarify: the list I want to construct is those elements from a that are
> members of b:
> Select[a, MemberQ[b, #] &]
>
> This is (I think!) the same as
>
> With[
>    {c = Intersection[a, b]},
>    Select[a, MemberQ[c, #] &]
>    ]
>
> but the latter is faster.
>
>
> On 20/03/2008, Szabolcs Horv=E1t <szhorvat at gmail.com> wrote:
>>
>> 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?
>> >
>> [...]

This seems fairly fast.

In[23]:= {a, b} = Table[RandomInteger[10000, 1000], {2}];
Timing[s1 = Select[a, MemberQ[b, #] &];]

Out[24]= {0.621, Null}

In[25]:= Timing[s2 = Module[{mq},
Map[(mq[#] = True) &, b];
Reap[Map[If[mq[#] === True, Sow[#]] &, a]]][[2, 1]];]

Out[25]= {0.02, Null}

In[26]:= s2 === s1
Out[26]= True

Daniel Lichtblau
Wolfram Research

```

• Prev by Date: ListPlot Joined/Filling bug?
• Next by Date: Problem involving NDSolve
• Previous by thread: Re: ListPlot Joined/Filling bug?
• Next by thread: Problem involving NDSolve