パスワードを忘れた? アカウント作成
176969 journal

greenteaの日記: フラグの初期化を横着する。 5

日記 by greentea

書いているCプログラムで、フラグの配列をmemsetで初期化する部分が重くて悩んでいたとき、友人から大変素晴らしいアドバイスをもらった。
何を当たり前のことを、と思う人も多いかもしれないが、個人的には素晴らしいと思ったので日記に書く。
(なので、誰でも思いつく、当たり前、といった内容のコメントは不要である)

intで表現できる範囲を越えない範囲の、巨大な数字N, Mがあった。
N回、処理をするのだが、各回での処理で、要素数Mのフラグ配列(bool型。Cなので,charかintでやってた)を所持する必要があった。
また、各回ごとに、フラグ配列は0に初期化する必要があった。

int i;
int flags[M];
 
for(i=0;i<N;i++){
    memset(flags, 0, sizeof(int) * M);
    do_something(i, flags);
}

ここで、do_somethingはO(1)であったのだが、memsetがO(M)であるので、
プログラム全体としてはO(N)ではなくO(N*M)となってしまい、速度低下の原因となっていた。

これを、こう書き換える。

int i;
int flags[M];
 
memset(flags, -1, sizeof(int) * M);
for(i=0;i<N;i++){
    do_something(i, flags);
}

そして、do_something内にある

flags[j] = 1

flags[j] = i

に,

if(flags[j])

if(flags[j] == i)

に,書き換える。
そうすると、flagsの初期化は1回で済む。

09.12.22 11:26 コメントで指摘を受けて、一部修正

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • by Anonymous Coward on 2009年12月22日 9時18分 (#1692530)
    i=0 のとき気をつけてね

    i の初期値を 1 か 2 になるように切り替えれば、
    flagsの使い方によるけど、初期化が不要になることも。
    もっとも flags 確保直後の初期化は必要だけど
    • by Anonymous Coward
      > i=0 のとき
      そのための memset(flags, -1, size) ではなくて?

      それはそうと flags[i] じゃなくて flags[j] の予感
      たかがフラグにカウンタと同じサイズを奢るところが富豪的で痺れます
      • >それはそうと flags[i] じゃなくて flags[j] の予感

        指摘感謝。修正しました。

        >たかがフラグにカウンタと同じサイズを奢るところが富豪的で痺れます

        charにするとか、bit演算使うとかいう方法はあったと思いますが、
        メモリは既に、他の所で呆れる位にたくさん使われていましたので、もはや気になりませんでした。
        まさに富豪的なプログラムだと自分でも思っています。

        速度面に関しましても、使用メモリを小さくすると早くなったとは思いますが、
        オーダがO(N*M)の処理を消し去ることはできなかったでしょう。

        --
        1を聞いて0を知れ!
        親コメント
      • by Anonymous Coward
        > そのための memset(flags, -1, size) ではなくて?
        豪快に見落としてた!

        > たかがフラグにカウンタと同じサイズを奢るところが富豪的で痺れます
        同意。でもきっとビット演算の時間ももったいなかったのよ。・・ん?
        ビット演算 + 小さい領域を memset するのと、int とかのでかい領域の
        フラグ配列を memset するのだと、きっと後者の方が時間かかるね。
        • by Anonymous Coward

          前者は N 回繰り返しですけどね
          後者なら1回、しかしキャッシュが溢れる可能性もある諸刃の剣、
          とかまあケースバイケースで良いんじゃないですか?
          現実の動作を見もしないで空論を重ねても意味がありません。

typodupeerror

日々是ハック也 -- あるハードコアバイナリアン

読み込み中...