HaskellでAtCoderの問題を解く（入力の高速化編） #AtCoder

筆者はHaskell入門者で、趣味として競技プログラミングサイトのAtCoderやProject Eulerの問題を解いています。

これら2サイトのうち、Project Eulerは数学っぽい問題が多く、他言語と比べてHaskellは有利なくらいの印象ですが、AtCoderでは入出力がハマりどころになります。

特に入力が大量の場合¹、コンパイル言語のはずの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程度 ↩