5月 14

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
Tagged with:
3月 04

サーバのバッチ処理等で定期的に自動でJUnitを実行するためのメモです。JUnitのテストはGUIで実行すれば視覚的にわかりやすく、コマンドベースでも実行可能です。ただしこれらのテスト結果は、対人間のためのものであり、対プログラムというわけではありません。この記事では、JUnitのテスト結果をプログラムに対して伝える方法を説明します。

なお、本記事ではJUnit 3.8(junit-3.8.2.jar)の利用を想定しています。JUnit 4以降は異なる部分もありますので、ご注意ください。

続きを読む »

Tagged with:
10月 23

Windows7(64bit)へのJava SE 7 (JDK 7 Update 1) の開発環境のインストール方法について説明します。なお画像の一部はOracleのJavaのダウンロードサイトよりキャプチャさせていただき、引用させていただいております。

続きを読む »

Tagged with:
2月 20

CentOS5.5へのJ2SDK 1.4.2のインストールメモです。

続きを読む »

Tagged with:
11月 24

同じネットワーク上の別のパソコンを起動する方法としてWake On LANという仕組みがあります。これはWake On LANに対応したコンピュータ(BIOS,LANカード)に対し、マジックパケットという一定の規則に則ったデータを送信することにより、停止したコンピュータを起動することができます。詳しいことは以下のサイトを参考にしてください。

続きを読む »

Tagged with:
10月 11

M2EclipseのEclipse3.6へのインストールと設定手順です。M2EclipseはEclipseのJavaプロジェクトでMavenを利用するためのプラグインです。pom.xmlを読み込み、自動的にライブラリのクラスパスを設定します。なお事前にMavenのインストールが必要です。

続きを読む »

Tagged with:
10月 08

Java系のビルドツール「Maven」のインストール方法のメモです。ここではMaven2.2.1を利用します。

続きを読む »

Tagged with:
10月 08

Visual EditorのEclipse3.6へのインストール手順です。Visual EditorはSwingのGUIコンポーネントをマイクロソフトのVisual Studioのようにビジュアルなエディタで配置できるEclipseのプラグインです。
なお失敗が心配な人は、インストール前にEclipseのバックアップと変更したTomcatの設定ファイルのバックアップを取ったほうがよいでしょう。

続きを読む »

Tagged with:
10月 03

JavaのWebアプリケーションを構築した際に、ユーザ情報を管理することがあります。このときパスワードも管理することになりますが、パスワードを平文のままDBに入れるのはセキュリティの観点から好ましくありません。ここではCommons Codecを利用し、パスワードを簡単に暗号化する方法を説明します。

ハッシュを利用した認証

Commons Codecでは一方向ハッシュを実現するためのDigestUtilsクラスが用意されています。ハッシュとは、ある任意の値から、どのような値でも一様であり、衝突耐性のある値(ハッシュ値)を得ることです。また同じハッシュアルゴリズムであれば、元の値が同じであれば、ハッシュ値も同じです。例えば「ABCD」という値をハッシュ化し、「1234」というハッシュ値を得た場合、「ABCD」は何度ハッシュ化しても「1234」であり、「1234」をハッシュ値として持つ元の値を、発見することは限りなく困難です。

ハッシュは一方向に対してのみ有効であり、ハッシュ値から元の値を得ることはできません。実際にWebアプリケーションで認証をさせる場合は、パスワードをハッシュ値としてDBに入れ、認証時に入力された文字列から同一ハッシュアルゴリズムでハッシュ値を求め、ハッシュ値が一致を確認することで認証します。

Commons Codec

Commons CodecはApache Commonsプロジェクトの1プロジェクトです。OSSとして提供され、無償かつApache License 2.0のため、OSSの中でも比較的自由に利用可能です。

●対応するバージョン

バージョン Javaバージョン
1.3 1.2.2
1.4 1.4

 
●ハッシュ関連メソッド

DigestUtils
String md5Hex (String data)
          MD5でハッシュ化します。
String shaHex (String data)
          SHA-1でハッシュ化します。
String sha256Hex (String data)
          SHA-256でハッシュ化します。

サンプル

文字列からハッシュ値を求めるサンプルです。ここではMD5, SHA-1, SHA-256でハッシュ値を求めます。現状、この中ではSHA-256が一番強力なので、マシンパワーに余裕があればSHA-256を利用されることをお勧めします。

実行環境

  • Commons Codec:1.4
  • Java:6.0.21
例:文字列からハッシュ値を求める
import org.apache.commons.codec.digest.DigestUtils;

public class DigestUtilsSample {

    public static void main(String[] args) {
        String data = "test1234";

        //MD5でハッシュ
        System.out.println("MD5     = " + DigestUtils.md5Hex(data));

        //SHAでハッシュ
        System.out.println("SHA-1   = " + DigestUtils.shaHex(data));

        //SHA256でハッシュ
        System.out.println("SHA-256 = " + DigestUtils.sha256Hex(data));		
    }

}
実行結果
MD5     = 16d7a4fca7442dda3ad93c9a726597e4
SHA-1   = 9bc34549d565d9505b287de0cd20ac77be1d3f2c
SHA-256 = 937e8d5fbb48bd4949536cd65b8d35c426b80d2f830c5c308e2cdec422ae2244
Tagged with:
8月 10

Tomcat 6.0(6.0.29)のWindows7へのインストール方法を説明します。今回は複数バージョンのTomcatをインストールすることを想定し、インストーラによるインストールではなく、zipアーカイブによるインストールについて記述します。

続きを読む »