No Such Blog or Diary

比較の仕方がデータによらないソートである Bitonic Sort を Haskell で書いてみた．要素数 2^n 限定．だけ．

import System.Random
randInt :: IO (Int)
randInt = getStdRandom (randomR (0,1000))
randInts n = randInts' n []
 where
 randInts' n xs = 
  if n == 0 then return xs
  else
   randInt >>= (\x -> randInts' (n-1) (x:xs))
  
bimerge xs ys 1 dir = unzip (zipWith (\x y -> if (x < y) == dir then (x,y) else (y,x)) xs ys)
bimerge xs ys n dir = (xxs++xys, yxs++yys)
	where
	(xs', ys') = unzip (zipWith (\x y -> if (x < y) == dir then (x,y) else (y,x)) xs ys)
	n2 = (n `div` 2)
	(xxs, xys) = bimerge (take n2 xs') (drop n2 xs') n2 dir
	(yxs, yys) = bimerge (take n2 ys') (drop n2 ys') n2 dir
  
bisort xs = bisort' xs (length xs) True
	where
	bisort' zs 1 dir = zs
	bisort' zs n dir = xs'' ++ ys''
		where
		n2 = (n `div` 2)
		xs' = bisort' (take n2 zs) n2 dir
		ys' = bisort' (drop n2 zs) n2 (not dir)
		(xs'', ys'') = bimerge xs' ys' n2 dir
  
 -- randInts 1024 >>= (\x -> print (bisort x))
 -- randInts 1024 >>= (\xs -> print (snd (foldl (\(x, f) y -> (y, and [f, (x <= y)])) (-1, True) (bisort xs))))

ふと気が付けば今日は誕生日．四捨五入すると３０歳になってしまう歳になってしまった．しゃーねーからケーキでも焼くか．

パソコンに重たい計算をやらせながら寝たら部屋が暑い...　おかげであまり眠れずに非常に眠い．エアコンつけるか...

いい加減に髪が邪魔になってきたのでバサッと切りに行って来た．髪を切るのに金をかけるのが馬鹿らしく思えるので１０００円でカットできるQBハウスをためにしてみることに．休日の午後で結構待ったけど，実際のカットはスポーツ刈りで１０分かからず即効終了．とりあえず，今度行くときは平日の午前中にしよう．

画像回転で最内のループを１６個展開してみたら１．２倍速くなった．block での DC の最内ループも 32個展開してとうとう毎秒 300回を超えた．いやあ，これだけ単純な計算だと展開したほうがやっぱ速いなぁ．ということで，これにてプログラム凍結．ソースとか

32x32 の変換テーブルを２段階用意して画像回転してみたら見事に１．５倍の速さに．もちろん，元画像は長さを1.5倍して if 分によるチェックをはずしてある．どうやらテーブルを引くことで演算がほぼいらなくなるので速くなるのと，アクセスが32x32のブロック単位になるため，画像がどの方向でもキャッシュのあたりはずれがあまり変わらないことによるようだ．ただ，変換テーブルのところで小数点以下を切り捨てているので今の方法では画面が汚い...　改良できるのだろうか？

ソースとか