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