私は、グリッド内のポイントのリストのすべての隣人を特定の距離に取得する機能を持っています。これには、多くの重複が含まれます(私の隣人の隣人==私)。
いくつかの異なるソリューションを試してきましたが、どれがより効率的かわかりません。以下は、std::vector sort-unique-erase を使用するソリューションと std::unordered_set への std::copy を使用するソリューションの 2 つのソリューションを並べて実行するコードです。
また、これまでのネイバーを含むベクトルをネイバー関数に渡す別の解決策も試しました。ネイバー関数は std::find を使用して、追加する前にネイバーがまだ存在しないことを確認します。
3 つの解決策がありますが、どちらがより高速になるかについては、頭を悩ませることはできません。アイデアはありますか？
コード スニペットは次のとおりです。
// 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());