/****************************/
/* ソートと探索 */
/* 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;
}