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

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

# 主要な探索の種類とイメージ
- 線形探索
- 二分探索
- ハッシュ探索

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

## 線形探索

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

![out.gif](https://qiita-image-store.s3.amazonaws.com/0/368897/348851a7-1c3b-fad4-c74e-6a49f89e26f0.gif)

#### [計算量](https://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%82%A6%E3%81%AE%E8%A8%98%E5%8F%B7#%E4%B8%80%E8%88%AC%E7%9A%84%E3%81%AA%E3%82%AA%E3%83%BC%E3%83%80%E3%83%BC)
1024件のデータがあれば1024回参照します。愚直。

```math
O(n)
```


## 二分探索

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

![out.gif](https://qiita-image-store.s3.amazonaws.com/0/368897/1e24454d-4f47-b03e-19f8-fa619e653ff4.gif)

#### [計算量](https://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%82%A6%E3%81%AE%E8%A8%98%E5%8F%B7#%E4%B8%80%E8%88%AC%E7%9A%84%E3%81%AA%E3%82%AA%E3%83%BC%E3%83%80%E3%83%BC)
1024件 = 2^10件 = 2*2*2*2*2*2*2*2*2*2件を半分ずつ捨てながら見るので、
最大でも10個のデータを参照すれば見つかります。賢い。

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

## ハッシュ法

- 対象データ全てのmail_addressをハッシュ関数に渡して一定のルールで変換し、ハッシュ値を得ます
- 検索キーのmail_addressも同じハッシュ関数に渡して、同じルールで変換し、ハッシュ値を得ます
- ハッシュ値の一致するデータを参照します
- 対象データのハッシュ値の塊から指定したハッシュ値xxxを見つける際に、追加の処理は必要ありません（実装例：[ハッシュテーブル](https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E3%83%86%E3%83%BC%E3%83%96%E3%83%AB)）

![out.gif](https://qiita-image-store.s3.amazonaws.com/0/368897/7ce47e57-8636-5bcb-236b-56be3a710e97.gif)


#### [計算量](https://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%82%A6%E3%81%AE%E8%A8%98%E5%8F%B7#%E4%B8%80%E8%88%AC%E7%9A%84%E3%81%AA%E3%82%AA%E3%83%BC%E3%83%80%E3%83%BC)
1024件でもハッシュ関数を1度経由すれば、対象データを直接参照できます

```math
O(1)
```

#### 欠点
一般的に、アルゴリズムは[実行時間短縮とメモリ消費低減のトレードオフ](https://ja.wikipedia.org/wiki/%E6%99%82%E9%96%93%E3%81%A8%E7%A9%BA%E9%96%93%E3%81%AE%E3%83%88%E3%83%AC%E3%83%BC%E3%83%89%E3%82%AA%E3%83%95)です
両方が悪い実装は存在しますし、作れますが、
それぞれで同時に最高のパフォーマンスを出すアルゴリズムは存在しないでしょう
ハッシュ法もご多分に漏れず、メモリを食います

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

PostgreSQL 実行計画(explain, explain analyze)

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

[PostgreSQL Index Only Scan 奮闘記 その3 | TECHSCORE BLOG](https://www.techscore.com/blog/2013/06/07/postgresql-index-only-scan-%E5%A5%AE%E9%97%98%E8%A8%98-%E3%81%9D%E3%81%AE3/)
[【SQL】ゼロ知識から実行計画を読み解きパフォーマンス改善 - Qiita](https://qiita.com/yoshinori_hisakawa/items/5ef0cf4fd8eb6dd3037f)
[EXPLAIN - PostgreSQL 10.5文書](https://www.postgresql.jp/document/10/html/index.html)

# Java実装・計測
## 探索の実装前に

![キャプチャ.PNG](https://qiita-image-store.s3.amazonaws.com/0/368897/4b1fb688-7349-7d8f-0303-c61c4951ebd8.png)

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

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

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

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

```Java
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

```Java
// 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

```Java
// 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

```Java
// 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]
(http://e-words.jp/w/%E7%B7%9A%E5%BD%A2%E6%8E%A2%E7%B4%A2.html)
[二分探索（2分探索）とは - IT用語辞典 e-Words](http://e-words.jp/w/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2.html)
[ハッシュ法（ハッシュ探索）とは - IT用語辞典 e-Words](http://e-words.jp/w/%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E6%B3%95.html)
[線型探索 - Wikipedia](https://ja.wikipedia.org/wiki/%E7%B7%9A%E5%9E%8B%E6%8E%A2%E7%B4%A2)
[二分探索 - Wikipedia](https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2)