ElixirでAtCoder参加してみよう(Tupleは書き換えが遅いよ）

# はじめに

[ElixirのリストとPythonのリストは違います](https://qiita.com/GeekMasahiro/items/e65af26ae11d84b905ff) この記事に書きました。Tupleによって高速になった例です。
しかし、Tupleにも欠点がありました。
Tupleのsizeが大きいほど、値を書き換えが遅い。O(n)の時間がかかるのです。

次の問題で、これを解決する必要があったので、方法をまとめてみます。
https://atcoder.jp/contests/abc141/tasks/abc141_c

# TLE発生！

[abc141_c](https://atcoder.jp/contests/abc141/tasks/abc141_c)は、List aの値毎の個数を求める処理をO(N)で行うことです。
Pythonで作った場合、Listを使って、問題なくクリアできます。Count()という便利なものもあるので、特別な事を気にしなくても解けてしまいます。

## TLEになるコード

Tupleを使って実装してみたら、TLEになりました。

```Elixir
defmodule Main do
～～省略～～
    def solve(n, k, q, a) do
        t =
        (for _ <- 0..n-1, reduce: {} do
           acc -> Tuple.append(acc, k-q)
        end)

        t = a |> Enum.reduce(t, fn (a,t) -> put_elem(t,a-1,elem(t,a-1)+1) end)

        Tuple.to_list(t)
        |> Enum.map(fn
            x when x>0 -> "Yes"
            x -> "No"
        end)
        |> Enum.join("\n")
        |> IO.puts()
    end
～～省略～～
```
put_elem()の処理で時間がかかっていました。

# Tupleの値書き換え速度の調査

書き換え(put_elem)が遅いかどうか、試してみます。

|時間(μs)|Tupleの大きさ|
|--------|-------------|
|117|100000|
|2|100|

遅いです。117μSがどれくらい遅いかというと、abc141_cの問題をクリアするには、10^5回の更新を2秒以下で行う必要があります。
117μS*10^5 = 11.7秒
TLEになるレベルに遅い。

実行時間確認方法
```Elixir
iex(38)> tuple_size(t)
100000
iex(39)> :timer.tc(Kernel, :put_elem, [t,0,1])
{117,
 {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...}}
```

```Elixir
iex(46)> tuple_size(t)
100
iex(47)> :timer.tc(Kernel, :put_elem, [t,0,1])
{2,
 {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...}}
```

# :etsを使おう

いろいろ方法を考えてみたんですが、:etsがよさそう。elixirforumでも:etsとなってます。
https://elixirforum.com/t/way-to-get-o-1-access-set/24471/4

使い方は、[ここ等](https://elixirschool.com/ja/lessons/storage/ets)　をみてください。

# :etsを使ったプログラム

```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.read(:line) |> String.trim()
    def ii(), do: next_token() |> String.to_integer()
    def linei(), do: input() |> String.to_integer()
    def li(), do: input() |> String.split(" ") |> Enum.map(&String.to_integer/1)

    def inc_table(t, i) do
        ret = :ets.lookup(t,i)
        {_, val} = hd(ret)
        :ets.insert(t, {i,val+1})
    end

    def solve(n, k, q, a) do
        t = :ets.new(:user_lookup, [:set, :protected, :named_table])
        for i <- 0..n-1, do: :ets.insert(t, {i,k-q})

        a |> Enum.map(&inc_table(t,&1-1))

        (for i <- 0..n-1 do
            :ets.lookup(t,i)
            |> hd()
            |> elem(1)
        end)
        |> Enum.map(fn
            x when x>0 -> "Yes"
            x -> "No"
        end)
        |> Enum.join("\n")
        |> IO.puts()
    end

    def main() do
        n = ii()
        k = ii()
        q = ii()
        a = for _ <- 1..q, do: linei()
        solve(n, k, q, a)
    end

end

```
無事ACできました。実行時間は800msくらい。
10^5で割ると、8μS
TupleのNが小さいとき(1μS)レベルよりは10倍遅いですが、:etsの機能を考えると早いですね。

# まとめ

- :etsを使うことで、値の更新を高速にできACできた。
- データを更新する系は、Tupleは向いていない。
- abc141_cの問題のような簡単配列処理に:etsを持ち出すのは、ちょっと記述量が多い（Pythonのリストの記述に比べて）気がした。
- この問題は、マップを使う方法（O(log n)かな？)も候補。imutableな操作なので更新はTupleと同様遅いかも？機会があったら今後調べてみたい。


補足
Mapの場合を記事にしました
https://qiita.com/GeekMasahiro/items/f2929b3919adf959be88