tailの速度比較

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
もはや測定不能だ。