我有一个函数,可以获取网格中一组点到特定距离内的所有邻居,其中涉及许多重复(我的邻居的邻居等于我自己)。
我已经尝试了几种不同的解决方案,但我不知道哪个更有效。下面是演示两个并行运行的解决方案的代码,一个使用std::vector sort-unique-erase,另一个使用std::copy进入std::unordered_set。
我还尝试了另一种解决方案,即将到目前为止包含邻居的向量传递给邻居函数,该函数将使用std::find确保邻居不存在才添加它。
所以有三种解决方案,但我无法完全理解哪个会更快。有任何想法吗?
代码片段如下:
我已经尝试了几种不同的解决方案,但我不知道哪个更有效。下面是演示两个并行运行的解决方案的代码,一个使用std::vector sort-unique-erase,另一个使用std::copy进入std::unordered_set。
我还尝试了另一种解决方案,即将到目前为止包含邻居的向量传递给邻居函数,该函数将使用std::find确保邻居不存在才添加它。
所以有三种解决方案,但我无法完全理解哪个会更快。有任何想法吗?
代码片段如下:
// Vector of all neighbours of all modified phi points, which may initially include duplicates.
std::vector<VecDi> aneighs;
// Hash function, mapping points to their norm distance.
auto hasher = [&] (const VecDi& a) {
return std::hash<UINT>()(a.squaredNorm() >> 2);
};
// Unordered set for storing neighbours without duplication.
std::unordered_set<VecDi, UINT (*) (const VecDi& a)> sneighs(phi.dims().squaredNorm() >> 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(), [&] (const VecDi& a, const VecDi&b) {
const UINT aidx = Grid<VecDi, D>::index(a, phi.dims(), phi.offset());
const UINT bidx = Grid<VecDi, D>::index(b, phi.dims(), phi.offset());
return aidx < bidx;
});
aneighs.erase(std::unique(aneighs.begin(), aneighs.end()), aneighs.end());