ソートと探索

　　まず，new 演算子を使用した 1 次元配列に，ランダムに生成した 1,000,000 個のデータを記憶し，その後，C++ 標準ライブラリ内の sort 関数によってソートし，二分探索（バイナリサーチ）を行う C++ 標準ライブラリ内の binary_search 関数によって探索しています．探索するデータは，最初に生成したデータの 10 個毎のデータです（ 100,000 個）．データを記憶するのにかかった時間，ソートにかかった時間，及び，探索にかかった時間を出力しています．

　　次は，探索木を利用した例です．C++ 標準ライブラリ内の コンテナである set クラスは，二本木として実装されているようですので，これを使用します．まず，ランダムに生成した 1,000,000 個の整数データを set クラスに保存し，その後，最初に生成したデータの 10 個毎のデータ（ 100,000 個）に対して探索を行っています．データを記憶するのにかかった時間，及び，探索にかかった時間を出力しています．

　　3 番目は，ハッシュを利用した例です．C++ 標準ライブラリ内の コンテナである unordered_map クラスでは，各要素は，キーのハッシュ値に基づきハッシュテーブルに格納されるため，これを使用します．まず，ランダムに生成した 1,000,000 個の整数データを unordered_map クラスに保存し，その後，最初に生成したデータの 10 個毎のデータ（ 100,000 個）に対して探索を行っています．データを記憶するのにかかった時間，及び，探索にかかった時間を出力しています．

　　最後は，文字列の探索です．ランダムに生成した長さ 1,000,200 の文字列 str に対して，5,000 個の長さ 200 の文字列を探索しています．5,000 個の文字列は，str の部分文字列であり，その内，半分には，文字列 str に含まれない文字が 1 文字含まれています．そのため，半分の文字列に対しては，探索しても見つからないことになります．ここでは，文字列に対して 2 つの方法を使用しています．最初は，文字列を char の配列として表現し，C/C++ の標準関数 strstr 関数を利用した場合です．2 番目の例では，文字列に対して，C++ 標準ライブラリ内の string クラスを利用しています．データを記憶するのにかかった時間，及び，探索にかかった時間を出力しています．

/****************************/
/* ソートと探索             */
/*      coded by Y.Suganuma */
/****************************/
#include <time.h>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <random>
#include <vector>
#include <set>
#include <unordered_map>
#include <string>

using namespace std;

#define N 1000000
#define NS 100000

int main()
{
			// 初期設定
	random_device sd;
	mt19937 rnd(sd());
			//
			// 二分探索（ vector ）
			//
				// データ設定
	int *data   = new int [N];
	int *data_s = new int [NS];
	clock_t tm1 = clock();
	int m       = 0;
	for (int i1 = 0; i1 < N; i1++) {
		int k = rnd();
		data[i1] = k;
		if (i1%10 == 0) {
			data_s[m] = k;
			m++;
		}
	}
				// sort
	clock_t tm2 = clock();
	sort(data, data+N);
				// 二分探索
	clock_t tm3 = clock();
	int n = 0;
	for (int i1 = 0; i1 < NS; i1++) {
		bool b = binary_search(data, data+N, data_s[i1]);
		if (!b)
			n++;
	}
	clock_t tm4 = clock();
	printf("データ数(array)： %d，探索データ数 %d\n", N, NS);
	printf("   data %d ms\n", (int)(tm2-tm1));
	printf("   sort %d ms\n", (int)(tm3-tm2));
	printf("   二分探索 %d ms，失敗 %d\n", (int)(tm4-tm3), n);
			//
			// 探索木（ set ）
			//
				// データ設定
	set<int> s;
	tm1 = clock();
	m   = 0;
	for (int i1 = 0; i1 < N; i1++) {
		int k = rnd();
		pair<set<int>::iterator, bool> b = s.emplace(k);
		if (b.second) {
			if (i1%10 == 0) {
				data_s[m] = k;
				m++;
			}
		}
		else
			i1--;
	}
				// 探索
	tm2 = clock();
	n   = 0;
	for (int i1 = 0; i1 < NS; i1++) {
		if (s.find(data_s[i1]) == s.end())
			n++;
	}
	tm3 = clock();
	printf("データ数(set)： %d，探索データ数 %d\n", N, NS);
	printf("   data %d ms\n", (int)(tm2-tm1));
	printf("   探索 %d ms，失敗 %d\n", (int)(tm3-tm2), n);
			//
			// ハッシュ（ unordered_map ）
			//
				// データ設定
	unordered_map<int, double> um;
	uniform_real_distribution<> uniform_r(0, 1.0);
	tm1 = clock();
	m   = 0;
	for (int i1 = 0; i1 < N; i1++) {
		int k    = rnd();
		double v = uniform_r(rnd);
		pair<unordered_map<int, double>::iterator, bool> b;
		b = um.insert(pair<int, double>(k, v));
		if (b.second) {
			if (i1%10 == 0) {
				data_s[m] = k;
				m++;
			}
		}
		else
			i1--;
	}
				// 探索
	tm2 = clock();
	n   = 0;
	for (int i1 = 0; i1 < NS; i1++) {
		if (um.find(data_s[i1]) == um.end())
			n++;
	}
	tm3 = clock();
	printf("データ数(unordered_map)： %d，探索データ数 %d\n", N, NS);
	printf("   data %d ms\n", (int)(tm2-tm1));
	printf("   探索 %d ms，失敗 %d\n", (int)(tm3-tm2), n);
			//
			// 文字列（ 配列 ）
			//
	int N1  = 1000201;
	int NS1 = 5000;
	int NL  = 200;
				// データ設定
	char *str1      = new char [N1+1];
	char **data_st1 = new char *[NS1];
	for (int i1 = 0; i1 < NS1; i1++)
		data_st1[i1] = new char [NL+1];
	n = 0;
	for (int i1 = 0; i1 < N1; i1++) {
		str1[i1] = (char)(65 + 58 * uniform_r(rnd));
		if (n < NS1 && i1 >= 2*NL && (i1 % NL) == 0) {
			int k = i1 - NL - NL / 2 - 1;
			for (int i2 = 0; i2 < NL; i2++) {
				data_st1[n][i2] = str1[k];
				k++;
			}
			data_st1[n][NL] = '\0';
			if (n % 2 > 0)    // 存在しないデータの作成
				data_st1[n][NL/2] = '(';
			n++;
		}
	}
	str1[N1] = '\0';
				// 探索
	NS1    = n;
	tm2    = clock();
	int n1 = 0;
	int n2 = 0;
	for (int i1 = 0; i1 < NS1; i1++) {
		char *p = strstr(str1, data_st1[i1]);
		if (p != NULL)
			n1++;
		else
			n2++;
	}
	tm3 = clock();
	printf("文字数(char)： %d，探索データ（数 %d，文字数 %d）\n", N1, NS1, NL);
	printf("   data %d ms\n", (int)(tm2-tm1));
	printf("   探索 %d ms，成功 %d，失敗 %d\n", (int)(tm3-tm2), n1, n2);
			//
			// 文字列（ string ）
			//
				// データ設定
	vector<string> data_st;
	string str;
	NS1 = 5000;
	n   = 0;
	tm1 = clock();
	for (int i1 = 0; i1 < N1; i1++) {
		str += (char)(65 + 58 * uniform_r(rnd));
		if (n < NS1 && i1 >= 2*NL && (i1 % NL) == 0) {
			int k = i1 - NL - NL / 2 - 1;
			string s = str.substr(k, NL);
			if (n % 2 > 0)    // 存在しないデータの作成
				s = s.replace(NL/2, 1, "(");
			data_st.push_back(s);
			n++;
		}
	}
				// 探索
	NS1 = n;
	tm2 = clock();
	n1  = 0;
	n2  = 0;
	for (int i1 = 0; i1 < NS1; i1++) {
		string::size_type p = str.find(data_st[i1]);
		if (0 <= p && p < str.size()-1)
			n1++;
		else
			n2++;
	}
	tm3 = clock();
	printf("文字数(string)： %d，探索データ（数 %d，文字数 %d）\n", N1, NS1, NL);
	printf("   data %d ms\n", (int)(tm2-tm1));
	printf("   探索 %d ms，成功 %d，失敗 %d\n", (int)(tm3-tm2), n1, n2);

	return 0;
}
		

（出力）

データ数(array)： 1000000，探索データ数 100000
   data 9 ms
   sort 67 ms
   二分探索 20 ms，失敗 0
データ数(set)： 1000000，探索データ数 100000
   data 689 ms
   探索 63 ms，失敗 0
データ数(unordered_map)： 1000000，探索データ数 100000
   data 414 ms
   探索 6 ms，失敗 0
文字数(char)： 1000201，探索データ（数 5000，文字数 200）
   data 467 ms
   探索 2970 ms，成功 2500，失敗 2500
文字数(string)： 1000201，探索データ（数 5000，文字数 200）
   data 47 ms
   探索 3568 ms，成功 2500，失敗 2500