4

クラスに割り当てられた本を読んでいて、配列アクセスにはO（1）時間がかかると書かれています。これは非常に高速です（おそらく可能な限り高速です）が、これを数回参照する必要があるループがある場合、値を配列で検索するために一時変数を割り当てることに利点はありますか？または、一時変数を使用しても、O（1）を使用することはできますか？

この質問は言語に依存しないと思います。また、答えがイエスであるとしても、アドバンテージは小さいということを理解しています。私はただ興味があります。

4

5 に答える 5

6

O（1）は「瞬時」を意味するものではないことに注意してください。それは単に「せいぜい一定」を意味します。これは、これらの2番目が宇宙の原子数よりも大きい場合でも、 1と10 1000の両方が両方ともO（1）であることを意味します。

同じ配列要素に複数回繰り返しアクセスする場合、アクセスごとにO（1）時間がかかります。その配列要素をローカル変数に格納すると、O（1）ルックアップ時間も得られますが、定数は同じではない可能性があります。どちらか一方のオプションを選択する方が良いかもしれませんが、確実にプログラムをプロファイリングする必要があります。

実際には、この種のマイクロ最適化は、実行しているコードがプログラムの実行時間の大部分を占めていない限り、プログラム時間に測定可能な影響を与える可能性はほとんどありません。この変更が実際のコードに顕著な影響を与える例を見つけると、私はショックを受けます。

現代のアーキテクチャはおそらくこの変更を少し速くするかもしれませんが、劇的にはそうではありません。同じ配列要素に複数回アクセスし続けると、プロセッサはおそらく配列のその部分をキャッシュに保持し、ルックアップを非常に高速にします。また、優れた最適化コンパイラは、非ローカルコピーコードをローカルコピーコードに変換している場合があります。

お役に立てれば！

于 2013-02-07T06:39:54.603 に答える
4

私が理解しているなら、あなたは

for (int i=0; i<len; i++) {
   int temp = ar[i];
   foo += temp;
   bar -= temp;
}

より良いです：

for (int i=0; i<len; i++) {
   foo += ar[i];
   bar -= ar[i];
}

私はそれについて心配しません：

ループ本体のコードが同じ配列エントリにar[i]複数回アクセスする場合、中途半端なコンパイラ（ゼロ以外の最適化レベル）は、その値をレジスタに保持して、すばやく再利用できるようにします。言い換えると、上記のコードサンプルのいずれかが与えられた場合、コンパイラはおそらくまったく同じアセンブリを生成します。

これらのいずれかはまだO（1）であることに注意してください（一度に1つのものにアクセスします）。アルゴリズムのbig-O表記と命令レベルの最適化を混同しないでください。

編集

上記の2つのサンプルを含む2つの関数を含むサンプルプログラムをコンパイルしたところ、-O2gcc4.7.2でまったく同じマシンコードが生成されました。バイト単位。

于 2013-02-07T06:38:55.730 に答える
1

O（1）時間よりも優れたパフォーマンスを発揮できる唯一の方法は、そもそも何もする必要がないことです。それはO（0）時間になります。

またはより少ない単語で：いいえ。

于 2013-02-07T06:38:50.287 に答える
0

最新のCPUハードウェア（キャッシュラインなど）には、説明したようなことを実行するものがすでに組み込まれていますが、一時変数では実行できない方法で優れています。それよりもさらに優れているのは、ソースを変更する必要がないことです。

于 2013-02-07T06:44:50.690 に答える
0

いいえ。アレイへのアクセスは、輝きと愛から作られた魔法のようなゼロフットプリントのものではありません。Cの配列インデックスからアドレスを決定するアルゴリズムはここで見ることができます。mul最終的な1Dメモリアドレスに到達するには、追加の操作（主に、コストの観点からsおよび条件付き）が必要になるため、配列の次元が多いほど、アクセスが遅くなります。配列の次元が1つしかない場合でも、ベースアドレスのオフセットを計算する必要があります。これは単一のadd操作であるため、O（1）です。

于 2014-12-29T13:08:52.617 に答える