More efficient vector comparison

user_7328332 0
Viewed 331

I am trying to compare 2 different vectors to catch any duplicates. one vector is 5 million elements of 10 numbers and the other is 2.8 million of 10 elements. My operating system is ubuntu 18.04 and I am using QtCreator. I am getting a hangup when I try to compare these large vectors. here is what I have tried:

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

when I try and run this and debug Qt hangs. I am also wondering if I need to change the erase to look something like :

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

Any suggestions as to a "Better" way of doing this would be helpful. I know these are some big vectors having more then 2 and a half million elements of 10 numbers.

Thx in advance

Idzireit

Still tackling the problem. Right now I am trying a derivative of Mark Ransom's solution. Here is what I got so far:

#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;
}

I only needed to sort 1 of the vectors. The other was sorted as it was made. The problem I am having with the appended code is now it is not finding the duplicates. It does go through each of the vectors once but for some reason it is not finding the duplicates. I know there are some because a previous attempt and sorting them out found them though I was running into a serious sigseg fault.

I have been trying to wrap my head around auto and unique and just cant quite get the examples and my (code? methods?) to coincide.

Idzireit

vector c++
2 Answers

There are two three problems with your solution.

  1. Your code has undefined behavior. When you delete item iterator becomes invalid.

  2. Your code has large complexity o(n^2) o(n^3).

  3. Removing item from middle of vector has linear complexity, so for large vectors it should be avoided. This is why I've corrected point 2.

Code below has o(n) time complexity, and use of STL algorithms is usually best choice:

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

You can consider replacing internal std::vector with std::array, since as you describe it has constant size and this will reduce memory fragmentation (what should provide extra boost).

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

The algorithm you've selected is O(n²), which means for large data sets it will take a very long time. It's easy to see why you thought it was hung.

If you don't care about ordering, you can sort both vectors to convert this from an O(n²) problem to O(n log n). Once they're sorted you walk through each vector simultaneously, incrementing an index depending on which one is less than the other.

If you can't fit the entire data set into memory at once, you can even use this method by reading from sorted files.

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());
Mark_Ransom_59870
Related