两个向量之间的差异甲和乙

Question

我有两个名为 A 和 B 的 vector 对象。 MyType 类有一个字段 ID，我想获取位于 A 中但不在 B 中的 MyType* >。我正在开发图像分析应用程序，我希望找到一个快速/优化的解决方案。

Answer 1

无序方法通常具有二次复杂度，除非数据事先排序（通过 ID 字段），在这种情况下它将是线性的，并且不需要通过 B 重复搜索。

struct CompareId
{
    bool operator()(const MyType* a, const MyType* b) const
    {
        return a>ID < b->ID;
    }
};
...
sort(A.begin(), A.end(), CompareId() );
sort(B.begin(), B.end(), CompareId() );

vector<MyType*> C;
set_difference(A.begin(), A.end(), B.begin(), B.end(), back_inserter(C) );

另一种解决方案是使用像 std::set 这样的有序容器将 CompareId 用于 StrictWeakOrdering 模板参数。我认为如果您需要应用大量集合运算，这会更好。这有其自身的开销（作为一棵树），但如果您确实发现这是一个效率问题，您可以实现一个快速内存分配器来超快地插入和删除元素（注意：只有在您分析并确定这是瓶颈）。

警告：进入有些复杂的领域。

您可以考虑另一种解决方案，如果适用，它可能会非常快，而且您永远不必担心数据排序。基本上，使任何共享相同 ID 的 MyType 对象组存储共享计数器（例如：指向 unsigned int 的指针）。

这将需要创建一个 ID 到计数器的映射，并且需要在每次基于其 ID 创建 MyType 对象时从映射中获取计数器。由于您的 MyType 对象具有重复的 ID，因此您不必像创建 MyType 对象那样频繁地插入到映射中（大多数对象可能只是获取现有计数器）。

除此之外，还有一个全局“遍历”计数器，每当获取时该计数器就会递增。

static unsigned int counter = 0;
unsigned int traversal_counter()
{
    // make this atomic for multithreaded applications and
    // needs to be modified to set all existing ID-associated
    // counters to 0 on overflow (see below)
    return ++counter;
}

现在让我们回到存储 MyType* 的 A 和 B 向量的位置。为了获取 A 中不在 B 中的元素，我们首先调用 traversal_counter()。假设这是我们第一次调用它，则遍历值为 1。

现在迭代 B 中的每个 MyType* 对象，并将每个对象的共享计数器设置为从 0 到遍历值 1。

现在迭代每个 MyType * A 中的对象。计数器值与当前遍历值（1）不匹配的元素是 A 中不包含在 B 中的元素。

当遍历计数器溢出时会发生什么情况？在这种情况下，我们迭代存储在 ID 映射中的所有计数器，并将它们与遍历计数器本身一起设置回零。如果它是 32 位无符号整数，则只需在大约 40 亿次遍历中发生一次。

这是您可以应用于给定问题的最快解决方案。它可以对未排序的数据以线性复杂度执行任何集合操作（​​并且总是，不仅仅是在像哈希表这样的最佳情况下），但它确实引入了一些复杂性，因此只有在您确实需要时才考虑它。

Answer 2

对两个向量进行排序 (std::sort)到 ID，然后使用 std::set_difference。例如，您需要定义一个自定义比较器来传递给这两种算法

struct comp
{
    bool operator()(MyType * lhs, MyType * rhs) const
    {
        return lhs->id < rhs->id;
    }
};

Answer 3

首先看问题。你想要“A中的一切而不是B中的一切”。这意味着您将必须访问“A 中的所有内容”。您还必须访问 B 中的所有内容才能了解 B 中存在和不存在的内容。因此，这表明应该有一个 O(n) + O(m) 解决方案，或者随意消除 n 和 m 之间的差异，O(2n)。

让我们考虑一下 std::set_difference 方法。每次排序的时间复杂度为O(n log n)，set_difference 的时间复杂度为O(n)。因此，sort-sort-set_difference 方法的复杂度是O(n + 2n log n)。我们称之为O(4n)。

另一种方法是首先将 B 的元素放入集合（或映射）中。遍历 B 来创建集合的时间为 O(n) 加上每个元素的插入 O(log n)，然后遍历 AO(n)，并查找A (log n) 的每个元素的总和：O(2n log n)。我们称之为O(3n)，这稍微好一些。

最后，使用 unordered_set （或 unordered_map），并假设我们得到 O(1) 插入和 O(1) 查找的平均情况，我们有一种方法 <代码>O(2n)。啊哈！

这里真正的胜利是，unordered_set（或映射）可能是表示数据的最自然的选择，即，正确的设计会产生优化的实现。这种情况并不总是发生，但当它发生时那就太好了！

Answer 4

如果 B 先于 A 存在，那么在填充 A 时，您可以在 C 向量中进行记账。