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

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

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

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

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

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

    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

IO.read(:all)

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

    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

IO.read(:all)単体

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

    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

IO.binstream(:stdio, :line)

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

    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

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

    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

プログラム全体

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)を使うのが効果的でした。