リスト最後尾への追加は、実際どのくらい遅くなるのか

elixir school のドキュメントに以下の記載がある。

Elixirはリストコレクションを連結リストとして実装しています。
すなわちリストの長さを得るのは線形時間(O(n))の処理となります。
このことから、リスト先頭への追加はほとんどの場合にリスト末尾への追加より高速です

そうなんだ。
で、実際どのくらい？が気になったので試してみた。

バージョン情報は以下。

[twintaro@phoenix ~]$ elixir --version
Erlang/OTP 22 [erts-10.4.2] [source] [64-bit] [smp:1:1] [ds:1:1:10] [async-threads:1] [hipe]

Elixir 1.9.0-rc.0 (e5888e7) (compiled with Erlang/OTP 22)

以下のコードで試す。

defmodule My do
  def insert_check(len) do
    ary = for x <- 1..len do
      x
    end
    starttime = Time.utc_now
    for y <- 1..100 do
#1      List.insert_at(ary, -1, y)
#2      [y|ary]
    end
    endtime = Time.utc_now
    IO.inspect Time.diff(endtime, starttime, :microsecond) / 100
  end
end

length_patterns = [1,1,10,100,1000,10000,100000]
for lp <- length_patterns do
  IO.inspect My.insert_check(lp)
  IO.inspect "-----"
end

コメントアウトしてある部分は、
1が最後尾への追加、
2が先頭への追加
です。

1~100000までの長さの配列を作って、そこに対して要素の追加を行います。
(実際に追加されるんじゃなくて、追加された配列が返る)

回数少ないとブレそうなので１００回やって平均を出します。
で、結果。

1.最後尾への追加

0.21 # 1
"-----"
0.29 # 10
"-----"
0.57 # 100
"-----"
6.79 # 1000
"-----"
63.48 # 10000
"-----"
981.81 # 100000
"-----"

確かに、配列の要素が増えるほど、処理時間が増えてる。。。
では、先頭への追加は？

2.先頭への追加

0.14 # 1
"-----"
0.06 # 10
"-----"
0.05 # 100
"-----"
0.07 # 1000
"-----"
0.1 # 10000
"-----"
0.29 # 100000
"-----"

うん、要素が増えても、処理速度は変わらない。
要素数が少なければそんなに問題にならないかもですが、
理由がなければ先頭に追加をしておけば安心ですね。

実際数値で出してみて、腹落ちしたというお話でした。m(_ _)m