2

コンテクスト

私はこのようなコードを持っています：

..
vector<int> values = ..., vector<vector<int>> buckets;
//reserve space for values and each buckets sub-vector
for (int i = 0; i < values.size(); i++) {
  buckets[values[i]].push_back(i);
}
...

したがって、同じ値を持つエントリのインデックスを持つ「バケット」を取得します。これらのバケットは、その後の処理で使用されます。

実際、私はネイティブの動的配列（int ** buckets;）を使用していますが、簡単にするために、上記のベクトルを使用しました。

充填する前に、各バケツのサイズを知っています。

ベクトルのサイズは約2,000,000,000です。

問題

上記のコードを見るとわかるように、ランダムな方法で「バケット」配列にアクセスします。したがって、実行時間が大幅に遅くなる一定のキャッシュミスがあります。はい、プロファイルレポートにそのようなミスがあります。

質問

そのようなコードの速度を向上させる方法はありますか？

Auxベクトルを作成し、最初に出現する値をそこに配置しようとしました。したがって、2番目のインデックスを見つけたときに、対応するバケットに2つのインデックスを配置できます。このアプローチではスピードアップはありませんでした。

ありがとうございました！

4

2 に答える 2

0

コードを遅くするのはキャッシュミスだと思い込んでいるのはなぜですか? プロフィールを作成しましたか、それとも頭に浮かんだことですか?

パフォーマンスの観点から、コードには非常に間違った点がいくつかあります。最初の最も明白な点は、ベクトル サイズを予約しないことです。何が起こっているかというと、ベクトルが最初は非常に小さい (たとえば、2 つの要素) ため、サイズを超えて追加するたびに、サイズが再度変更され、コンテンツが新しいメモリの場所にコピーされます。20 億のエントリがあると言っている場合、おそらく 30 回のサイズ変更を行っていることになります。

他の改善点を確認する前に、関数(または、最適な動作に応じて )を呼び出す必要があります。vector.reserve()vector.resize()

編集

真剣に？PSでベクトルを使用していないことにも言及しましたか? 実際のコードがどのように見え、どのように実行されるかをどのように推測すればよいでしょうか?

于 2012-05-13T08:56:10.723 に答える
0

特定の間隔fooで少なくとも可逆的かつ全射的ですか? 次に、その間隔を実行して、 (が の逆数の場合) で完全buckets[j]に埋めることができます。bar(j,k)barfook[0,...,MAX_BAR_J)j+1

ただしfoo、ハッシュ プロパティがある場合は、次のインデックスがどのインデックスに到達するかを予測できないため、可能性はほとんどありませiん。ですから、今のところチャンスはないと思います。

于 2012-05-13T09:09:00.400 に答える