HaskellでAtcoderの緑diffを解いてみた（性能改善も添えて）

# TL;DR

初めてHaskellを触って、緑Diffの問題を解きました。
Haskellの文法を知りつつ性能改善に努めます。

# 今回チャレンジする問題

[C - Sowing Stones](https://atcoder.jp/contests/abc379/tasks/abc379_c)

個人的に、移動方法に制限がありますが最適輸送の考えに少し親しいものを感じていて面白いと思いました。

# 解き方についての考察

初期で0となっていない玉の中で、小さいインデックスから順番に見ていきます。
まず、それまでのIndexについて埋められていれば問題ないですが、埋められないのであれば達成できないとして終了をします。
もし埋められるのであれば、どこまで埋められるかを仮想的に配置をします。
（このときに、埋めようとしているものの中に1より玉の数を保持していても、後で埋まっているところに対して同様の処理をするため問題ないです）。

そして、最終的に埋めた数が`n`と一致するか確認をすれば良いことがわかります。

（[解説 - トヨタ自動車プログラミングコンテスト2024#11(AtCoder Beginner Contest 379)](https://atcoder.jp/contests/abc379/editorial/11323)に詳細内容があります）

# Haskellでの実装方法について

Haskellは関数型プログラミング言語で、変数は全て immutable です。
こちらに注意をしてなんの機能が必要かを考えます。

## 必要な機能

1. 関数を実行する機能: これは言わずもがなです。
1. 標準入力をサポートする機能: 競プロでは必須の機能です。
1. リストを結合する機能: `X_i`の内容と`A_i`の内容について、同じタイミングで扱いたいため結合をする必要があります。
1. sortする機能: `X_i`については順番に与えられていないため sortをする必要があります。
1. 関数を繰り返し実行する機能: これは言わずもがなです。
1. 関数を早期終了する機能: 途中で達成できない場合は早期に終了をする必要があります。

## Haskellでの実装方法について

Haskellについて公式ドキュメントを参照する際は[Hoogle](https://hoogle.haskell.org/)が非常に便利です。
任意の関数について調べることができます。

1. 関数を実行する機能: 
    - 関数を実行するためのもの [7.1 Basic I/O Operations in haskell-tutorial.dvi](https://www.haskell.org/tutorial/haskell-98-tutorial.pdf)
1. 標準入力をサポートする機能: 
    - 文字の羅列: 例 `n m`のような取得
        - 標準入力をするためのもの [getLine](https://hackage.haskell.org/package/ihaskell-0.12.0.0/docs/IHaskellPrelude.html#v:getLine)
        - 空白で区切られた文字列をリストに変換するためのもの [words](https://hackage.haskell.org/package/base-4.20.0.1/docs/Prelude.html#v:words)
        - 関数適応をするための中間記法 [<$>](https://hackage.haskell.org/package/base-4.20.0.1/docs/Prelude.html#v:-60--36--62-)
    - リスト: 例 `A_1, A_2, ..., A_n`のような取得
        - 標準入力をするためのもの [getLine](https://hackage.haskell.org/package/ihaskell-0.12.0.0/docs/IHaskellPrelude.html#v:getLine)
        - 基本的な変換:
            - 空白で区切られた文字列をリストに変換するためのもの [words](https://hackage.haskell.org/package/base-4.20.0.1/docs/Prelude.html#v:words)
            - リストに対して関数を適応するためのもの [map](https://hackage.haskell.org/package/base-4.20.0.1/docs/Prelude.html#v:map)
            - StringをIntに変換するためのもの [read](https://hackage.haskell.org/package/base-4.20.0.1/docs/Prelude.html#v:read)
        - 標準入力に対して,基本的な変換を適応するためのもの [fmap](https://hackage.haskell.org/package/base-4.20.0.1/docs/Prelude.html#v:fmap)
1. リストを結合する機能: 
    - リストを結合するためのもの [zip](https://hackage.haskell.org/package/base-4.20.0.1/docs/Prelude.html#v:zip)
1. sortする機能:
    - リストをソートするためのもの [sort](https://hackage.haskell.org/package/base-4.20.0.1/docs/Data-List.html#v:sort)
    - タプルに関する順序について: (公式ドキュメントを見つけられませんでしたが、第一要素でソートしています🙇 [[Haskell-beginners] sorting by elements in a tuple](https://mail.haskell.org/pipermail/beginners/2009-October/002415.html))
1. 関数を繰り返し実行する機能:
    - 関数内でwhereを利用し小さな関数を定義できます [where in CheatSheet.pdf](https://hackage.haskell.org/package/CheatSheet-1.11/src/CheatSheet.pdf)
    - 条件下によって異なる値を返すためのもの [A Gentle Introduction to Haskell: Patterns](https://www.haskell.org/tutorial/patterns.html)
        - `|`を利用して条件分岐を行うことができますし、引数によって異なる関数を呼び出すこともできます。
1. 関数を早期終了する機能:
    - 値の型が不明瞭である場合に利用できるもの [Maybe(Just, Nothing)](https://hackage.haskell.org/package/base-4.20.0.1/docs/Prelude.html#t:Maybe)
    - (こちらを利用することで不要な計算は行わないようにできる)

# 初回の実装について

下の実装で一応ACを取ることができます。
- [提出 #59747483 - トヨタ自動車プログラミングコンテスト2024#11(AtCoder Beginner Contest 379)](https://atcoder.jp/contests/abc379/submissions/59747483)

しかしながら、1488msという結果でHaskellとしてはとても遅い結果になり、他の提出者の中でももっとも遅い結果になってしまいました（2024/11/16時点）。

# 性能改善について

なぜ上記のコードが悪いのかはいくつか理由があるため、修正を加えてどの程度改善できるかを試してみます。

## 1. **遅延評価によるサンクの蓄積**
Haskellは遅延評価を行う言語で、式が必要になるまで評価されません([Thunk - HaskellWiki](https://wiki.haskell.org/Thunk))
そのため、コード内の `go` 関数では、`sum` と `sumIdx` の値が逐次計算されず、評価されるまで「サンク」（未評価の式）が蓄積されます。特に以下の部分で問題が発生します

```haskell
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](https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/strict.html))

```haskell
{-# 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 ほどしか改善されなく誤差の範囲内でした。

- [提出 #59870778 - トヨタ自動車プログラミングコンテスト2024#11(AtCoder Beginner Contest 379)](https://atcoder.jp/contests/abc379/submissions/59870778)

## 2. **リストによるソートの遅さ**

Haskellのリストはリンクリスト構造であり、大量のデータを扱う場合、メモリ効率やキャッシュ効率が悪くなります。特に sort 関数を使ってリストをソートする部分がボトルネックになる可能性があります。
- [Data.List](https://hackage.haskell.org/package/base-4.20.0.1/docs/Data-List.html)

リストよりも高速なデータ構造である `Data.Vector` を使用することで、メモリ効率とアクセス速度が向上します。
[Data.Vector.Unboxed](https://hackage.haskell.org/package/vector-0.13.2.0/docs/Data-Vector-Unboxed.html)
[Data.Vector.Algorithms.Intro](https://hackage.haskell.org/package/vector-algorithms-0.9.0.2/docs/Data-Vector-Algorithms-Intro.html)

また、`go`関数でリストのパターンマッチ ([] や ((x, a):xs)) を使用していましたが、ベクターには使用できません。
代わりに、`VU.length` と `VU.!`（インデックスアクセス）を使用しました。
さらに、`Vector`ではInteger型を利用できない上、今回の問題では2^29-1を超える値は出現しないため、Int型を利用します。

```haskell
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)
```

- [提出 #59880059 - トヨタ自動車プログラミングコンテスト2024#11(AtCoder Beginner Contest 379)](https://atcoder.jp/contests/abc379/submissions/59880059)

この変更により、実行時間は 600ms ほど改善され、1488ms から 837ms ほどになりましたが、Haskellにしてはまだ遅い結果です。

## 3. **IOアクションの遅さ**

HaskellのIOアクションは工夫をしないと遅いと言われています。
- [performance - Haskell program involving `read` is much slower than an equivalent Python one - Stack Overflow](https://stackoverflow.com/questions/29186541/haskell-program-involving-read-is-much-slower-than-an-equivalent-python-one)
- [Iteratee I/O - HaskellWiki](https://wiki.haskell.org/Iteratee_I/O)

この問題に対処するためには、`ByteString` が有効のようです。
[Data.ByteString.Char8](https://hackage.haskell.org/package/bytestring-0.12.1.0/docs/Data-ByteString-Char8.html)

（現時点で詳細な理由を把握できていないためわかりましたら追記をします🙇）

```haskell
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まで改善されました。。。！！！

- [提出 #59882262 - トヨタ自動車プログラミングコンテスト2024#11(AtCoder Beginner Contest 379)](https://atcoder.jp/contests/abc379/submissions/59882262)

（こちらの結果は, 2024/11/17時点で5番目に速い結果になりました）

# まとめ

Haskellのコードが遅い理由と、パフォーマンス改善の方法についてまとめました。

- 遅延評価によるサンクの蓄積を防ぐために、引数を厳密評価する
- リストよりも高速なデータ構造である `Data.Vector` を使用する
- IOアクションの遅さを防ぐために、`ByteString` などを使用する

このように、Haskellのコードを高速化するための方法を学びました。これらのテクニックを使って、高速なHaskellプログラを書いてみましょう！

# 感想

普段はPythonを使っているので、Haskellは遅延評価や型推論など、新しい概念が多くて難しいですが、高速なコードを書くためのテクニックを学ぶことができて、とても勉強になりました。
また、標準ライブラリの遅延について外部のライブラリを利用して高速化することも面白いと感じました。

今回のようなパフォーマンス改善はHaskellに限らず、他の言語でも応用できるので、今後のコーディングにも役立てたいです。