Более эффективное сравнение векторов

Question

Я пытаюсь сравнить 2 разных вектора, чтобы поймать дубликаты. один вектор - это 5 миллионов элементов из 10 чисел, а другой - 2,8 миллиона из 10 элементов. Моя операционная система 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());

Были бы полезны любые предложения относительно «лучшего» способа сделать это. Я знаю, что это некоторые большие векторы, имеющие более 2 с половиной миллионов элементов из 10 чисел.

Спасибо заранее

Idzireit

Все еще решаю проблему. Прямо сейчас я пытаюсь получить производную от решения Марка Рэнсома. Вот что я получил до сих пор:

#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.

Я пытался обернуть голову вокруг авто и уникальности и просто не могу привести примеры и мой (код? Методы?) В соответствие.

Idzireit

Answer 1

В вашем решении две три проблемы.

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());
}

Вы можете рассмотреть замену внутреннего std::vector на std::array, поскольку, как вы описываете, он имеет постоянный размер, и это уменьшит фрагментацию памяти (что должно обеспечить дополнительный импульс).

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

Answer 2

Вы выбрали алгоритм O (n²), что означает, что для больших наборов данных это займет очень много времени.Легко понять, почему вы думали, что оно зависло.

Если вы не заботитесь о порядке, вы можете отсортировать оба вектора, чтобы преобразовать это из задачи O (n²) в O (n log n).После того, как они отсортированы, вы проходите по каждому вектору одновременно, увеличивая индекс в зависимости от того, какой из них меньше другого.

Если вы не можете поместить весь набор данных в память сразу, вы можете даже использоватьэтот метод путем чтения из отсортированных файлов.

bool vec_less(const vector<int>& v1, const vector<int>& v2)
{
    for (int i = 0; i < v1.size() && i < v2.size(); i++)
    {
        if (v1[i] < v2[i])
            return true;
        if (v2[i] < v1[i])
            return false;
    }
    return v1.size() < v2.size();
}

std::sort(vector1.begin(), vector1.end(), vec_less);
std::sort(vector2.begin(), vector2.end(), vec_less);
vector<vector<int> >::iterator v1 = vector1.begin();
vector<vector<int> >::iterator v1out = v1;
vector<vector<int> >::iterator v2 = vector2.begin();

while (v1 != vector1.end())
{
    if (v2 == vector2.end() || vec_less(*v1, *v2))
    {
        if (v1out != v1)
            *v1out = *v1;
        ++v1;
        ++v1out;
    }
    else if (vec_less(*v2, *v1))
        ++v2;
    else // equal
    {
        ++v1;
        ++v2;
    }
}
vector1.resize(v1out - vector1.begin());