Help us understand the problem. What is going on with this article?

探索の基礎とJava実装・計測

TL;DR

  • 初心者向け
  • 適切な探索方法を選んで、実行時間を短くする方法を学びましょう
  • 単純な処理でも20億回実行したら0.5秒ぐらいかかります
    • (なおDB接続を繰り返すと桁外れに時間がかかります)

主要な探索の種類とイメージ

  • 線形探索
  • 二分探索
  • ハッシュ探索

mail_addressを指定してcustomerを検索する例を考えてみましょう

線形探索

  • 対象データを順番に参照して、検索キーmail_addressが一致しているか調べます

out.gif

計算量

1024件のデータがあれば1024回参照します。愚直。

O(n)

二分探索

  • mail_addressで全体をソートします
  • 真ん中辺りのデータを参照して、一致しているか調べます
  • 一致していなければ半分を捨てて、残りの半分の真ん中を参照します
  • 一種の分割統治法

out.gif

計算量

1024件 = 2^10件 = 2*2*2*2*2*2*2*2*2*2件を半分ずつ捨てながら見るので、
最大でも10個のデータを参照すれば見つかります。賢い。

O(\log n)

※計算機科学で言うlogの底は2です。 2^(log n) = n です

ハッシュ法

  • 対象データ全てのmail_addressをハッシュ関数に渡して一定のルールで変換し、ハッシュ値を得ます
  • 検索キーのmail_addressも同じハッシュ関数に渡して、同じルールで変換し、ハッシュ値を得ます
  • ハッシュ値の一致するデータを参照します
  • 対象データのハッシュ値の塊から指定したハッシュ値xxxを見つける際に、追加の処理は必要ありません(実装例:ハッシュテーブル

out.gif

計算量

1024件でもハッシュ関数を1度経由すれば、対象データを直接参照できます

O(1)

欠点

一般的に、アルゴリズムは実行時間短縮とメモリ消費低減のトレードオフです
両方が悪い実装は存在しますし、作れますが、
それぞれで同時に最高のパフォーマンスを出すアルゴリズムは存在しないでしょう
ハッシュ法もご多分に漏れず、メモリを食います

データベースで使われているのは?

PostgreSQL 実行計画(explain, explain analyze)

  • Seq Scan: 線形探索
  • Index Scan: 二分探索っぽいもの
  • Hash ~: ハッシュ法

PostgreSQL Index Only Scan 奮闘記 その3 | TECHSCORE BLOG
【SQL】ゼロ知識から実行計画を読み解きパフォーマンス改善 - Qiita
EXPLAIN - PostgreSQL 10.5文書

Java実装・計測

探索の実装前に

キャプチャ.PNG

単純な処理分岐でも20億回実行したら0.61秒かかります

ベースにするソースコード

100000人のcustomerを用意して、メールアドレスを1000回検索してみましょう。
https://ideone.com/w0hDzg

検索処理を入れる場所(TODO)が未実装の状態で0.9秒です。

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        // n人分のデータを作り
        int n = 100000;
        Random rand = new Random();
        String[][] customer = new String[n][2];
        for (int i = 0; i < n; i++)
            customer[i][0] = String.valueOf((char) (rand.nextInt(26)+'a')) + i + "@ab.com";
        for (int i = 0; i < n; i++)
            customer[i][1] = i + "さん";

        // メールアドレスでソートします
        Arrays.sort(customer, (c1, c2) -> c1[0].compareTo(c2[0]));

        // キーをメールアドレス、値を名前としたハッシュマップも作ります
        Map<String, String> hashmap = new HashMap<>(n);
        for (String[] c : customer)
            hashmap.put(c[0], c[1]);

        // 同じcustomer(101番目)の名前が取れる
        System.out.println(customer[101][0] + "の名前は" + customer[101][1]);
        // ハッシュマップからメールアドレスで取ることもできる
        System.out.println(customer[101][0] + "の名前は" + hashmap.get(customer[101][0]));
        System.out.println("確認終わり");

        // では、m人分のメールアドレスを適当に選んで
        int m = 1000;
        String[] keys = new String[m];
        for (int j = 0; j < m; j++)
            keys[j] = customer[rand.nextInt(n)][0];

        // 1人ずつ
        for (int j = 0; j < m; j++){
            String key = keys[j];
            // 検索してみましょう

            // TODO
            String found = null;

            if (j % 100 == 0) {
                System.out.println(key + "の名前は" + Objects.toString(found, "不明"));
            }
        }
    }
}

線形探索

3.9秒です。遅い!
https://ideone.com/GIle7V

// TODOだった場所
String found = null;
for (int i = 0; i < n; i++) {
    if (Objects.equals(key, customer[i][0])) {
        found = customer[i][1];
    }
}

二分探索

1秒です。そもそもデータ用意が0.9秒だったので、検索自体にほとんど時間がかかっていません
https://ideone.com/eF7Txv

// TODOだった場所
String found = null;
keyCustomer[0] = key;
int index = Arrays.binarySearch(customer, keyCustomer, (c1, c2) -> c1[0].compareTo(c2[0]));
found = customer[index][1];

ハッシュ法

0.93秒です。ほぼ全く時間がかかりません
https://ideone.com/67PzQP

// TODOだった場所
String found = null;
found = hashmap.get(key);

二分探索(1024倍)

二分探索とハッシュ法の差が誤差レベルだったので、
検索回数(m)を1024倍にして比較してみましょう。
二分探索は1.69秒です。
https://ideone.com/ppG31d

ハッシュ法(1024倍)

ハッシュ法の検索回数(m)も1024倍にしてみましょう。
1.16秒です。
https://ideone.com/ppG31d
二分探索よりも、検索キーの増加に対して実行時間の伸びが緩やか。計算量の差です

探索って実際に開発で使うの?

 初学者が意識する機会は少ないでしょうが、利用しています。
 データベースで注文履歴一覧を検索する状況を考えてみましょう。SQLでcustomer顧客テーブル(1万件超)にorder注文テーブル(1万件超)とorder_detail注文明細テーブル(1万件超)を結合して明細を取得して、さらにproduct商品テーブル(1万件超)を結合して商品名を取得します。
 あなたがこのSQLを実行して現実的な時間で終了するのであれば、DB管理者が適切な主キー制約/一意制約/インデックスなどを設定して、DBがそれに基づいて二分探索(っぽいもの)に使う木構造データやハッシュ法に使うハッシュ表を事前に用意して、SQL実行時に利用されているのでしょう。
 なお現場では、DB定義が抜けているために処理が遅い/SQLのテーブル結合条件が複雑なため線形探索しかできず、遅い/本番環境で動かすまでそれらの問題に気づかない/改善余地はあるが放置される、といった不幸な状況が多く発生します。
 あなたの担当の外にも疑わしい箇所がある、ということは知っておいてください。

Hope this helps.


その他、参考

線形探索(リニアサーチ)とは - IT用語辞典 e-Words
二分探索(2分探索)とは - IT用語辞典 e-Words
ハッシュ法(ハッシュ探索)とは - IT用語辞典 e-Words
線型探索 - Wikipedia
二分探索 - Wikipedia

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした