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

*To*: mathgroup at smc.vnet.net*Subject*: [mg86782] Re: Fast way to select those elements from a list that are in another*From*: Szabolcs Horvát <szhorvat at gmail.com>*Date*: Thu, 20 Mar 2008 05:50:12 -0500 (EST)*Organization*: University of Bergen*References*: <frt574$sj8$1@smc.vnet.net>

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.