How to quickly check if two vectors have equal values

Question:

The number of elements reaches 100000 and I have to compare it with another vector of 100000, how can I do this with a very high performance 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++;
}
}
}
``````

You can try creating a hash array, for example

``````char hash[0x7FFFFFFF];
``````

if any positive integers are possible.

Initialize the vector,

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

Iterate over one of your 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;
}
``````

Then iterate over the second vector, incrementing `cont` if the hash is already filled,

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

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

The problem now is that too much RAM is used. 1GB RAM minimum, just for the hash vector…

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

Scroll to Top