3

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

4

4 回答 4

2

无序方法通常具有二次复杂度，除非数据预先排序（通过您的 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) );

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

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

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

这将需要创建一个 ID 到计数器的映射，并且需要在每次基于其 ID 创建 MyType 对象时从映射中获取计数器。由于您有具有重复 ID 的 MyType 对象，因此您不必像创建 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。

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

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

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

于 2010-06-28T19:06:45.090 回答
2

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

struct comp
{
    bool operator()(MyType * lhs, MyType * rhs) const
    {
        return lhs->id < rhs->id;
    }
};
于 2010-06-28T18:56:58.063 回答
1

首先看问题。您想要“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（或 map）可能是首先表示数据的最自然选择，即正确的设计会产生优化的实现。这并不总是发生，但发生时很好！

于 2010-06-28T20:29:18.123 回答
0

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

于 2010-06-28T23:23:13.053 回答