Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2008

[Date Index] [Thread Index] [Author Index]

Search the Archive

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

  • To: mathgroup at smc.vnet.net
  • Subject: [mg86806] Re: Fast way to select those elements from a list that are in another
  • From: "Andrew Moylan" <andrew.j.moylan at gmail.com>
  • Date: Fri, 21 Mar 2008 01:55:52 -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?
> >
>
> Hi Andrew,
>
> You did not formulate the problem precisely.  There are two differences
> between c and d = Select[a, MemberQ[c, #] &.  One is that c is sorted,
> while d is not, and the other is that duplicates are removed from c.
> Which of these two are important?
>
> If only one of the two is important then I can come up with much faster
> solutions, but if *both* are important then the problem becomes more
> difficult.
>


  • Prev by Date: Re: floating point issue
  • Next by Date: Re: Bug: symbol recreates itself suddenly
  • Previous by thread: Re: Fast way to select those elements from a list that are in another
  • Next by thread: Re: Fast way to select those elements from a list that are in another