vector的sort/unique/erase性能与复制到unordered_set的性能比较

Question

我有一个函数，可以获取网格中一组点到特定距离内的所有邻居，其中涉及许多重复（我的邻居的邻居等于我自己）。

我已经尝试了几种不同的解决方案，但我不知道哪个更有效。下面是演示两个并行运行的解决方案的代码，一个使用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());

- Dave

Answer 1

这里的很多情况可能取决于输出集合的大小（这又取决于您采样了多远的邻居）。

如果它很小（不超过几十个项目），使用std :: vector和std :: find手动实现集合可能仍然相当有竞争力。问题在于它是一个O(N²)算法——每次插入一个项目，都必须搜索所有现有项目，因此每次插入都与已在集合中的项目数量成线性关系。因此，随着集合变得越来越大，插入项目的时间增长大约是平方级别的。

使用std :: set，每次插入只需要进行约log₂(N)次比较，而不是N次比较。这将将总体复杂度从O(N²)降低到O(N log N)。主要缺点是它（至少通常）是由单独分配的节点构建的树。这通常会降低其引用局部性——即，您插入的每个项目都将包含数据本身以及一些指针，并且遍历树意味着跟随指针。由于它们是单独分配的，当前在树中相邻的节点很可能在内存中不相邻，因此您将看到相当多的缓存未命中。底线：虽然随着项目数量的增加，其速度增长相对较慢，但涉及的常数相当大——对于少量项目，它将开始非常慢（通常比您手动实现的版本慢得多）。

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

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

也可以在纯线性序列中实现类似于集合的结构。这样既保留了集合仅存储唯一项的优点，又保留了向量本地引用的优点。其思想是保持大部分当前集合排序，以便您可以按对数时间复杂度进行搜索。然而，当您插入新项目时，只需将其放入单独的向量（或现有向量的未排序部分）中即可。当您进行新的插入时，还要对这些未排序的项目进行线性搜索。

当未排序的部分变得太大（对于“太大”的某种定义）时，您会对这些项目进行排序并将它们合并到主组中，然后重新开始相同的序列。如果您根据“log N”（其中N是已排序组中的项数）来定义“太大”，则可以保持整个数据结构的O（N log N）复杂度。当我试玩过它时，我发现未排序的部分可能比我预期的要大，直到它开始引起问题。

- Jerry Coffin

---

哇，非常详尽和有用的信息。思考的食粮很多，干杯！你最后提出的排序+未排序对的想法听起来非常有趣，我需要仔细思考一下。 - Dave

Answer 2

Unsorted set在插入时具有常数时间复杂度O(1)（平均情况下），因此删除操作的时间复杂度为O(n)，其中n是删除前的元素数量。

对大小为n的元素列表进行排序的时间复杂度为O(n log n)，遍历列表以删除重复项的时间复杂度为O(n)。 O(n log n) + O(n) = O(n log n)。

未排序集合（类似于性能上的哈希表）更好。

未排序集合的相关数据： http://en.cppreference.com/w/cpp/container/unordered_set

- asafrob