Почему мой код для set_intersection медленнее, чем стандартный?

У меня есть две функции ниже. Я выполняю каждый примерно 200K раз со случайными отсортированными векторами (каждая функция получает те же два вектора, но векторы меняются между прогонами). Я немного сбит с толку, потому что мой код выполняется в общей сложности около 500 мс для всех 200К итераций, тогда как вызов функции STD выполняется за 440 мс. Куда идет ~ 60 мс? Что STD делает (или не делает), что я сделал по-другому?

Я использую Visual Studio 10 на ядре i5.

int getAndIntersectMine(std::vector<int>& resultContainer)
{
std::vector<int> const& vector0 = getSomeVector();
std::vector<int> const& vector1 = getAnotherVector();

const int length0 = vector0.size();
const int length1 = vector1.size();

const int* ptr0 = &vector0[0];
const int* ptr1 = &vector1[0];

int i0 = 0;
int i1 = 0;
int numels = 0;

while(i0 < length0 && i1 < length1)
{
if(ptr0[i0] == ptr1 [i1]) {
resultContainer[numels++] = ptr0[i0];
i0++;
i1++;
}
else if (ptr0[i0] > ptr1[i1])
{
i1++;
}
else
{
i0++;
}
}

return numels;
}int getAndIntersectStds(std::vector<int>& resultContainer)
{
std::vector<int> const& vector0 = getSomeVector();
std::vector<int> const& vector1 = getAnotherVector();

std::vector<int>::iterator last =
std::set_intersection(
vector0.begin(),
vector0.end(),
vector1.begin(),
vector1.end(),
resultContainer.begin());

return last - resultContainer.begin();
}

1

Решение

Я думаю, проблема в том, что вы используете подписку вместо итераторов.

в то время как итерация стандартного алгоритма делает (в указателе уравнения)

int * beg = &v[0];
int * end = &v[0] + v.size();
while(beg != end)
{
...
++beg;
}

Ваш более обширный арифметический

int * beg = &v[0];
int i = 0, s = v.size();
while(i != s)
{
//use beg[i], which is *(beg + i)
...
++i;
}

А также пост приращения … но я думаю, что это оптимизировано

1

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]