Arrays.binarySearchとHashSet.containsの比較

Arrays.binarySearchとHashSet.containsで、どちらの方が高速か比較してみました。

使ったコードは以下のようなもの。

package myproject.test;

import java.util.Arrays;
import java.util.HashSet;

public class PerformanceTest {

public static void main(String[] args) {
　// Arrays.binarySortとHashSet.containsの比較

　// 配列の宣言
　String[] arrays = {
　　"A", "M", "U", "W",
　};

　// 繰り返し回数
　int searchNum = 10000;

　// HashSetにも詰め込む
　HashSet<String> hashSet = new HashSet<String>();
　for (String str : arrays) {
　　hashSet.add(str);
　}

　　// ソートする
　　Arrays.sort(arrays);

　　// 開始時間記録
　　long jinrikiStartTime = System.nanoTime();

　　// 存在しないキーを繰り返し検索させる
　　for (int i = 0; i < searchNum; i++) {
　　　for(String key : arrays) {
　　　　if("Z".equals(key)) {
　　　　　System.out.println("Hit!!"); // ここには入らない
　　　　}
　　　}
　　}

　　// 終了時間記録
　　long jinrikiEndTime = System.nanoTime();

　　System.out.println("■■人力検索（Equalsで地道に）■■");
　　System.out.println("経過時間：" + (jinrikiEndTime - jinrikiStartTime));


　　// 開始時間記録
　　long binSrchStartTime = System.nanoTime();

　　// 存在しないキーを繰り返し検索させる
　　for (int i = 0; i < searchNum; i++) {
　　　Arrays.binarySearch(arrays, "Z");
　　}
　　// 終了時間記録
　　long binSrchEndTime = System.nanoTime();

　　System.out.println("");
　　System.out.println("■■Arrays.binarySearch■■");
　　System.out.println("経過時間：" + (binSrchEndTime - binSrchStartTime));

　　// 開始時間記録
　　long hashSetStartTime = System.nanoTime();

　　// 存在しないキーを繰り返し検索させる
　　for (int i = 0; i < searchNum; i++) {
　　　hashSet.contains("Z");
　　}
　　// 終了時間記録
　　long hashSetEndTime = System.nanoTime();

　　System.out.println("");
　　System.out.println("■■HashSet.contains■■");
　　System.out.println("経過時間：" + (hashSetEndTime - hashSetStartTime));

　}

}

ある配列 or HashSetの中に検索文字列が含まれるかを調べます。

今回は一番性能差が出ると思われる検索しても見つからない場合でやります。

比較対象として配列を地道に回してEqualsで比較させるのも入れました。

結果は以下のとおり

■■人力検索（Equalsで地道に）■■

経過時間：3381442

■■Arrays.binarySearch■■

経過時間：3765352

■■HashSet.contains■■

経過時間：1945013

困ったことにEqualsの方がbinarySearchより早くなってしまいました。笑

恐らく1文字だったのがまずかったのかな？

てことで一部変更

　　// 配列の宣言
　　String[] arrays = {
　　　　"ABCDEFGHIJKLMNOPQRSTUVWXY3", "ABCDEFGHIJKLMNOPQRSTUVWXY2",
　　　　"ABCDEFGHIJKLMNOPQRSTUVWXY4", "ABCDEFGHIJKLMNOPQRSTUVWXY1"
　　};

こんな感じの最後一文字だけ違うのを用意してみました。

で、実行結果がこちら

■■人力検索（Equalsで地道に）■■

経過時間：4698517

■■Arrays.binarySearch■■

経過時間：6636688

■■HashSet.contains■■

経過時間：2223253

あ、あれ？汗

予想と全然違います。

てゆーかbinarySearch遅い。

んー、これはちょっと理由を探る必要がありそうですね。

昔は早かったのかな？Equalsが早くなったのか？

ともあれ、HashSetはやはり早いので、キー値と一致するか調べるときなどはHashSetがよさそうですね。

もっとも、上記はすべてナノ秒ですから、よっぽどシビアでなければ気にする必要無さそうですが。