コレクションクラスの処理速度について

#1. はじめに
エンジニアとして入社してから今までは主にJavaの開発を携わっていきました。
最近では処理のパフォーマンスに対しても考えないといけない場面に遭遇することもあったため、
簡単な内容となりますが今一度自分の復習も込めて、コレクションクラスでよく使われているListを例に、
それぞれの実行速度についてまとめてみます。

#2. ArrayListとLinkedList
それぞれの主な特徴として、
ArrayList ：要素にアクセスするスピードが早い
LinkedList ：要素に挿入したり削除するスピードが早い
が挙げられてます。

今回は上記二つを例にし、処理の実行速度の計測を行います。

##要素の追加(add)
まずは100万の要素を追加する場合の作成速度について比較します。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class App {
    public static void main(String[] args) throws Exception {
        //ArrayList インスタンスの生成
        List<String> sampleArrayList = new ArrayList<>();
        //LinkedList インスタンスの生成
        List<String> sampleLinkedList = new LinkedList<>();
        /**
         * 値の追加(100万回addを行う) 
         */
        //ArrayList
        long tBefore1_1 = System.currentTimeMillis();
        for (int i = 0 ; i < 1000000; i++) {
            sampleArrayList.add("Add Object");
        }
        long tAfter1_1 = System.currentTimeMillis();
        System.out.println("ArrayList(追加):" +(tAfter1_1 - tBefore1_1)+ "ms");
        //LinkedList
        long tBefore1_2 = System.currentTimeMillis();
        for (int i = 0 ; i < 1000000; i++) {
            sampleLinkedList.add("Add Object");
        }
        long tAfter1_2 = System.currentTimeMillis();
        System.out.println("LinkedList(追加):" +(tAfter1_2 - tBefore1_2)+ "ms");
    }
}

実行結果(ミリ秒単位)

項目名	1回目	2回目	3回目	平均
ArrayList	17ms	18ms	18ms	17.6ms
LinkedList	112ms	110ms	103ms	108.3ms

要素の追加に対して、ArrayListの方が圧倒的に早いことが分かりました。

##要素の挿入(add)
次に、100万の要素があるListに対し、指定したインデックスへ10万回addした時の速度を計ってみます。
上記のソースに以下を記載

        /**
         * 値の挿入
         */
        //ArrayList
        long tBefore2_1 = System.currentTimeMillis();
        for (int i = 0 ; i < 100000; i++) {
            //100件目に対して追加
            sampleArrayList.add(100,"Add Object2");
        }
        long tAfter2_1 = System.currentTimeMillis();
        System.out.println("ArrayList(挿入):" +(tAfter2_1 - tBefore2_1)+ "ms");

        //LinkedList
        long tBefore2_2 = System.currentTimeMillis();
        for (int i = 0 ; i < 100000; i++) {
            //100件目に対して追加
            sampleLinkedList.add(100,"Add Object2");
        }
        long tAfter2_2 = System.currentTimeMillis();
        System.out.println("LinkedList(挿入):" +(tAfter2_2 - tBefore2_2)+ "ms");

実行結果(ミリ秒単位)

項目名	1回目	2回目	3回目	平均
ArrayList	25281ms	19892ms	22100ms	22424.3ms
LinkedList	104ms	82ms	75ms	87ms

もともとあった要素に対しての挿入は、LinkedListの方が早いことが分かりました。

##要素の更新(set)
次に、110万の要素があるListに対して、30万回setした場合の速度を計ります。

        /**
         * 値の更新
         */
        //ArrayList
        long tBefore3_1 = System.currentTimeMillis();
        for (int i = 0 ; i < 300000; i++) {
            sampleArrayList.set(i,"Upd Object");
        }
        long tAfter3_1 = System.currentTimeMillis();
        System.out.println("ArrayList(更新):" +(tAfter3_1 - tBefore3_1)+ "ms");

        //LinkedList
        long tBefore3_2 = System.currentTimeMillis();
        for (int i = 0 ; i < 300000; i++) {
            sampleLinkedList.set(i,"Upd Object");
        }
        long tAfter3_2 = System.currentTimeMillis();
        System.out.println("LinkedList(更新):" +(tAfter3_2 - tBefore3_2)+ "ms");

実行結果(ミリ秒単位)

項目名	1回目	2回目	3回目	平均
ArrayList	9ms	6ms	7ms	7.3ms
LinkedList	97959ms	110058ms	111965ms	106660.6ms

更新については、圧倒的にArrayListが早いことが分かりました。

##要素の取得(get)
次に、110万の要素があるListに対して、30万回getした場合の速度を計ります。

        /**
         * 値の取得 
         */
        //ArrayList
        long tBefore4_1 = System.currentTimeMillis();
        for (int i = 0 ; i < 300000; i++) {
            sampleArrayList.get(100000);
        }
        long tAfter4_1 = System.currentTimeMillis();
        System.out.println("ArrayList(取得):" +(tAfter4_1 - tBefore4_1)+ "ms");

        //LinkedList
        long tBefore4_2 = System.currentTimeMillis();
        for (int i = 0 ; i < 300000; i++) {
            sampleLinkedList.get(100000);
        }
        long tAfter4_2 = System.currentTimeMillis();
        System.out.println("LinkedList(取得):" +(tAfter4_2 - tBefore4_2)+ "ms");

実行結果(ミリ秒単位)

項目名	1回目	2回目	3回目	平均
ArrayList	6ms	7ms	5ms	6ms
LinkedList	41485ms	42740ms	42825ms	42343.3ms

取得についてもArrayListが格段に早いことが分かりました。

##値のソート
今までの要素をソートした場合の速度を計測します。

        /**
         * 値のソート
         */
        //ArrayList
        long tBefore5_1 = System.currentTimeMillis();
        Collections.sort(sampleArrayList);
        long tAfter5_1 = System.currentTimeMillis();
        System.out.println("ArrayList(ソート):" +(tAfter5_1 - tBefore5_1)+ "ms");

        //LinkedList
        long tBefore5_2 = System.currentTimeMillis();
        Collections.sort(sampleLinkedList);
        long tAfter5_2 = System.currentTimeMillis();
        System.out.println("LinkedList(ソート):" +(tAfter5_2 - tBefore5_2)+ "ms");

実行結果(ミリ秒単位)

項目名	1回目	2回目	3回目	平均
ArrayList	21ms	19ms	17ms	19ms
LinkedList	46ms	46ms	43ms	45ms

これと言って大きな差はなく、ArrayListの方が少し早いことが分かりました。

##値の削除(remove)
最後に110万の要素に対し、30万回removeした時の実行速度を計ります。

        /**
         * 値の削除
         */
        //ArrayList
        long tBefore6_1 = System.currentTimeMillis();
        for (int i = 0 ; i < 300000; i++) {
            sampleArrayList.remove(10000);
        }
        long tAfter6_1 = System.currentTimeMillis();
        System.out.println("ArrayList(削除):" +(tAfter6_1 - tBefore6_1)+ "ms");

        //LinkedList
        long tBefore6_2 = System.currentTimeMillis();
        for (int i = 0 ; i < 300000; i++) {
            sampleLinkedList.remove(10000);
        }
        long tAfter6_2 = System.currentTimeMillis();
        System.out.println("LinkedList(削除):" +(tAfter6_2 - tBefore6_2)+ "ms");

実行結果(ミリ秒単位)

項目名	1回目	2回目	3回目	平均
ArrayList	64640ms	59437ms	59261ms	61112.6ms
LinkedList	3607ms	3712ms	3579ms	3632.6ms

削除処理についてはLinkedListの方が圧倒的に早いです。

#3.処理の組み合わせ
これまで単体の機能としての実行速度を計測してきましたが、
次に各処理を組み合わせた場合、どれくらいの速度なのかを見てみます。
一例として、100万件のListを作成したあとに1000件の挿入を行うパターンを上記の平均速度を元に机上で計算してみました。

項目名	追加速度(100万件)	挿入速度(1000件)	合計
ArrayList	17.6ms	308ms	325.6ms
LinkedList	108.3ms	3ms	111.3ms

たった1000件を挿入するだけでも全体としてはLinkedListを使用したほうが性能がよいことがわかりました。

#4.まとめ
単体の性能だけで語られることが多いため、直近の処理のみでどちらを選択するかを判断してしまうことが多いですが、
実際は単体の処理のみで使用されるのは少ないため、処理全体でどのように使うかでどちらを選択すべきか判断するべきだと思います。

#5.最後に
今回例に挙げたListだけに限らず、他でも同様の場面が考えられるため、
視野を広げて物事を判断する能力を培いたいと思いました。