関数プログラミング 珠玉のアルゴリズムデザイン 最小自由変数

雑記

配列に数字が入っていて配列に含まれない最小の自然数を求めるというのが第一章のお題
ソートはされてなくて非重複という条件付
最悪の場合O(n*(n/2+1))の方法ならアホでも思いつく
ソートすりゃクイックソートとかでO(n log n)の後に線形時間ならまだ分かる
いきなり線形時間ってどうすりゃいいんだべ？

のってた解法がこれ

minfree xs = minfrom 0 (length xs,xs)
minfrom a (n, xs) | n == 0     = a
                  | m == b - a = minfrom b (n - m, vs)
                  | otherwise  = minfrom a (m,     us)
                    where (us, vs) = partition (< b) xs
                          b        = a + 1 + n div 2
                          m        = length us

第一章でさっぱりわからん・・・
とりあえずlengthとpartitionという関数が使える前提で翻訳してみた

int minfree(int xs[])
{
	return(minfrom(0, length(xs), xs));
}

int minfrom(int a, int n, int xs[])
{
	if(n == 0) {return(a);}
	
	int b = a + 1 + n \ 2;
	
	// partitionはxsのうちbより小さいものをusへ、b以上のものをvsへ入れる
	int us[], vs[];
	us, vs = partition(b, xs);
	
	int m = length(us);
	
	if(m == b - a)
	{
		return(minfrom(b, n - m, vs));
	}
	else
	{
		return(minfrom(a, m, us));
	}
}

まだイマイチわからん・・・
変数が読みにくいので変数名をそれっぽくしてみた

int minfree(int xs[])
{
	return(minfrom(0, length(xs), xs));
}

int minfrom(int min, int max, int xs[])
{
	if(max == 0) {return(min);}
	
	int center = min + 1 + max \ 2;
	
	// partitionはxsのうちcenterより小さいものをleftへ、center以上のものをrigthへ入れる
	int left[], rigth[];
	left, rigth = partition(center, xs);
	
	int left_length = length(left);
	
	if(left_length == center - min)
	{
		return(minfrom(center, max - left_length, rigth));
	}
	else
	{
		return(minfrom(min, left_length, left));
	}
}

やっぱりどう考えてもpartition関数があるので線形時間にならない気がする
partition関数は一回xsを走査するやろ？じゃないとちっさいのとそれ以外に分けれずちっさいほうlength usが確定しない
Haskellにはなんか魔法でもあるんか？

要素数4の[3,2,1,0]を考える、答えは隙間がないので4になると思うが
partition (< 3) [3,2,1,0]となりus=[2,1,0]、vs=[3]となる、この時点で走査回数4回
ifのthen節に入り次のminfromで
partition (< 1) [3] となりus=[]、vs=[3]となる、この時点で総走査回数5回


要素数8の[7,6,5,4,3,2,1,0]を考える、答えは8
partition (< 5) [7,6,5,4,3,2,1,0]となりus=[4,3,2,1,0]、vs=[7,6,5]となる、この時点で走査回数8回
ifのthen節に入り次のminfromで
partition (< 7) [7,6,5] となりus=[6,5]、vs=[7]となる、この時点で総走査回数11回



どうしてもO(n)にならない
脳内デバッグしかしてないけどなんか間違ってるんだろうか？？？
まぁ普通にやるより早いよね、でもいいんだけど線形時間とうたっている以上、納得いかない