Haskellで、リストの末尾の要素を指定した数だけ取ってくる関数を書くとき、
書き方で速度がどのくらい変わるのか調べてみた。
main = getContents >>= putStr . unlines . takeLast 3 . lines
というコードを準備して、この中のmyTailの定義をいろいろ変えて、1〜100000を各行に書いたファイルを食わせてtimeで時間を調べてみる。
とりあえず安直な実装を試してみた。
takeLast n = reverse . take n . reverse
これで、0.63s user 0.07s system 72% cpu 0.954 total。
リスト用の関数をうまく使うと速くなるに違いない。というわけで、List.tailsを使ってみた。
takeLast n xs = List.tails xs !! (length xs - n)
0.75s user 0.08s system 70% cpu 1.183 total
とっても遅い。きっと「!!」では無駄にリストを作りまくってるんだろう。
メモリも無駄に食っていそうだ。
じゃあ3つ分のリストだけを保持しておくようにしてはどうだろう。
takeLastDo n m xs [] = xs takeLastDo n m (x:xs) (y:ys) | n == m = takeLastDo n n (xs++[y]) ys takeLastDo n m xs (y:ys) = takeLastDo n (m+1) (xs++[y]) ys takeLast n xs = takeLastDo n 0 [] xs
「++」をけっこう使うことになってしまったので、遅そう…と思いきや、
0.24s user 0.04s system 65% cpu 0.418 total。
意外とまともだ。ghcが偉いのかな?
最後に、http://haskell.g.hatena.ne.jp/muscovyduck/20060612/p1 にあったプログラム。
diffList xs [] = xs diffList [] ys = ys diffList (_:xs) (_:ys) = diffList xs ys takeLast n xs = diffList xs (drop n xs)
0.20s user 0.03s system 69% cpu 0.328 total
うーん。さすが。無駄がない。
別の言語ということで、perlの1linerを試してみた。
time perl -e 'while(<STDIN>){ $line[$i++%3] = $_; } for($j = $i-3; $j < $i; $j++) { print $line[$j%3]; }' < data
0.18s user 0.01s system 69% cpu 0.285 total
あらま。あっさりHaskellに勝ってしまった。
unlines, linesとか効率が悪いんだろうか。
あと、GNUのtailコマンド。
time tail -3 < data
0.00s user 0.01s system 45% cpu 0.019 total
もはや測定不能だ。