TL;DR
初めてHaskellを触って、緑Diffの問題を解きました。
Haskellの文法を知りつつ性能改善に努めます。
今回チャレンジする問題
個人的に、移動方法に制限がありますが最適輸送の考えに少し親しいものを感じていて面白いと思いました。
解き方についての考察
初期で0となっていない玉の中で、小さいインデックスから順番に見ていきます。
まず、それまでのIndexについて埋められていれば問題ないですが、埋められないのであれば達成できないとして終了をします。
もし埋められるのであれば、どこまで埋められるかを仮想的に配置をします。
（このときに、埋めようとしているものの中に1より玉の数を保持していても、後で埋まっているところに対して同様の処理をするため問題ないです）。
そして、最終的に埋めた数がnと一致するか確認をすれば良いことがわかります。
（解説 - トヨタ自動車プログラミングコンテスト2024#11(AtCoder Beginner Contest 379)に詳細内容があります）
Haskellでの実装方法について
Haskellは関数型プログラミング言語で、変数は全て immutable です。
こちらに注意をしてなんの機能が必要かを考えます。
必要な機能
- 関数を実行する機能: これは言わずもがなです。
- 標準入力をサポートする機能: 競プロでは必須の機能です。
- リストを結合する機能:
X_iの内容とA_iの内容について、同じタイミングで扱いたいため結合をする必要があります。 - sortする機能:
X_iについては順番に与えられていないため sortをする必要があります。 - 関数を繰り返し実行する機能: これは言わずもがなです。
- 関数を早期終了する機能: 途中で達成できない場合は早期に終了をする必要があります。
Haskellでの実装方法について
Haskellについて公式ドキュメントを参照する際はHoogleが非常に便利です。
任意の関数について調べることができます。
- 関数を実行する機能:
- 関数を実行するためのもの 7.1 Basic I/O Operations in haskell-tutorial.dvi
- 標準入力をサポートする機能:
- リストを結合する機能:
- リストを結合するためのもの zip
- sortする機能:
- リストをソートするためのもの sort
- タプルに関する順序について: (公式ドキュメントを見つけられませんでしたが、第一要素でソートしています🙇 [Haskell-beginners] sorting by elements in a tuple)
- 関数を繰り返し実行する機能:
- 関数内でwhereを利用し小さな関数を定義できます where in CheatSheet.pdf
- 条件下によって異なる値を返すためのもの A Gentle Introduction to Haskell: Patterns
-
|を利用して条件分岐を行うことができますし、引数によって異なる関数を呼び出すこともできます。
-
- 関数を早期終了する機能:
- 値の型が不明瞭である場合に利用できるもの Maybe(Just, Nothing)
- (こちらを利用することで不要な計算は行わないようにできる)
初回の実装について
下の実装で一応ACを取ることができます。
しかしながら、1488msという結果でHaskellとしてはとても遅い結果になり、他の提出者の中でももっとも遅い結果になってしまいました（2024/11/16時点）。
性能改善について
なぜ上記のコードが悪いのかはいくつか理由があるため、修正を加えてどの程度改善できるかを試してみます。
1. 遅延評価によるサンクの蓄積
Haskellは遅延評価を行う言語で、式が必要になるまで評価されません(Thunk - HaskellWiki)
そのため、コード内の go 関数では、sum と sumIdx の値が逐次計算されず、評価されるまで「サンク」（未評価の式）が蓄積されます。特に以下の部分で問題が発生します
go ((x, a):xs) sum sumIdx
| sum < fromIntegral x - 1 = Nothing
| otherwise = go xs (sum + a) (sumIdx + a * fromIntegral x)
ここでは sum + a や sumIdx + a * fromIntegral x が逐次評価されず、巨大な未評価の式が蓄積され、メモリ使用量が増大し、最悪の場合スタックオーバーフローになります。
こちらに対応するためには、引数を厳密評価する必要があります。
Haskellでは「Bang Patterns（ビックリマーク !）」を使って引数を厳密評価できます。これにより、サンクの蓄積を防ぎ、メモリ効率が向上します。
(6.14. Bang patterns and Strict Haskell — Glasgow Haskell Compiler 9.13.20241116 User's Guide)
{-# LANGUAGE BangPatterns #-}
go :: [(Int, Int)] -> Int -> Int -> Maybe Int
go [] !sum !sumIdx
| sum == n = Just $ n * (n + 1) `div` 2 - sumIdx
| otherwise = Nothing
go ((x, a):xs) !sum !sumIdx
| sum < x - 1 = Nothing
| otherwise = go xs (sum + a) (sumIdx + a * x)
-
!sumと!sumIdxで厳密評価を行い、遅延評価によるサンクの蓄積を防ぎます。
しかし、この方法でも 50ms ほどしか改善されなく誤差の範囲内でした。
2. リストによるソートの遅さ
Haskellのリストはリンクリスト構造であり、大量のデータを扱う場合、メモリ効率やキャッシュ効率が悪くなります。特に sort 関数を使ってリストをソートする部分がボトルネックになる可能性があります。
リストよりも高速なデータ構造である Data.Vector を使用することで、メモリ効率とアクセス速度が向上します。
Data.Vector.Unboxed
Data.Vector.Algorithms.Intro
また、go関数でリストのパターンマッチ ([] や ((x, a):xs)) を使用していましたが、ベクターには使用できません。
代わりに、VU.length と VU.!（インデックスアクセス）を使用しました。
さらに、VectorではInteger型を利用できない上、今回の問題では2^29-1を超える値は出現しないため、Int型を利用します。
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Algorithms.Intro as VAI
main :: IO ()
main = do
[nStr, mStr] <- words <$> getLine
let n = read nStr :: Int
firsts <- VU.fromList . map read . words <$> getLine :: IO (VU.Vector Int)
seconds <- VU.fromList . map read . words <$> getLine :: IO (VU.Vector Int)
let xa = VU.zip firsts seconds
mxa <- VU.thaw xa
VAI.sort mxa
xaSorted <- VU.freeze mxa
case process xaSorted n of
Just ans -> print ans
Nothing -> print (-1)
この変更により、実行時間は 600ms ほど改善され、1488ms から 837ms ほどになりましたが、Haskellにしてはまだ遅い結果です。
3. IOアクションの遅さ
HaskellのIOアクションは工夫をしないと遅いと言われています。
- performance - Haskell program involving
readis much slower than an equivalent Python one - Stack Overflow - Iteratee I/O - HaskellWiki
この問題に対処するためには、ByteString が有効のようです。
Data.ByteString.Char8
（現時点で詳細な理由を把握できていないためわかりましたら追記をします🙇）
import qualified Data.ByteString.Char8 as BS
import Data.Maybe (fromJust)
readInts2 :: IO (Int, Int)
readInts2 = do
line <- BS.getLine
let [a, b] = map (fst . fromJust . BS.readInt) (BS.words line)
return (a, b)
readIntVector :: Int -> IO (VU.Vector Int)
readIntVector n = do
line <- BS.getLine
return $ VU.fromListN n $ map (fst . fromJust . BS.readInt) (BS.words line)
この変更により、実行時間は 837ms から 52msまで改善されました。。。！！！
（こちらの結果は, 2024/11/17時点で5番目に速い結果になりました）
まとめ
Haskellのコードが遅い理由と、パフォーマンス改善の方法についてまとめました。
- 遅延評価によるサンクの蓄積を防ぐために、引数を厳密評価する
- リストよりも高速なデータ構造である
Data.Vectorを使用する - IOアクションの遅さを防ぐために、
ByteStringなどを使用する
このように、Haskellのコードを高速化するための方法を学びました。これらのテクニックを使って、高速なHaskellプログラを書いてみましょう！
感想
普段はPythonを使っているので、Haskellは遅延評価や型推論など、新しい概念が多くて難しいですが、高速なコードを書くためのテクニックを学ぶことができて、とても勉強になりました。
また、標準ライブラリの遅延について外部のライブラリを利用して高速化することも面白いと感じました。
今回のようなパフォーマンス改善はHaskellに限らず、他の言語でも応用できるので、今後のコーディングにも役立てたいです。