ElixirのリストとPythonのリストは違います

はじめに

AtCoderでこの問題をPythonと同じ感覚で記述したら、処理時間オーバ(TLE)になってしまいました。

対処方法をまとめてみます

TLEになったコード

main.ex

defmodule Main do
    def input(), do: IO.read(:line) |> String.trim()
    def ii(), do: input() |> String.to_integer()
    def li(), do: input() |> String.split(" ") |> Enum.map(&String.to_integer/1)
 
    def pos(i,a), do: Enum.at(a,i)
 
    def d(0,k,n,a), do:  pos(0,a) + k - pos(n-1,a)
    def d(i,_k,_n,a), do:  pos(i,a) - pos(i - 1, a)
 
    def solve(k, n, a) do
        d = for i <- 0..n-1, do: d(i,k,n,a)
        max_d = Enum.max(d)
        ans = Enum.sum(d) - max_d
        IO.puts(ans)
    end
 
    def main() do
        [k, n] = li()
        a = li()  # type: "List[int]"
        solve(k, n, a)
    end
 
end

入力例１，２では、正しい結果を出力して、処理内容としては問題がないコードでした。
しかし、処理時間が、制限時間を超えで不正解となってしまいました。

TLEのエラーになった時の入力データは、

nが200000と大きく、リストaが大きい事がわかります。

Pythonのコードの場合、これと同等の内容でも時間内に処理できます。

ElixirとPythonの違いはなにか？

Pythonの場合は、どうしてTLEにならず、Elixirの場合TLEなんでしょうか。

計算量を表す指標にO() （オーダー）があります。

TLEになったプログラムでは、Enum.at()を使っています。
i番目のデータを見つける為に、使用していますが、先頭からi番目まで辿っていく処理をしています。
処理時間はiの値比例した時間がかかります。iが10倍になれば処理時間は10倍かかります。
このような処理はO(n)と呼ばれています。Nが200000だとEnum.at(200000)は、Enum.at(0)にくらべて、200000倍の時間がかかることになります。これは遅い。

Pythonのリストの要素へのアクセスするa[i]はiの値によらず一定の値です。オーダーはO(1)。つまりNが大きくなっても速度の低下はしません。

Nが大きくなるとこの違いは歴然です

elem()を使おう

elem()はO(1)の処理時間です。
List.to_tuple(a)でタプルに変換して要素の参照は、elem()にしてみました。

main.ex

defmodule Main do
    def input(), do: IO.read(:line) |> String.trim()
    def ii(), do: input() |> String.to_integer()
    def li(), do: input() |> String.split(" ") |> Enum.map(&String.to_integer/1)

    def pos(i,a), do: elem(a,i)

    def d(0,k,n,a), do:  pos(0,a) + k - pos(n-1,a)
    def d(i,_k,_n,a), do:  pos(i,a) - pos(i - 1, a)

    def solve(k, n, a) do
        d1 = List.to_tuple(a)
        d = for i <- 0..n-1, do: d(i,k,n, d1)
        max_d = Enum.max(d)
        ans = Enum.sum(d) - max_d
        IO.puts(ans)
    end

    def main() do
        [k, n] = li()
        a = li()  # type: "List[int]"
        solve(k, n, a)
    end

end

まとめ

Tupleは要素のアクセスは速いですが、Enumが使えません。
Tuple/Listには一長一短があるので区別して使いましょう。

特徴	List	Tuple	List(Python)
要素の参照	O(n)	O(1)	O(1)
イテレーション	〇	×	〇

PythonのようにListでどっちもできるわけではないので、必要に応じて
Tuple.tolist(), List.to_tuple()で変換して使いましょう。

参考
Pythonの計算量
https://wiki.python.org/moin/TimeComplexity