LinkedListのランダムアクセスについて

1 この記事で何がしたいか？
2 実施条件
3 結論
4 なぜそうなるのか？
5 追記分

この記事で何がしたいか？

Qiitaの「軽い気持ちでLinkedListを使ったら休出する羽目になった話」を見て、

どの程度APIのパフォーマンスに影響が出るのか気になったのでテスト。

実施条件

１．iteratorのfor文(条件式とi++で回すタイプ)

２．拡張for文

上記タイプで処理時間に差が出る模様の為、どちらも試してみた。

結論

1万件程度のデータ数であれば、たいして問題にならない。

10万件を超えるような場合は大きな障害を生む可能性がある。

実施詳細

ランダムアクセス以外

まず、問題となったLinkedListのランダムアクセス以外をテスト

実行結果：最大10msで処理完了。

実行結果グラフ

前述通り、上記グラフにはLinkedListをランダムアクセス（get(index)）した結果は追加していない。

ArrayListは50万件処理しても、get(i)と拡張for文にさほど大差はなく、LinkedListも拡張for文なら問題ないパフォーマンスとなっている。

ランダムアクセス

先ほどのグラフにLinkedListを追加してみた。

実行結果：グラフがグラフの意味をなさなくなった。

LinkedListのランダムアクセス追加グラフ

もはやLinkedListのランダムアクセス以外が、処理時間に差がありすぎて限りなく0に見える。

50万件の処理時間は最大で155,848msとなり、リストからただ値を取得するだけで約2分30秒かかる恐ろしいパフォーマンスを誇る。

また、要素が10万件程度でも、約4秒程度かかってしまっている為、パフォーマンスを気にする場面では通常のfor文は使用しないようにしたい。

ランダムアクセスの処理時間グラフ

LinkedListの50万件の処理時間をグラフ化すると以下のようになる。

実行結果：「Qiitaの元記事」と同様のグラフとなった。

LinkedListの処理時間遷移

なぜそうなるのか？

APIを確認したところ、下記の記述となっている。

ArrayListのAPI

size、isEmpty、get、set、iterator、および listIterator の処理は、一定の時間で実行されます。add の処理も、一定の償却時間で実行されます。つまり、n 個の要素を追加するには O(n) 時間が必要です。ほとんどの場合、ほかのすべての処理も比例的な時間で実行されます。定数の係数は、LinkedList の実装の場合より小さくなります。

→リストが増えると、それなりに処理時間は伸びるけどget自体の時間は変わらないよ。という解釈ができる。

LinkedListのAPI

すべてのオペレーションは、二重リンク・リストの場合に予期されるとおりの動作をします。リストをインデックスで処理するオペレーションは、リストの先端または終端のうち、指定したインデックスに近い方からリストをトラバースします。

→リストの先端、または終端から走査する。という解釈からは要素数の半分で先端からのアクセスから、末端からのアクセスに変化した事が伺えるし、グラフ結果からも同様の事象となる。

意図的にLinkedListを使用する場面があったら、上記懸念がある事は頭の片隅に入れておこうと思う。