線形探索

/****************************/
/* 線形探索                 */
/*      coded by Y.Suganuma */
/****************************/
#include <stdio.h>
#include <vector>
#include <time.h>
#include "MT.h"

using namespace std;

clock_t tm1, tm2, tm3;
					// 配列と線形探索
void linear()
{
	int s[100000], n = 0, ct = 0;
	int *data = new int [5000000];
	init_genrand((unsigned)time(NULL));

	tm1 = clock();
	for (int i1 = 0; i1 < 5000000; i1++) {
		int k    = genrand_int31();
		data[i1] = k;
		ct++;
		if (i1%50 == 0 && n < 100000) {
			s[n] = k;
			n++;
		}
	}
	tm2 = clock();
	printf("   保存： %d ms\n", (int)(tm2-tm1));
	for (int i1 = 0; i1 < n; i1++) {
		for (int i2 = 0; i2 < 5000000; i2++) {
			if (data[i2] == s[i1])
				break;
		}
	}
	tm3 = clock();
	printf("   探索： %d ms\n", (int)(tm3-tm2));
	printf("   データ数： %d\n", ct);
}
					// vectorと線形探索
void linear_v()
{
	int s[100000], n = 0, ct = 0;
	vector<int> data;

	tm1 = clock();
	for (int i1 = 0; i1 < 5000000; i1++) {
		int k = genrand_int31();
		data.push_back(k);
		ct++;
		if (i1%50 == 0 && n < 100000) {
			s[n] = k;
			n++;
		}
	}
	tm2 = clock();
	printf("   保存： %d ms\n", (int)(tm2-tm1));
	for (int i1 = 0; i1 < n; i1++) {
		for (vector<int>::iterator it = data.begin(); it != data.end(); it++) {
			if (*it == s[i1])
				break;
		}
	}
	tm3 = clock();
	printf("   探索： %d ms\n", (int)(tm3-tm2));
	printf("   データ数： %d\n", ct);
}

int main()
{
					// 配列と線形探索
	printf("配列と線形探索\n");
	linear();
					// vectorと線形探索
	printf("vectorと線形探索\n");
	linear_v();

	return 0;
}