Javaのリスト速度対決

配列、ArrayList、LinkedListの速度対決をしてみました。
データ構造とアルゴリズムを習ってからずっと気になっていたんですが、
今必要に迫られて計測してみました。

条件

  • 要素数は7990272個です(中途半端)
  • for文を回す時間を計測します。初期化部分は含めません。
  • 要素はint(Integer)型です。
  • i: 0から7990271を動くindexです。
  • MAX: 7990272
  • 「10回だけ」とか指定がなければMAX回for文を回しています。

配列
普通の配列は速いですが、あとから追加・削除はできません。

  • 代入 14ms
  • 取得 14ms

ArrayList
ArrayListは以前からよく使っていました。
要素の取得は、普通の配列と遜色ない速さで嬉しいです。
要素の追加は、LinkedListより速いですね。
要素の削除は、先頭からやると、7990272回配列をコピーすることになるので、とんでもない時間がかかるようです。
末尾を削除するなら、LinkedListとほぼ同じ時間でできました。

  • add  226ms
    • ※要素を末尾に追加します
  • get(i) 19ms
    • ※指定したインデックスの要素を取得します
  • remove(0) 終わらないのであきらめた
    • ※指定したインデックスの要素を削除します
    • 一番遅いと思われる0番目を削除し続けました(1回ずつ配列を作り直すため)
  • remove(MAX – i – 1) 66ms
    • ※指定したインデックスの要素を削除します
    • 一番速いと思われる末尾の要素を削除し続けました
  • remove(3000000)を10回だけ 22ms
    • 真ん中へんの要素(3000000番目)を削除しました
    • めちゃくちゃ時間がかかりそうなので、10回だけやりました(この結果から7990272回やると恐ろしい時間がかかるのが分かります)

LinkedList
LinkedListは、普通に全ての要素を取得しようとするととんでもない時間がかかります。
先頭・末尾から削除しつつ取得すれば、かなり速く取得できます。
要素の追加は何故かArrayListより時間がかかるようです。

  • add  1070ms
    • ※要素を末尾に追加します
  • offer 1335ms
    • ※要素を末尾に追加します
  • push 1417ms
    • ※要素を先頭に追加します
  • pollFirst 55ms
    • ※先頭の要素を取得して削除します
  • pollLast 58ms
    • ※末尾の要素を取得して削除します
  • removeFirst 58ms
    • ※先頭の要素を取得して削除します
  • removeLast 69ms
    • ※末尾の要素を取得して削除します
  • get(i) 終わらないので諦めた
    • ※指定したインデックスの要素を取得します
  • remove(3000000)を10回だけ 87ms
    • 真ん中へんの要素(3000000番目)を削除しました
    • LinkedListの参照を3000000回たどる方が、ArrayListをコピーするよりも時間がかかることが分かります。

まとめ

  • もちろん普通の配列は速い。
  • でもArrayListを多用しても平気そう。特に要素の取得は普通の配列に迫る速さ。
  • 普通はわざわざLinkedListを使う必要はなさそう。要素の追加が遅いし、要素を削除せずに取得する方法は遅くて使えない。要素を削除する場合も、末尾から削除する場合はArrayListでも速い。中途半端な部分を削除する場合もArrayListを使った方がよさそう。
  • 先頭から削除する場合のみLinkedListを使う。

Leave a Reply

Your email address will not be published. Required fields are marked *

CAPTCHA