0

(掛け算の計算時間について私に混乱がありました。774RRさんのご回答を御覧ください)

1000×1000ぐらいの大きな配列(画像など)があるとします。i行目の先頭のアドレスを得るためには、

  double lightness[1000][1000];
  // ...
  long i = 200;                        // ここでは i = 200 とする
  double *pLightness = lightness[i];   

とすれば良いですが、これを0から999iに対して繰り返すとなると、iが増えるにつれて、アドレスを得るのにかかる時間も増えるとおもいます。([]の仕様のせい)

  for (i = 0; i < 1000; i++) {
    *pLightness = lightness[i]; // i行目の先頭のアドレス
    // ...(アドレスを使った操作)
  }

i = 0から999まで順に行列のi行目の先頭のアドレスを得るのに、これより速い方法はありますか?
できれば、"pLightness += 1000する"よりもさらに速くてエレガントな方法があればいいなと思っているのですが…

質問の動機としては、ij列のアドレスが得られている際に、右隣の、ij+i列のアドレスを得るには、アドレスの入ったポインタをインクリメントすれば速いので、iについても同じことができないかと思ったことです。

  // (i, j) = (300, 0) から (300, 999) まで lightness[i][j] のアドレス pLightness を使った操作をするコード
  i = 300;
  pLightness = lightness[i]; // 300行目の先頭のアドレス
  for (long j = 0; j < 1000; j++, pLightness++) {
    // ...(アドレスを使った操作)
  }

うーん、基礎的な内容の質問なので、「参考書読め」とか「もうちょっと頭使え」という話なのかもしれないですが、どうかご容赦ください。

1

1 件の回答 1

3

これを0から999のiに対して繰り返すとなると、iが増えるにつれて、アドレスを得るのにかかる時間も増えるとおもいます。

オイラの思いつく限りのすべての処理系において lightness[i] の計算時間は O(1) つまり処理時間は i の値に関係なく一定です。一定にならないハードウエア・ソフトウエア実装が想像できないです。

&lightness[i][j] がすでにあるとき
&lightness[i][j+1] を求めるに要するコストと
&lightness[i+1][j] を求めるに要するコストとでは
確かに違いがありますが、アセンブラ命令にして数命令、誤差の範囲です。ポインタ値の計算ののちにアクセスを開始する際のキャッシュのヒットミスペナルティのほうが圧倒的に大っす。

4
  • ご回答ありがとうございます。lightness[i] がなにをしているかというと、&lightness[0]を取得し、それに i を加える(アドレスに整数をプラスしているので、ここではdoubleのサイズとiの積をプラスすることになる)ので、lightness[i]の時間はiに比例すると思ったのですが…私の"[]"の仕様についての勘違いでしょうか?
    – WaftRaft
    2020年7月3日 10:57
  • もちろんi = 0 から 999までやる程度だったら誤差程度ということでしょうが…O(1)?
    – WaftRaft
    2020年7月3日 11:01
  • 今時の CPU では定数積演算は定数クロックで行えます。n倍する処理にn回の繰り返しを行うことはありません。
    – 774RR
    2020年7月3日 11:02
  • つまり、小さな数どうしの積も、大きな数どうしの積も、同じ時間で計算できるということですね。おそらく知っているべき事柄なんでしょうが、私には勉強になりました。重ねてお礼申し上げます。
    – WaftRaft
    2020年7月3日 11:10

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。