Mathematica 9 is now available
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: [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


  • Prev by Date: Re: Bug: symbol recreates itself suddenly
  • Next by Date: Re: finding positions of elements in a list
  • 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