时间戳

首页 > 解决方案 > 更高效的向量比较

c++ - 更高效的向量比较

问题描述

我正在尝试比较 2 个不同的向量以捕获任何重复项。一个向量是 10 个数字的 500 万个元素，另一个是 10 个元素的 280 万个。我的操作系统是 ubuntu 18.04，我正在使用 QtCreator。当我尝试比较这些大向量时，我陷入了困境。这是我尝试过的：

vector<vector<int> >::iterator v1;
vector<vector<int> >::iterator v2;

for(v1 = vector1.begin(); v1 != vector1.end(); v1++)
    {
        for(v2 = vector2.begin(); v2 != vector2.end(); v2++)
        {
            if(*v1 == *v2)
            {
                vector1.erase(v1);
            }
        }
    }

当我尝试运行它并调试 Qt 时会挂起。我还想知道是否需要将擦除更改为：

vector1.erase(v1.begin(), v1.end());

任何有关“更好”的方法的建议都会有所帮助。我知道这些是一些大向量，有超过 250 万个 10 个数字的元素。

提前谢谢

伊兹赖特

仍在解决问题。现在我正在尝试 Mark Ransom 解决方案的衍生产品。这是我到目前为止得到的：

#include "includes.h"

bool vec_less(vector<int> &v1, vector<int> &v2)
{

    for(int i = 0; i < 10; i++)
    {
        if(v1[i] == v2[i])
        {
            i++;
        }
        if(v1[i] < v2[i])
            return true;
        else
            return false;
    }
    return v1.size() <v2.size();
}

void dupfilter(vector<vector<int> > &aaperms, vector<vector<int> > &perms)
{
    vector<vector<int> >::iterator v1 = aaperms.begin();
    vector<vector<int> >::iterator v2 = perms.begin();

    while(v1 != aaperms.end() && v2 != perms.end())
    {

        if(*v1 == *v2)
        {
            aaperms.erase(v1);
            ++v1;
            ++v2;
        }

        if(vec_less(*v1, *v2) == true)
            ++v1;
        else
            ++v2;
    }

    return;
}

我只需要对其中的 1 个向量进行排序。另一个在制作时进行了分类。我在附加代码中遇到的问题是现在找不到重复项。它确实遍历了每个向量一次，但由于某种原因它没有找到重复项。我知道有一些是因为之前的尝试和整理发现它们虽然我遇到了严重的 sigseg 错误。

我一直试图将我的头脑围绕在 auto 和 unique 上，只是不能完全让示例和我的（代码？方法？）重合。

伊兹赖特

标签： c++vector

解决方案

有二您的解决方案存在三个问题。

  1. 您的代码具有未定义的行为。当您删除项目迭代器变得无效。

  2. 您的代码具有很大的复杂性o(n^2) o(n^3).

  3. 从向量中间删除项目具有线性复杂性，因此对于大向量应避免。这就是我纠正观点的原因2。

下面的代码有o(n)时间复杂度，使用 STL 算法通常是最好的选择：

using Vec = std::vector<std::vector<int>>;

void removeItems(Vec& from, const Vec& itemsToRemove)
{
    const std::unordered_set<Vec::value_type> items {
       itemsToRemove.begin(),
       itemsToRemove.end()
    };

    auto it = 
    std::remove_if(from.begin(), from.end(),
                   [&items](const auto &x){
                       return items.count(x) != 0;
                   });
    from.erase(it, from.end());
}

您可以考虑将 internal 替换std::vector为std::array，因为正如您所描述的，它具有恒定的大小，这将减少内存碎片（应该提供额外的提升）。

using Vec = std::vector<std::array<int, 5>>;

推荐阅读