Databases
StackOverflow2013
Postsdbo
POPerformance of vector sort/unique/erase vs. copy to unordered_set
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POPerformance of vector sort/unique/erase vs. copy to unordered_set
    primarykey
    data
    text
    <p>I have a function that gets all neighbours of a list of points in a grid out to a certain distance, which involves a lot of duplicates (my neighbour's neighbour == me again).</p> <p>I've been experimenting with a couple of different solutions, but I have no idea which is the more efficient. Below is some code demonstrating two solutions running side by side, one using std::vector sort-unique-erase, the other using std::copy into a std::unordered_set.</p> <p>I also tried another solution, which is to pass the vector containing the neighbours so far to the neighbour function, which will use std::find to ensure a neighbour doesn't already exist before adding it.</p> <p>So three solutions, but I can't quite wrap my head around which is gonna be faster. Any ideas anyone?</p> <p>Code snippet follows:</p> <pre><code>// Vector of all neighbours of all modified phi points, which may initially include duplicates. std::vector&lt;VecDi&gt; aneighs; // Hash function, mapping points to their norm distance. auto hasher = [&amp;] (const VecDi&amp; a) { return std::hash&lt;UINT&gt;()(a.squaredNorm() &gt;&gt; 2); }; // Unordered set for storing neighbours without duplication. std::unordered_set&lt;VecDi, UINT (*) (const VecDi&amp; a)&gt; sneighs(phi.dims().squaredNorm() &gt;&gt; 2, hasher); ... compute big long list of points including many duplicates ... // Insert neighbours into unordered_set to remove duplicates. std::copy(aneighs.begin(), aneighs.end(), std::inserter(sneighs, sneighs.end())); // De-dupe neighbours list. // TODO: is this method faster or slower than unordered_set? std::sort(aneighs.begin(), aneighs.end(), [&amp;] (const VecDi&amp; a, const VecDi&amp;b) { const UINT aidx = Grid&lt;VecDi, D&gt;::index(a, phi.dims(), phi.offset()); const UINT bidx = Grid&lt;VecDi, D&gt;::index(b, phi.dims(), phi.offset()); return aidx &lt; bidx; }); aneighs.erase(std::unique(aneighs.begin(), aneighs.end()), aneighs.end()); </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USDave
    1. USDave
    plurals
    1. This table or related slice is empty.
    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. POPerformance of vector sort/unique/erase vs. copy to unordered_set
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POPerformance of vector sort/unique/erase vs. copy to unordered_set
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POPerformance of vector sort/unique/erase vs. copy to unordered_set
      1. USAli
      1. VTFavorite
    1. This table or related slice is empty.
 

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