Databases
StackOverflow2013
Postsdbo
POEfficient set intersection of a collection of sets in C++
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POEfficient set intersection of a collection of sets in C++
    primarykey
    data
    text
    <p>I have a collection of <code>std::set</code>. I want to find the intersection of all the sets in this collection, in the fastest manner. The number of sets in the collection is typically very small (~5-10), and the number of elements in each set is is usually less than 1000, but can occasionally go upto around 10000. But I need to do these intersections tens of thousands of time, as fast as possible. I tried to benchmark a few methods as follows:</p> <ol> <li>In-place intersection in a <code>std::set</code> object which initially copies the first set. Then for subsequent sets, it iterates over all element of itself and the ith set of the collection, and removes items from itself as needed.</li> <li>Using <code>std::set_intersection</code> into a temporary <code>std::set</code>, swap contents to a current set, then again find intersection of the current set with the next set and insert into the temp set, and so on.</li> <li>Manually iterate over all the elements of all sets like in 1), but using a <code>vector</code> as the destination container instead of <code>std::set</code>.</li> <li>Same as in 4, but using a <code>std::list</code> instead of a <code>vector</code>, suspecting a <code>list</code> will provide faster deletions from the middle.</li> <li>Using hash sets (<code>std::unordered_set</code>) and checking for all items in all sets.</li> </ol> <p>As it turned out, using a <code>vector</code> is marginally faster when the number of elements in each set is small, and <code>list</code> is marginally faster for larger sets. In-place using <code>set</code> is a substantially slower than both, followed by <code>set_intersection</code> and hash sets. Is there a faster algorithm/datastructure/tricks to achieve this? I can post code snippets if required. Thanks! </p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. This table or related slice is empty.
    1. USParesh
    plurals
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POEfficient set intersection of a collection of sets in C++
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POEfficient set intersection of a collection of sets in C++
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThe question really depends on whether or not you are expected to find many common elements or not, as this alters the "best" structure that one can come up with. For example, a 6th method could be to simply use and `std::unordered_map` and count the number of occurrences of each elements. It's O(N) in the total number of elements. Then, you just pick the elements that have a total equal to the number of sets, O(M) in the number of distinct elements. No idea how well it would perform.
      singulars
      1. POEfficient set intersection of a collection of sets in C++
      1. USMatthieu M.
    2. CO@MatthieuM. I see. I will give this a try, though I suspect, it won't be faster than a `std::list` due to hashing and other overheads. Thanks!
      singulars
      1. POEfficient set intersection of a collection of sets in C++
      1. USParesh
    3. CO@MatthieuM. This method will give the resulting set in unsorted order. Luckily, I have two use cases, one which requires the result in sorted order, and one which does not. If this method is reasonably fast, I can use it atleast for the case where the intersection is not needed to be sorted.
      singulars
      1. POEfficient set intersection of a collection of sets in C++
      1. USParesh
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload