2

以下の2つの機能があります。ランダムにソートされたベクトルを使用して、それぞれを約200K回実行します（各関数は同じ2つのベクトルを取得しますが、ベクトルは実行ごとに異なります）。私のコードは200Kの反復すべてで合計約500ミリ秒で実行されるのに対し、STD関数呼び出しは440ミリ秒で実行されるため、少し混乱しています。〜60msはどこに行くのですか？私が違ったやり方で行ったSTDは何をしている（またはしていない）のですか？

コアi5でVisualStudio10を使用しています。

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

1 に答える 1

1

問題は、イテレータの代わりにサブスクリプションを使用していることだと思います。

stdアルゴリズムを反復している間（ポインタ式で）

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

あなたはよりarithmeic-extensiveです

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

また、ポストインクリメント...しかし、私はそれが最適化されていると思います

于 2013-03-15T13:30:21.953 に答える