筆者はHaskell入門者で、趣味として競技プログラミングサイトのAtCoderやProject Eulerの問題を解いています。
これら2サイトのうち、Project Eulerは数学っぽい問題が多く、他言語と比べてHaskellは有利なくらいの印象ですが、AtCoderでは入出力がハマりどころになります。
特に入力が大量の場合1、コンパイル言語のはずのHaskellがスクリプト言語より遅くなることがあります。実際、私はそのような問題でTLE (Time Limit Exceeded、実行時間制限オーバー) してしまい悲しい思いをしました。
本稿ではこの原因と対策を紹介します。
HaskellのString型は遅い
私がTLEしてしまったのは、標準入力の処理にgetLineやgetContentsを使っていたのが理由です。これらの関数は入力をIO String型として処理しますが、このString型が良くありません。
HaskellではString型がChar型のリストとして実装されています。このことはメリットもたくさんあるのですが、大きい文字列を扱うときには性能面の足かせになっています。そのため、一定以上のサイズの文字列を処理するなら高速なByteString型を使うのが定石になっています。感覚的には、扱う文字列が数百KBを超えるくらいからByteString型を使った方がよさそうに思います。
このこと自体はHaskellベテランの人にとっては常識中の常識だと思うんですが、ライトHaskellユーザーの私は完全に忘れており、敗北を喫したというわけです。
ByteString型を使った入力処理
String型が遅いことに気づいた私はByteString型を使うようになりました。私が現在使っているAtCoder用入力関数は次のようなものです。
import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as BS
tuplify2 (x:y:_) = (x,y)
tuplify2 _ = undefined
--Input functions with ByteString
readInt = fst . fromJust . BS.readInteger
readIntTuple = tuplify2 . map readInt . BS.words
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine
getIntNList n = map readIntList <$> replicateM (fromIntegral n) BS.getLine
getIntMatrix = map readIntList . BS.lines <$> BS.getContents
getIntTuple = readIntTuple <$> BS.getLine
getIntNTuples n = map readIntTuple <$> replicateM (fromIntegral n) BS.getLine
getIntTuples = map readIntTuple . BS.lines <$> BS.getContents
main = do
[n,m] <- getIntList
print [n,m]
見てわかる通りData.ByteStringパッケージではString型と同名もしくは近い名前の関数を提供しているので、String型からの移行はそれほど難しくないはずです。
実際の速度差
ABC127のD問題を例に出すと、私の書いたプログラムで入力にStringとByteStringそれぞれを使ったときの速度差は次の通りです。
| 実行時間 | |
|---|---|
| String版 | 1545 ms |
| ByteString版 | 325 ms |
String版の方が約1.2秒遅い結果になりました。この問題の制限時間は2秒ですから、入力処理だけで制限時間の半分以上を使っているわけです。これはHaskell入門者にとっては大きいハンディキャップになりかねません。
ちなみに、この問題の入力は最大10万行程度、1行は最大20バイト程度です。
また、Chokudai SpeedRun 002のA問題に至っては、ByteString版が200msなのに対してString版はTLE（2秒オーバー）します。String版を使っていると土俵にすら立てない問題があるのです。
まとめ
- AtCoderにHaskellで挑戦している人はByteString型を使った方がいいよ！
最初に書いた通り私はHaskellの経験が多いわけではないので、String型のまま高速に処理する方法があるのかもしれません。ベテランの方々のご意見お待ちしております。
参考URL
- Data.ByteString.Char8
-
Haskellで解くAtCoder - The curse of λ
- 本稿書きおわってから見つけたんですが神記事では…
-
といっても数万行、数MB程度 ↩