1

最近、私は配列を反復処理する方法をすべて考えていて、どれが最も効率的か (そして最も効率的でないか) を考えていました。架空の問題と 5 つの解決策を書きました。

問題

要素数を持つint配列が与えられた場合、すべての要素に任意の数を割り当てる最も効率的な方法は何でしょうか?arrlen42

解決策 0: 明らかなこと

for (unsigned i = 0; i < len; ++i)
    arr[i] = 42;

解決策 1: 逆に明らかなこと

for (unsigned i = len - 1; i >= 0; --i)
    arr[i] = 42;

解決策 2: アドレスと反復子

for (unsigned i = 0; i < len; ++i)
{   *arr = 42;
    ++arr;
}

解決策 3: アドレスとイテレータを逆にする

for (unsigned i = len; i; --i)
{    *arr = 42;
     ++arr;
}

解決策 4: 狂気に対処する

int* end = arr + len;
for (; arr < end; ++arr)
    *arr = 42;

推測

ほとんどの場合、明らかな解決策が使用されますが、添字演算子が のように書かれた場合と同様に、乗算命令になるのではないかと思い*(arr + i * sizeof(int)) = 42ます。

逆のソリューションは、代わりに比較iすることで減算操作を軽減する方法を利用しようとします。このため、私はSolution 2よりもSolution 3を好みます。また、配列がキャッシュに格納されているため、前方にアクセスするように配列が最適化されていることを読みました。これは、ソリューション 1で問題を引き起こす可能性があります。0len

Solution 4がSolution 2よりも効率が悪い理由がわかりません。ソリューション 2はアドレスと反復子をインクリメントしますが、ソリューション 4はアドレスのみをインクリメントします。

結局、これらのソリューションのどれを好むかわかりません。答えは、コンパイラのターゲット アーキテクチャと最適化設定によっても異なると思います。

これらのうち、どちらが好きですか?

4

4 に答える 4

6

ISO 標準は、コードで物事を行うさまざまな方法の効率を義務付けていません (一部のコレクション アルゴリズムの特定の big-O タイプのものを除く)。それがどのように機能するかを義務付けているだけです。

配列のサイズが数十億の要素であるか、1 分間に何百万回も配列を設定したい場合を除き、通常、どちらの方法を使用してもほとんど違いはありません。

あなたが本当に知りたいのであれば (そして私はそれがほぼ確実に不必要であると今でも主張しています)、ターゲット環境でさまざまな方法をベンチマークする必要があります。推測しないで測定してください！

どちらを好むかというと、私の最初の傾向は、読みやすさを最適化することです。特定のパフォーマンスの問題がある場合にのみ、他の可能性を検討します。それは単に次のようなものです：

for (size_t idx = 0; idx < len; idx++)
    arr[idx] = 42;
于 2013-09-16T08:11:40.637 に答える
1

ここでパフォーマンスが問題になるとは思いません-それらは、たとえあったとしても（コンパイラーがそれらのほとんどに対して同一のアセンブリを生成すると想像できます）、マイクロ最適化はほとんど必要ありません。

最も読みやすいソリューションを使用してください。標準ライブラリはstd::fill、またはより複雑な割り当てを提供します

for(unsigned k = 0; k < len; ++k)
{
    // whatever
}

そのため、あなたのコードを見ている他の人にとって、あなたが何をしているのかは明らかです。C++11 では、次のこともできます

for(auto & elem : arr)
{
    // whatever
}

必要なくコードを難読化しようとしないでください。

于 2013-09-16T08:12:26.027 に答える