No Such Blog or Diary

«Prev || 1 | 2 | 3 |...| 922 | 923 | 924 |...| 955 | 956 | 957 || Next»

Bitonic Sort in Haskell

比較の仕方がデータによらないソートである 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))))

四捨五入できない

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

暑くて眠い

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

QBハウス

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

Loop Unrolling

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

変換テーブルやってみた

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

ソースとか

«Prev || 1 | 2 | 3 |...| 922 | 923 | 924 |...| 955 | 956 | 957 || Next»
Search
Feeds

Page Top