ElixirでAtCoder 入力処理の高速化（ABC309 Eで試す）

# 入力の処理の高速化の調査

ABC309Eが入力の処理だけで、1700msもかかり解けなかったので、高速化方法を調査してみました。

※この記事は、新ジャッジになる前に測定したものです。現在のジャッジで実行するとこれよりも遅い値になっていると思いますが、同様な対策は有効だと思います。

# ファイルの読み込みだけで1700ms

入力の読み取りのみのプログラムで実行時間を調べてみる

```Elixir
    def main() do
        n = ii()
        m = ii()
        p = li()  # type: "List[int]"
        xy = (for _ <- 1..m, do: li())
        # solve(n, m, p, xy)
        IO.puts(4)
    end

```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/532235/e80e0f67-182f-996c-ff88-ee21b4b0f88c.png)

# IO.read(:all)

`IO.read(:all)`でまとめて読み込んでみるが変化なし。

```Elixir
    def main() do
        n = ii()
        m = ii()
        p = li()  # type: "List[int]"
        xy =
        IO.read(:all)
        |> String.trim()
        |> String.split("\n")
        |> Enum.map(fn x ->
            String.trim(x)
            |> String.split(" ")
            |> Enum.map(&String.to_integer/1)
            end)
        # xy = (for _ <- 1..m, do: li())
        # test(n, m, p, xy)
        # solve(n, m, p, xy)
        IO.puts(4)
    end
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/532235/4073e648-1608-168f-6207-d52a5308d9d6.png)

# IO.read(:all)単体

`IO.read(:all)`だけの処理時間をみてみるとこれだけで結構かかっている。これではだめだな。

```Elixir
    def main() do
        n = ii()
        m = ii()
        p = li()  # type: "List[int]"
        xy =
        IO.read(:all)
        # xy = (for _ <- 1..m, do: li())
        # test(n, m, p, xy)
        # solve(n, m, p, xy)
        IO.puts(4)
    end
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/532235/173523be-8cf0-1b65-a322-70ebbd31f9b4.png)

# IO.binstream(:stdio, :line)

`IO.binstream(:stdio, :line)`を使ってみる。いい感じです。

```Elixir
    def main() do
        n = ii()
        m = ii()
        p = li()  # type: "List[int]"
        xy =
        IO.binstream(:stdio, :line)
        # xy = (for _ <- 1..m, do: li())
        # test(n, m, p, xy)
        # solve(n, m, p, xy)
        IO.puts(4)
    end
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/532235/54233e75-b94f-a3f5-121d-122ec0dabb53.png)

`IO.binread(:stdio, :all)`で読み込み、データの整形もしてみる。

```Elixir
    def main() do
        n = ii()
        m = ii()
        p = li()  # type: "List[int]"

        xy =
            IO.binread(:stdio, :all)
            |> String.trim()
            |> String.split("\n")
            |> Enum.map(fn x ->
                String.trim(x)
                |> String.split(" ")
                |> Enum.map(&String.to_integer/1)
                end)
        # xy = (for _ <- 1..m, do: li())
        # test(n, m, p, xy)
        # solve(n, m, p, xy)
        IO.puts(4)
    end
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/532235/0aa4b698-ec75-9bff-41d3-42030f1c0ec6.png)

# プログラム全体

```Elixir
defmodule Main do
    import Bitwise
    def next_token(acc \\ "") do
        case IO.getn(:stdio, "", 1) do
          " " -> acc
          "\n" -> acc
          x -> next_token(acc <> x)
        end
    end
    def input(), do: IO.binread(:line) |> String.trim()
    def ii(), do: next_token() |> String.to_integer()
    def li(), do: input() |> String.split(" ") |> Enum.map(&String.to_integer/1)

    def new() do
        :ets.new(:memo, [:set, :protected, :named_table])
    end

    def put(v, k) do
        :ets.insert(:memo, {k,v})
        v
    end

    def get(k) do
        case :ets.lookup(:memo, k) do
            [{_,v}|_] -> v
            [] -> nil
        end
    end

    def lookup_g(g, i) do
        Map.get(g, i, 0)
    end

    def insurance_count(g, parent, 1) do
        lookup_g(g, 1)
    end

    def insurance_count(g, parent, i) do
        case get(i) do
          nil ->
            max(
                lookup_g(g, i),
                insurance_count(g, parent, parent[i])-1
            )
            |> put(i)
          x-> x
        end
    end

    def solve(n, m, p, xy) do
        g = for [x,y] <- xy, reduce: %{} do
            g -> Map.update(g, x, y+1, fn prev_y -> max(prev_y, y + 1) end)
        end
        parent = for {i,p} <- Enum.zip(2..n,p), into: %{}, do: {i,p}

        new()
        # IO.inspect(g)
        # IO.inspect(parent)
        1..n
        |> Enum.map(fn x -> insurance_count(g, parent, x) end)
        # |> IO.inspect(label: "result")
        |> Enum.count(fn x -> x > 0 end)
        |> IO.puts()
    end

    def main() do
        n = ii()
        m = ii()
        p = li()  # type: "List[int]"

        xy =
            IO.binread(:stdio, :all)
            |> String.trim()
            |> String.split("\n")
            |> Enum.map(fn x ->
                String.trim(x)
                |> String.split(" ")
                |> Enum.map(&String.to_integer/1)
                end)
        # xy = (for _ <- 1..m, do: li())
        # test(n, m, p, xy)
        solve(n, m, p, xy)
    end

end
```

最終的には、1669 msでACできました。

IO.binread(:stdio, :all)を使うのが効果的でした。