TL;DR
- 初心者向け
- 適切な探索方法を選んで、実行時間を短くする方法を学びましょう
- 単純な処理でも20億回実行したら0.5秒ぐらいかかります
- （なおDB接続を繰り返すと桁外れに時間がかかります）
主要な探索の種類とイメージ
- 線形探索
- 二分探索
- ハッシュ探索
mail_addressを指定してcustomerを検索する例を考えてみましょう
線形探索
- 対象データを順番に参照して、検索キーmail_addressが一致しているか調べます
計算量
1024件のデータがあれば1024回参照します。愚直。
O(n)
二分探索
- mail_addressで全体をソートします
- 真ん中辺りのデータを参照して、一致しているか調べます
- 一致していなければ半分を捨てて、残りの半分の真ん中を参照します
- 一種の分割統治法
計算量
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を見つける際に、追加の処理は必要ありません（実装例：ハッシュテーブル）
計算量
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実装・計測
探索の実装前に
単純な処理分岐でも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];
// １人ずつ
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