1

特にこれを読んだ後、私はちょっと驚いています。

私が使う

template <class T>
int GetPosition(vector<T> mVec, T element)
{
    return find(mVec.begin(), mVec.end(), element) - mVec.begin();
}

と

template <class T>
int GetPosition(map<T, int> mMap, T element)
{
    return mMap.find(element)->second;
}

ベクトルリスト内の特定の要素のインデックスを取得するためのテンプレート関数として。

要素は、インデックスを取得したいオブジェクトへの一意のポインターです。

次に、このテンプレートを for ループで使用します

for(int i = 0; i < myCount; i++)
{
  index = GetPosition(myVector, elements[i]) //or GetPosition(myMap, elements[i])
}

私が収集したすべての情報は、マップを使用することを提案しましたが、マップの実装は数桁遅くなりました.57ミリ秒のベクトルバリアントと比較して、マップを使用した場合は70000ミリ秒です。

ここで何かがひどく壊れていますが、何が原因かわかりません。あなたは？

開発プラットフォームは Windows XP 上の MS VS 2008 Standard sp1 です。

4

3 に答える 3

3

コードがここに書かれているように、ベクトルとマップの両方を値で渡していることに注意してください。つまり、呼び出しごとにそれぞれの新しいコピーを再構築しています。それは明らかに検索の時間を圧倒しています。

試す：

template <class T> 
int GetPosition(const map<T, int> &mMap, T element)
于 2010-07-07T13:47:09.917 に答える
3

それらを値で渡しているため、実行しているすべての呼び出しでvectorandに対処しています。mapこれにより、結果がほとんど無意味になると私は考えていました。

それらを参照または const 参照として渡し、テストを再度実行してください。

template <class T>
int GetPosition(const vector<T>& mVec, T element)
{
    return find(mVec.begin(), mVec.end(), element) - mVec.begin();
}

template <class T>
int GetPosition(const map<T, int>& mMap, T element)
{
    return mMap.find(element)->second;
}
于 2010-07-07T13:47:53.230 に答える
1

他の回答が言及しているように、参照を使用してコピーを回避する以外に、アルゴリズムの複雑さにも違いがあります。

サイズ n の (ソートされていない) ベクトルでのルックアップは O(n) 時間の複雑さを持ちますが、マップ上の同じ操作は O(log n) 時間の複雑さを持ちます。

簡単に説明すると、ベクトル内のオブジェクトの検索には K1*n の時間がかかり、マップには K2*log(n) の時間がかかることを意味します。ここで、K1 と K2 はベクトルとマップの実装に依存する定数です。

実際にはどちらが速いかは、コンテナーのサイズと定数によって異なります (K1 の方が速いと言っても過言ではありません。

キャッシュ コヒーレンスなどもここで機能します。コンテナーが小さい場合、すべてがベクターのキャッシュにありますが、マップのキャッシュにはありません。（キャッシュを使用すると、定数も実際には一定ではありませんが、それは別の話です...）

于 2010-07-07T23:13:50.217 に答える