How to check if two vectors have equal values quickly

Asked

Viewed 1,364 times

3

The element number reaches 100000 and I have to compare with another vector of 100000, as I can do it with a very high unemployment gain

How I’m comparing the vectors

for(i = 0; i < teste; i++)
{
    for(j = 0; j < teste; j++)
    {
        if(indice[i] == aux[j])
        {
            cont++;
        }
    }
}
c array

  • For your scenario this recursive mode is recommended, since you need to check each value; if you only want to compare if the vectors are equal, you can use strcmp.

  • Hello Mauro, the vector are numbers, so do not go to use strcmp, you could give me an example of what would be this recursive mode ? , thanks in advance

  • Has equal values of which form ? has the same numbers in the same positions ? Or the same numbers even in different positions ?

1 answer

2


You can try to create a vector hash, for example

char hash[0x7FFFFFFF];

if any positive integers are possible.

Initialize the vector,

for (int i = 0; i < 0x7FFFFFFF; ++i)
{
    hash[i] = 0;
}

Itere one of its original vectors and use the hash to know that that number exists in this vector:

for (int i = 0; i < teste; ++i)
{
    hash[indice[i]] = 1;
}

Hence the second vector, increasing cont if the hash is already completed,

for (int i = 0; i < teste; ++i)
{
    if (hash[aux[i]])
    {
        ++cont;
    }
}

That way complexity becomes O(n), instead of O(n 2), which was your case.

The problem now is that a lot of RAM is used. 1 GB of RAM, at least, only for the vector hash...

So there is a counterpart between algorithmic complexity and spatial complexity, which must always be taken into account.

  • I think it’s cool to quote search/sort methods too! They may be useful for learning (for example, this algorithm used in the question would be a "Bubble Sort".. introduce a "Shell Sort" or "Selection Sort" for Rafael to study well!)

  • 2

    Thank you Martillo worked

  • I’ll search Cleber, thanks for the tip

Browser other questions tagged c array

You are not signed in. Login or sign up in order to post.