単純な処理で思わぬ性能問題が出た話

Listに重複がある場合に出力するという、Java初心者練習用のようなプログラム。

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        List list = Arrays.asList("yamada", "nakamura", "aoki", "yamada", "shimizu", "nakamura");

        Iterator it = list.iterator();
        List list2 = new ArrayList<String>();
        while(it.hasNext())
        {
            String name = (String)it.next();
            if( list2.contains(name)){
                System.out.println(name);
            } else {
                list2.add(name);
            }
        }
    }
}

実行結果
yamada
nakamura


だが、これと同様のプログラム構造のバッチ処理の性能試験にて、Listの件数が10万件、20万件・・・となった際に、処理速度が指数関数的（比例ではない）に遅くなるという問題が起きた。
なぜ、指数関数的に遅くなる・・・？

当初、ヒープの枯渇によるGC連発を疑ったが、そうではなかった。

list2.contains(name)の部分の処理が、list2の件数に比例して遅くなるのが原因だった。
まあそりゃそうか、内部的には全件なめるんだろうしな・・・。
なので、ループの回数と、list2.contains(name)の1回あたりの処理が両方件数に比例するので、比例×比例で二乗になっていた。

賢明な皆さんは一瞬で気づいたかもしれないが、小一時間悩んでしまった。orz