c++ - vector 排序/唯一/删除与复制到 unordered_set 的性能

Question

我有一个函数，可以将网格中点列表的所有邻居移出一定距离，这涉及很多重复项(我邻居的邻居再次 == 我)。

我一直在尝试几种不同的解决方案，但我不知道哪个更有效。下面是一些代码，演示了两个并行运行的解决方案，一个使用 std::vector sort-unique-erase，另一个使用 std::copy 到 std::unordered_set。

我还尝试了另一种解决方案，即将包含到目前为止的邻居的 vector 传递给邻居函数，该函数将使用 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());

Answer 1

这里的很大一部分可能取决于输出集的大小(反过来，这将取决于您采样的邻居的距离)。

如果它很小，(不超过几十个项目左右)您使用 std::vector 手动滚动的集合实现和 std::find可能会保持相当的竞争力。它的问题在于它是一个 O(N2) 算法——每次插入一个项目时，您必须搜索所有现有项目，因此每次插入都与集合中已有项目的数量成线性关系。因此，随着集合变大，其插入项目的时间大致呈二次方增长。

使用 std::set您每次插入只需进行大约 log2(N) 次比较而不是 N 次比较。这将整体复杂度从 O(N2) 降低到 O(N log N)。主要的缺点是它(至少在正常情况下)实现为由单独分配的节点组成的树。这通常会降低其引用的局部性——即，您插入的每个项目都将由数据本身加上一些指针组成，遍历树意味着跟随指针。由于它们是单独分配的，因此(当前)在树中相邻的节点在内存中很可能不会相邻，因此您会看到相当数量的缓存未命中。底线:虽然它的速度随着项目数量的增加而增长相当缓慢，但所涉及的常数相当大——对于少量项目，它开始时会相当慢(通常比你的手卷版本慢一点) )。

使用 vector/sort/unique 结合了前面每个的一些优点。将项目存储在一个 vector 中(每个项目没有额外的指针)通常会导致更好的缓存使用——相邻索引处的项目也位于相邻的内存位置，所以当你插入一个新项目时，新项目的位置很可能会已经在缓存中。主要的缺点是，如果您正在处理一个非常大的集合，这可能会使用更多的内存。当您插入每个项目时，集合消除重复项(即，只有在与集合中已有的任何项目不同时才会插入项目)，这将插入所有项目，然后最后删除所有重复项。鉴于当前的内存可用性和我猜你可能正在访问的邻居数量，我怀疑这在实践中是一个主要缺点，但在错误的情况下，它可能会导致一个严重的问题——几乎所有虚拟内存的使用几乎肯定会使其成为净亏损。

从复杂性的角度来看最后一个，它将变成 O(N log N)，有点像集合。不同之处在于，对于该集合，它实际上更像是 O(N log M)，其中 N 是邻居的总数，而 M 是唯一邻居的数量。对于 vector ，它实际上是 O(N log N)，其中 N 是(再次)邻居的总数。因此，如果重复的数量非常大，则集合可能具有显着的算法优势。

也可以在纯线性序列中实现类似集合的结构。这保留了集合仅存储唯一项的优势，也保留了 vector 的引用位置优势。这个想法是保持当前集合的大部分排序，所以你可以在 log(N) 复杂度中搜索它。但是，当您插入一个新项目时，您只需将其放入单独的 vector (或现有 vector 的未排序部分)中。当你做一个新的插入时，你也会对那些未排序的项目进行线性搜索。

当未排序的部分变得太大(对于“太大”的某些定义)时，您对这些项目进行排序并将它们合并到主组中，然后再次开始相同的序列。如果根据“log N”(其中 N 是已排序组中的项目数)定义“太大”，则可以将整个数据结构的复杂度保留为 O(N log N)。当我使用它时，我发现未排序的部分在它开始引起问题之前可能比我预期的要大。