大量データを扱うときはArrayListよりHashSetを使おう

最近は性能問題が徐々に収束してきました。
解決された問題のうちの1つをここで紹介したいと思います。

「あるバッチプログラムの性能要件が100万件のデータを60分で処理しないといけない」というものがあったのですが、計測してみると2.5時間で40万件弱しか処理できないという問題がありました。(このデータから100万件にかかる時間を算出すると17時間。。。)

このバッチプログラム、最初の15分間は処理量が6500件だったのに、時間が経過していくとどんどん劣化し、3時間経過で800件前後となり、その後は徐々に劣化していく、かなりお粗末なプログラムでした。

メモリリークは発生していなかったので、ログを埋め込んで時間のかかっている処理を切り分けていくとDBから取得したデータをArrayListに格納し、それを存在チェックしている箇所(ArrayList#contains)がボトルネックであることが判明しました。

存在チェックをしているcontainsメソッドが同様に用意されているHashSetに書き換えて計測すると100万件データの処理時間が下記の通りとなりました。

  • 変更前(ArrayListを使った場合) 約17時間
  • 変更後(HashSetを使った場合) 約50分

ArrayListをHashSetに変えただけで約1/20の処理時間となり、劇的に改善されました。
大量データを扱うときはArrayListとHashSetでこれほど性能に違いがあることが分かりました。
そこで無駄な処理を省いて純粋にArrayList#containsとHashSet#containsを使ったプログラムを計測してみました。

public class Sample {
    private static final SimpleDateFormat sdf = 
    new SimpleDateFormat("yyyy/MM/dd HH:mm:ss.SSS");
    private static final int LOOP_COUNT = 100000;
   
    public static void main(final String[] args) {
        HashSet<Integer> set = new HashSet<Integer>();
        ArrayList<Integer> list = new ArrayList<Integer>();

        for(int i = 0; i < LOOP_COUNT; i++){
            list.add(i);
        }

        log("ArrayList start");
        for(int iList : list){
            if(list.contains(iList)){
                // Nothing is done.
            }
        }
        log("ArrayList end");
       
        for(int i = 0; i < LOOP_COUNT; i++){
            set.add(i);
        }
        log("HashSet start");
        for(int iSet : set){
            if(set.contains(iSet)){
                // Nothing is done.
            }
        }
        log("HashSet end");       
    }
   
    public static void log(final String str){
        System.out.println(sdf.format(new Date().getTime()) + " " + str);
    }
}

結果

2009/01/14 12:05:20.195 ArrayList#contains start
2009/01/14 12:06:28.492 ArrayList#contains end
2009/01/14 12:06:28.601 HashSet#contains start
2009/01/14 12:06:28.617 HashSet#contains end

まとめ
ArrayList#containsは約1分に対し、HashSet#containsは16ミリ秒。これだけでも十分に大きな差があることが分かります。ArrayListは追加された要素を1列のリストに格納していくため要素を取り出すときは、リストの先頭から順番に要素を取り出すのに対し、HashSetはhashCodeの値を元に、そのhashCodeの値を採番している格納先から対象となるオブジェクトを探しに行くので、大量データを扱うときにはArrayListとHashSetの性能に大きな違いが表れるようです。