ByteStringでwcを書く

Haskell

Haskellで速いwcを書いてみようという記事を読んだのですが、Haskellの文字列表現は他言語に比べ非常に効率が悪いわけで、それをつかってそこそこ速くしようとするとコードが汚くなってしまわざるを得ないという感じを受けました。

そこでByteStringで書いてみるとどうなるかという実験。

import qualified Data.ByteString as B
import Data.ByteString.Base

main = do
    text <- B.getContents

    -- lines
    putStr . show . length . B.split (c2w '\n') $ text
    putChar ' '

    -- words
    putStr . show . length. B.splitWith isSpaceWord8 $ text
    putChar ' '

    -- characters
    putStrLn . show . B.length $ text

textを三回使いまわし,別々に調べるという全くもって工夫の無いコードですが、Haskellで速いwcを書いてみようでも使っているFreeBSDのhandbook(3.8Mバイト)を入手して測定したところ

% ghc --make -O -fglasgow-exts wc.hs 
% time ./wc < book.txt                                                                                              
84709 654559 3848348
./wc < book.txt  0.19s user 0.02s system 97% cpu 0.214 total

0.19sと十分速いです。メモリ使用量も1Mで,非常に少なかったです。
ちなみに-Oと-fglasgow-extsなしだと1.67sでした。


Haskellで効率の良いプログラムを書きたいときには

  • ライブラリで用意されている関数を積極的に使う
    • 例えば、ByteStringモジュールでは複数のループを一つのループにするループ融合という最適化などが行われているのですが、再帰を使って自前でループを書くとこういった最適化が阻害されてしまいます。(今回のプログラムではほとんど関係ないですが)
  • データ構造を適切に選ぶ
    • 大量のデータを扱う場合はByteStringやArrayなどの方が適している場合がある
  • 最適化オプション-O -fglasgow-extsをつける。

あたりに注意するだけで,大分違ってくると思います。