アルゴリズム変更 - ここにタイトルを入力|

http://d.hatena.ne.jp/goth_wrist_cut/20071214/1197604488
これ↑
今更ながら題意に即してない気がして訂正。
具体的には初期化の部分。

初期密度を0.3,0.5,0.7でそれぞれ試せ、という問題だったのだが、この方法だと「おおよそ」になってしまう。
つまりは乱数任せ。
それはどうなんだろう。やはり0.5と言われたらぴったり0.5にすべきなのだろう。
と、いうことでこうなった

/* 初期化 */
int i;
for( i = 0; i < length * density; i++ ) {
	*nth( primaryBuf, i, length ) = TRUE;
}
for( i = 0; i < length; i++ ) {
	/* [0,length)の乱数を得て、対象とスワップする */
	int r = (double)length * (double)rand() / ( RAND_MAX + 1.0 );
	BOOL s;
	s = *nth( primaryBuf, i, length );
	*nth( primaryBuf, i, length ) = *nth( primaryBuf, r, length );
	*nth( primaryBuf, r, length ) = s;
}

最初に必要個数だけTRUEにして、それをシャッフルする、という至極単純な仕掛け。
callocしてるので0代入(というかFLASE代入。あくまでBOOL!)はいらないはず。

なんでわざわざスワップするのか?
もっと単純に、適当な数字取ってきて、そこが0だったら1代入してカウントアップ、そうでなかったら無視、をループさせて指定個数まで持っていく方法もあるのだが...。

int count = 0;
while( count < length * density ) {
	int rnd = (double)length * (double)rand() / (RAND_MAX + 1.0);
	if( !*nth( primaryBuf, rnd, length ) ) {
		*nth( primaryBuf, rnd, length ) = TRUE;
		count++;
	}
}

↑つまりこんな感じ(コンパイラに通して無いので間違いあったらすまぬ。
いかんせん有限時間で終わる証明ができんのだ。
つまり乱数相手なもんでいつ終わるか分からないと。
density(=密度)が低い場合にはそんなに問題にならないのだが、densityが高くなってくると、すでに1(=TRUE)が代入されてて無視しなくちゃいけないパターンが増えてくるのだ。
そうするとcountの増え方は頭打ちになっていっていつ終わるか...ということになる。

というか実際lengthにRAND_MAX以上の値をいれられてdensityを1にすると終わらないという。
もともと[0..RAND_MAX]までの「整数」が得られるわけで、それをRAND_MAX以上に引き伸ばそうとすると絶対出てこない数字が発生してしまうのだ。
なのでそこの部分はずっと0のまま、ひたすら無限ループ、となってしまう。

まぁ、それ以前にgccでコンパイルしちゃうとそんなバカでかいメモリをAllocできないというね。うん。
gccのRAND_MAXって2147483647なのね。
てっきり32767ってANCIかなんかで決められてるのかと思ってた。

最初に必要個数いれてシャッフルする方法(=前者のソースコード)ならlength*density+lengthで、最大でもlength*2回のループで確実に終わることが保証されてる。
ついでに言えば二個目のループですべての箇所に触れてやってるし、一応全体が均等にシャッフルされるはずだ。

前回の課題で -- 減点こそはされなかったものの -- 範囲の違い(世に言う閉区間"[a,b]"と開区間"(a,b)"の違い)をSHITEKIされたので今回はコメントにもちゃんと"[0,length)"などと書いて意識してることをアピール(w
配列はゼロオリジンなのでlengthは含めちゃあかんと。

あとしょうもないバグフィックスをいくつか。

getopt_longの引数は"r:d:s:l:g:ho"ぢゃなくて"r:d:s:l:g:ho:"
ショートオプションにしたらセグ落ち(「セグメンテーションフォールトで落ちるの略」。方言。)して少し焦った。

perrorの後にexitし忘れ。
allocateできないのに先進むなつーの。

assert使うのはどうよ?
→ちゃんとエラーメッセージ吐いてexit

こんな感じ。