两个向量 a和b之间的区别

StackOverflow https://stackoverflow.com/questions/3135261

  •  01-10-2019
  •  | 
  •  

题

我有两个 vector<MyType*> 对象调用 A 和 B. 。 mytype课程有一个字段 ID 我想得到 MyType* 在 A 但不在 B. 。我正在研究图像分析应用程序，我希望找到一个快速/优化的解决方案。

有帮助吗？

解决方案

除非事先（通过您的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的有序容器，并使用用于严格的Weakordering模板参数的比较。我认为，如果您需要进行大量设定操作，这会更好。它有自己的开销（是一棵树），但是如果您确实发现这是一个效率问题，则可以实现快速的内存分配器以超快插入和删除元素（注意：仅当您配置并确定它是这样做的瓶颈）。

警告：进入某种复杂的领土。

您可以考虑另一种解决方案，如果适用，可能会非常快，您不必担心对数据进行分类。基本上，使任何共享同一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向量的地方。要获取不在B中的元素，我们首先调用traversal_counter（）。假设这是我们第一次称呼它，这将使我们的遍历值为1。

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

现在，通过A中的每个mytype*对象进行迭代。

当您溢出遍历柜台时会发生什么？在这种情况下，我们迭代存储在ID映射中的所有计数器，并将它们与遍历计数器本身一起将其设置为零。如果是32位未签名的INT，则只需要在大约40亿个遍历中发生一次。

这是关于最快的解决方案，您可以应用于给定的问题。它可以对未分类数据进行线性复杂性进行任何设置的操作（并且始终不仅在诸如哈希表之类的最佳场景中），但它确实引入了一些复杂性，因此只有在您真正需要的情况下才考虑它。

其他提示

分类两个向量（std::sort）根据ID，然后使用 std::set_difference. 。例如，您需要定义一个自定义比较器以传递到这两个算法，例如

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

首先看这个问题。您想要“ b中的所有内容”。这意味着您将不得不访问“所有内容”。您还必须访问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（或地图）是 大概 首先代表您的数据的最自然选择，即正确的设计产生了优化的实现。这并不总是会发生，但是当这样做时很好！

如果B先前主义者为A，则在填充A时，您可以在C向量中进行簿记。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top