Java:Listの高速化(contains vs indexOf)

2013年05月14日 22時49分 Java • Tags: , ,




contains vs indexOf

Listに指定したオブジェクトが含まれているかをチェックするメソッドとしてcontainsとindexOfが用意されています。どちらもnullもしくはequalsで一致するオブジェクトがListに含まれるかを走査しています。

List (ArrayList, Vector, LinkedList)
boolean contains (Object o)
          リストに指定された要素が含まれている場合に true を返します。
int indexOf (Object o)
          指定された要素がリスト内で最初に検出された位置のインデックスを返します。指定された要素がリストにない場合は -1 を返します。

さて、それではどちらのメソッドを利用するほうがパフォーマンスがよいのでしょうか?結論を言うとどちらを利用しても同じです。ソースコードが公開されているため、ソースコードを見てみましょう。

※JDK7.0_17より

ArrayList(Vectorもsynchronized以外はほぼ同じ)
public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}
LinkedList
public boolean contains(Object o) {
    return indexOf(o) != -1;
}

public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

念のためプログラムを組んで検証してみます。

  • 検証①:"0"~"9999"の文字列のリストから"0"、"5000"、"9999"を探す
  • 検証②:"0"を10000個追加した文字列のリストから"0"、"1"を探す
  • 探す回数は1000万回とする
  • これらを5回行い、上限と下限を除き平均値をとる
  • ListオブジェクトにはArrayListを用いる
  • Eclipse上で実行し、実行環境のJ2SE-1.4(jre7)、コンパイラを1.4準拠とする

検証プログラムはこちら

計測結果はこのようになりました。

検索値 contains indexof
検証①0 46.6ms 46.6ms
検証①5,000 146583.0ms 147862.3ms
検証①9,999 320877.0ms 315328.6ms
検証②0 15.6ms 16.0ms
検証②1 341562.6ms 341848.6ms

こんなことに拘るなら、少しでもメモリを節約するプログラムを作るとか、適切なListオブジェクトを選択するとか、他のことに注力したほうがよいでしょう。

検証用プログラム

検証:containsとindexOfの速度比較
import java.util.ArrayList;
import java.util.List;

public class ListPerformance {

    public static void main(String[] args) {

        int num = 5;
        System.out.println("検証①:対象のリスト位置による違い");
        System.out.println("・\"0\"~\"9999\"の文字列のリストから\"0\"、\"5000\"、\"9999\"を探す");
        List list = new ArrayList();
        for (int i = 0; i < 10000; i++) {
            list.add(String.valueOf(i));
        }
        long[][] times = new long[6][num];
        for (int i = 0; i < num; i++) {
            for (int no = 0; no < 6; no++) {
                long start = System.currentTimeMillis();
                search(list, no);
                long end = System.currentTimeMillis();
                times[no][i] = end - start;
            }
        }

        for (int no = 0; no < 6; no++) {
            for (int i = 0; i < num; i++) {
                if (no == 0) {
                    System.out.println("contains 0(先頭) " + (i + 1) + "回目:" + times[no][i]);
                } else if (no == 1) {
                    System.out.println("indexOf 0(先頭) " + (i + 1) + "回目:" + times[no][i]);
                } else if (no == 2) {
                    System.out.println("contains 5000(中) " + (i + 1) + "回目:" + times[no][i]);
                } else if (no == 3) {
                    System.out.println("indexOf 5000(中) " + (i + 1) + "回目:" + times[no][i]);
                } else if (no == 4) {
                    System.out.println("contains 9999(末尾) " + (i + 1) + "回目:" + times[no][i]);
                } else if (no == 5) {
                    System.out.println("indexOf 9999(末尾) " + (i + 1) + "回目:" + times[no][i]);
                }
            }
        }

        System.out.println("");
        System.out.println("検証②:リスト中の対象の有無の違い");
        System.out.println("・\"0\"を10000個追加した文字列のリストから\"0\"、\"1\"を探す");
        list = new ArrayList();
        for (int i = 0; i < 10000; i++) {
            list.add("0");
        }
        times = new long[4][num];
        for (int i = 0; i < num; i++) {
            for (int no = 0; no < 4; no++) {
                long start = System.currentTimeMillis();
                search2(list, no);
                long end = System.currentTimeMillis();
                times[no][i] = end - start;
            }
        }

        for (int no = 0; no < 4; no++) {
            for (int i = 0; i < num; i++) {
                if (no == 0) {
                    System.out.println("contains 0(ある) " + (i + 1) + "回目:" + times[no][i]);
                } else if (no == 1) {
                    System.out.println("indexOf 0(ある) " + (i + 1) + "回目:" + times[no][i]);
                } else if (no == 2) {
                    System.out.println("contains 1(ない) " + (i + 1) + "回目:" + times[no][i]);
                } else if (no == 3) {
                    System.out.println("indexOf 1(ない) " + (i + 1) + "回目:" + times[no][i]);
                }
            }
        }
    }

    public static void search(List list, int no) {
        String str1 = "0";
        String str2 = "5000";
        String str3 = "9999";
        int num = 10000000;
        if (no == 0) {
            for (int i = 0; i < num; i++) {
                if (list.contains(str1)) {
                }
            }
        } else if (no == 1) {
            for (int i = 0; i < num; i++) {
                if (list.indexOf(str1) != -1) {
                }
            }
        } else if (no == 2) {
            for (int i = 0; i < num; i++) {
                if (list.contains(str2)) {
                }
            }
        } else if (no == 3) {
            for (int i = 0; i < num; i++) {
                if (list.indexOf(str2) != -1) {
                }
            }
        } else if (no == 4) {
            for (int i = 0; i < num; i++) {
                if (list.contains(str3)) {
                }
            }
        } else if (no == 5) {
            for (int i = 0; i < num; i++) {
                if (list.indexOf(str3) != -1) {
                }
            }
        }
    }

    public static void search2(List list, int no) {
        String str1 = "0";
        String str2 = "1";
        int num = 10000000;
        if (no == 0) {
            for (int i = 0; i < num; i++) {
                if (list.contains(str1)) {
                }
            }
        } else if (no == 1) {
            for (int i = 0; i < num; i++) {
                if (list.indexOf(str1) != -1) {
                }
            }
        } else if (no == 2) {
            for (int i = 0; i < num; i++) {
                if (list.contains(str2)) {
                }
            }
        } else if (no == 3) {
            for (int i = 0; i < num; i++) {
                if (list.indexOf(str2) != -1) {
                }
            }
        }
    }
}

検証①:実行結果
検証①:対象のリスト位置による違い
・"0"~"9999"の文字列のリストから"0"、"5000"、"9999"を探す
contains 0(先頭) 1回目:62
contains 0(先頭) 2回目:47
contains 0(先頭) 3回目:47
contains 0(先頭) 4回目:32
contains 0(先頭) 5回目:46
indexOf 0(先頭) 1回目:63
indexOf 0(先頭) 2回目:46
indexOf 0(先頭) 3回目:47
indexOf 0(先頭) 4回目:46
indexOf 0(先頭) 5回目:47
contains 5000(中) 1回目:146874
contains 5000(中) 2回目:146313
contains 5000(中) 3回目:147530
contains 5000(中) 4回目:145767
contains 5000(中) 5回目:146562
indexOf 5000(中) 1回目:148091
indexOf 5000(中) 2回目:147717
indexOf 5000(中) 3回目:148995
indexOf 5000(中) 4回目:147779
indexOf 5000(中) 5回目:146875
contains 9999(末尾) 1回目:323061
contains 9999(末尾) 2回目:321953
contains 9999(末尾) 3回目:321345
contains 9999(末尾) 4回目:319333
contains 9999(末尾) 5回目:317694
indexOf 9999(末尾) 1回目:314247
indexOf 9999(末尾) 2回目:320003
indexOf 9999(末尾) 3回目:312609
indexOf 9999(末尾) 4回目:317679
indexOf 9999(末尾) 5回目:314060

検証②:リスト中の対象の有無の違い
・"0"を10000個追加した文字列のリストから"0"、"1"を探す
contains 0(ある) 1回目:16
contains 0(ある) 2回目:16
contains 0(ある) 3回目:15
contains 0(ある) 4回目:15
contains 0(ある) 5回目:16
indexOf 0(ある) 1回目:16
indexOf 0(ある) 2回目:16
indexOf 0(ある) 3回目:16
indexOf 0(ある) 4回目:16
indexOf 0(ある) 5回目:15
contains 1(ない) 1回目:342343
contains 1(ない) 2回目:341718
contains 1(ない) 3回目:342140
contains 1(ない) 4回目:340673
contains 1(ない) 5回目:340830
indexOf 1(ない) 1回目:343044
indexOf 1(ない) 2回目:340705
indexOf 1(ない) 3回目:342327
indexOf 1(ない) 4回目:340658
indexOf 1(ない) 5回目:342514


Leave a Reply

preload preload preload