Javaのオブジェクトを探せ！基本アルゴリズムの二分探索で高速化しよう。

#Java

記事をシェア：

コピー

こんにちは。ぐっさんです。

ORマッピングがデータベースアクセスの主流となってきた昨今ですが、大量データを取得し、その中から対象のオブジェクトを抽出するということが増えてきたと思います。

データが増えれば増えるほど、抽出ロジックがボトルネックになってきます。
二分探索は、データが増えれば増えるほど効果が表れてきます。

二分探索
ソート済みのリストや配列に入ったデータ（同一の値はないものとする）に対する検索を行うにあたって、中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。

— wikipedia「二分探索」

そこで、二分探索と通常の抽出の時間を比較したサンプルを作ってみました。

二分探索と通常の抽出の比較サンプル

1000万件のデータリストの中から、ランダムで選択されたIDのオブジェクトを抽出するサンプルです。

package jp.amg_solution.blog.sample;

import java.util.ArrayList;
import java.util.List;

public class BinarySearchBlogSample {

  public static void main(String[] args) {

    // 10000000件のデータリストを作成
    List<BinarySearchBlogSampleData> sampleDataList = new ArrayList<BinarySearchBlogSampleData>();
    for (int i=0; i<10000000; i++) {
      BinarySearchBlogSampleData sampleData = new BinarySearchBlogSampleData();
      sampleData.id = i;
      sampleData.label = "label" + String.format("%05d",  i);
      sampleDataList.add(sampleData);
    }

    // ランダムで検索するIDを取得
    int targetID = (int)(Math.random() * 10000000);
    System.out.println("Target       : " + targetID);

    BinarySearchBlogSampleData searchData = null;

    // 上から順に検索
    long start = System.currentTimeMillis();
    searchData = normalSearch(targetID,  sampleDataList);
    System.out.println("=========== NORMAL SEARCH ===========");
    System.out.println("Result ID    : " + searchData.id);
    System.out.println("Result Label : " + searchData.label);
    System.out.println("Time         : " + searchData.id);
    System.out.println("Time         : " + (System.currentTimeMillis() - start) + "ms");

    // 二分探索で検索
    start = System.currentTimeMillis();
    searchData = binarySearch(targetID,  sampleDataList);
    System.out.println("=========== BINARY SEARCH ===========");
    System.out.println("Result ID    : " + searchData.id);
    System.out.println("Result Label : " + searchData.label);
    System.out.println("Time         : " + (System.currentTimeMillis() - start) + "ms");

  }

  /**
   * 二分探索による検索
   * @param targetID - 検索するID
   * @param sampleDataList - 検索対象リスト
   * @return 検索されたデータ
   */
  private static BinarySearchBlogSampleData binarySearch(int targetID,  List<BinarySearchBlogSampleData> sampleDataList) {
    int startIndex = 0;
    int endIndex = sampleDataList.size() - 1;

    while (startIndex <= endIndex) {
      int midIndex = (startIndex + endIndex) / 2;
      BinarySearchBlogSampleData midData = sampleDataList.get(midIndex);
      if (midData.id == targetID) {
        return midData;
      } else if (midData.id < targetID) {
        startIndex = midIndex + 1;
      } else {
        endIndex = midIndex - 1;
      }
    }

    return null;
  }

  /**
   * 通常の検索
   * @param targetID - 検索するID
   * @param sampleDataList - 検索対象リスト
   * @return 検索されたデータ
   */
  private static BinarySearchBlogSampleData normalSearch(int targetID,  List<BinarySearchBlogSampleData> sampleDataList) {
    for (BinarySearchBlogSampleData sampleData : sampleDataList) {
      if (sampleData.id == targetID) {
        return sampleData;
      }
    }
    return null;
  }

}

実行結果は、下記の通りです。

Target : 7706200
=========== NORMAL SEARCH ===========
Result ID : 7706200
Result Label : label7706200
Time : 7706200
Time : 64ms
=========== BINARY SEARCH ===========
Result ID : 7706200
Result Label : label7706200
Time : 0ms

おお！実行時間が全然違いますね。
通常の探索だと64msかかっているところが、二分探索だと0msです。

サンプルの50行目から67行目が実際の二分探索のロジックになります。
idの値が、中間インデックスのデータと比較して、リストの前後のどちらにあるか判定します。
その判定をもとに、開始インデックスもしくは終了インデックスを調整することがポイントです。
また、二部探索を使う場合は、ソートしている必要があるので注意が必要です。