ElixirでAtCoder参加してみよう(Mapの実行時間を調べてみた）

はじめに

TupleはO(1)でアクセスがでるが、書き換えが遅い。という記事を書きました。

zacky1972 さんから、処理時間を測定についてコメントをいただきました。
https://github.com/zacky1972/various_map

Mapのget,putをみてみると、

##### With input size 100000 #####
Name              ips        average  deviation         median         99th %
Map get        8.16 M      122.55 ns ±15375.64%          84 ns         209 ns
Map put        6.86 M      145.67 ns  ±2532.76%      120.90 ns      162.50 ns

putもgetも1μs以下!!!
つまり10^5実行しても0.1秒
Tupleやets使ってみましたが、Mapでいいんじゃないか？

Tuple/ETSの記事と同じくAtCoderの問題(abc141_c)で試してみました

マップを使った回答

    def solve(n, k, q, a) do
        t = Enum.reduce(a, %{}, fn
             a,t -> Map.update(t, a, k-q+1, fn x -> x+1 end)
            end)

        (for i <- 1..n, do: Map.get(t,i,k-q))
        |> Enum.map(fn
            x when x>0 -> "Yes"
            x -> "No"
        end)
        |> Enum.join("\n")
        |> IO.puts()
    end

実行時間

AtCoderのジャッジでの実行時間

保存方法	実行時間
:ets	805ms
Map	770ms

まとめ

• Mapは、O(logN)なので、Tupleの読み取り時のO(1)よりは遅いが、N=10^5程度なら大きな問題にはならない。
• Tupleは、書き換えが遅い問題があるは、Mapでは問題ない。
• :etsも候補になるが、今回の例では、Mapでも大差はなかった。
• MapはEnumが使えたり、記述も用意なので、Mapの利点は大きい。