greenteaの日記: フラグの初期化を横着する。 5
書いている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 コメントで指摘を受けて、一部修正
初期化すら必要ない方法もあるかもよ (スコア:0)
i の初期値を 1 か 2 になるように切り替えれば、
flagsの使い方によるけど、初期化が不要になることも。
もっとも flags 確保直後の初期化は必要だけど
Re: (スコア:0)
そのための memset(flags, -1, size) ではなくて?
それはそうと flags[i] じゃなくて flags[j] の予感
たかがフラグにカウンタと同じサイズを奢るところが富豪的で痺れます
Re:初期化すら必要ない方法もあるかもよ (スコア:1)
>それはそうと flags[i] じゃなくて flags[j] の予感
指摘感謝。修正しました。
>たかがフラグにカウンタと同じサイズを奢るところが富豪的で痺れます
charにするとか、bit演算使うとかいう方法はあったと思いますが、
メモリは既に、他の所で呆れる位にたくさん使われていましたので、もはや気になりませんでした。
まさに富豪的なプログラムだと自分でも思っています。
速度面に関しましても、使用メモリを小さくすると早くなったとは思いますが、
オーダがO(N*M)の処理を消し去ることはできなかったでしょう。
1を聞いて0を知れ!
Re: (スコア:0)
豪快に見落としてた!
> たかがフラグにカウンタと同じサイズを奢るところが富豪的で痺れます
同意。でもきっとビット演算の時間ももったいなかったのよ。・・ん?
ビット演算 + 小さい領域を memset するのと、int とかのでかい領域の
フラグ配列を memset するのだと、きっと後者の方が時間かかるね。
Re: (スコア:0)
前者は N 回繰り返しですけどね
後者なら1回、しかしキャッシュが溢れる可能性もある諸刃の剣、
とかまあケースバイケースで良いんじゃないですか?
現実の動作を見もしないで空論を重ねても意味がありません。