4

我有一个函数可以将网格中点列表的所有邻居都移到一定距离，这涉及到很多重复项（我邻居的邻居 == 我又一次）。

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

2 回答 2

5

这里很大程度上可能取决于输出集的大小（这反过来又取决于您采样的邻居的距离）。

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

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

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

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

也可以在纯线性序列中实现类似集合的结构。这既保留了集合仅存储唯一项的优势，又保留了向量的局部性参考优势。这个想法是保持大多数当前集合排序，因此您可以在 log(N) 复杂度中搜索它。但是，当您插入一个新项目时，您只需将其放入单独的向量（或现有向量的未排序部分）中。当您进行新插入时，您还会对那些未排序的项目进行线性搜索。

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

于 2013-07-14T14:52:44.897 回答
1

未排序集的插入（平均）具有恒定的时间复杂度 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

于 2013-07-14T14:43:29.223 回答