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

*To*: mathgroup at smc.vnet.net*Subject*: [mg86797] Re: Fast way to select those elements from a list that are in another*From*: Szabolcs Horvát <szhorvat at gmail.com>*Date*: Fri, 21 Mar 2008 01:54:10 -0500 (EST)*Organization*: University of Bergen*References*: <frt574$sj8$1@smc.vnet.net> <47E23A75.7030909@gmail.com> <47E23CD8.3020207@gmail.com>

IMO the main problem is that Mathematica does not have a real associative array and/or set datastructure. What we really needed here was a set: With[{c = SetDatastructure[Intersection[a,b]]}, Select[a, # is an element of c &] ] But a real set is not available, so I had to resort to this "inverse" solution: instead of selecting those elements that are in c, remove those that are not in c. Associative arrays and sets can be emulated in several ways in Mathematica but none of them provide all features of the "associative array" of other languages: test for membership, add members one by one, add a batch of members, remove members one by one, get a list (or set) of keys, and get a list of values. One can use either a dispatch table, or associate downvalues with a symbol, but neither of these two approaches allows for doing everything I listed above in an easy way. The solution using downvalues would have been Timing[ unsortedIntersection4 = Module[{aa}, (aa[#] = 1) & /@ Intersection[a, b]; Select[a, ValueQ[aa[#]] &] ]; ] but this is not always as fast as the unsortedIntersection3 solution because elements are added one-by-one instead of as a batch. What do other MathGroup members think about this? Have you ever felt the need for an associative array (or set) data structure? Szabolcs