vectorデータ検索方法

STLでプログラムを記述する際にvectorコンテナを使用してデータを格納することが多く、コンテナ内のデータが秩序化されている場合、2つの方法を採用することができます.
(1)利用中のfind関数で検索する.
(2)半値で検索する.
またhash_にデータを格納することもできますmapで検索を行い,これら2つの方法を比較する時間効率をテストする.

1.データセットのテスト

999999より小さいすべての素数をクエリー・データセットとして生成し、2～99999の間のすべての数を検索します.
配列Aに2~999999の間のすべての数を記憶させると、素数を生成する方式
(1)現在最小の数字minを見つける;
(2)minのすべての倍数を削除します.
この2つのプロセスをAのすべてのデジタル処理が完了するまで繰り返し、すなわち2~99999の間のすべての素数が見つかった.

2.効率比較

find関数を用いて検索するには2745 msが必要であり,折半とhash_を用いる.mapはいずれも0 msしか必要ありません.
数字が99999999に増加すると、半減するのに63 msかかります.hash_mapは31 msかかります.
数字が99999999に増加すると、半減で577 msかかり、hash_mapは499 msかかります.
注意:hash_mapでバケツを初期化できない個数はhashの速度を低下させる.(初期化方法をお知らせください)

3.分析

実際に発生した問題:大規模な図データを処理する過程でvectorがすべての図データを格納できることに遭遇し、hash_mapはできません.すなわちvectorが格納するデータ規模比hash_mapが大きい.
半角検索は、秩序化されたデータの検索にのみ使用できますが、findは必要ありません.

4.参照コード

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;


class compare
{
	vector dataVector;
	vector findData;
	hash_map dataHash;
public:
	compare();
	~compare(void);
	void generalPrime();
	void findTest();
	void binSearch();
	void hashTest();
};

compare::compare()
{
	generalPrime();
}


compare::~compare(void)
{
	findData.clear();
	dataVector.clear();
}

void compare::findTest()
{
	clock_t startTime = clock();
	vector::iterator result;
	int exist = 0;
	for (vector::iterator it = findData.begin(); it < findData.end(); it++)
	{
		result = find(dataVector.begin(), dataVector.end(), *it);
		if (result != dataVector.end())
		{
			// 
			exist++;
		}
	}
	clock_t endTime = clock();
	cout << "exist num: " << exist << " find time " << (double)(endTime - startTime)/CLOCKS_PER_SEC*1000 << "ms" <::iterator it = findData.begin(); it < findData.end(); it++)
	{
		start = 0;
		end = dataVector.size() - 1;
		middle = (start + end) / 2;
		while (start <= end)
		{
			if (*it < dataVector[middle])
			{
				end = middle - 1;
			}
			else if (*it > dataVector[middle])
			{
				start = middle + 1;
			}
			else
			{
				break;
			}
			middle = (start + end) / 2;
		}
		if (start <= end)
		{
			exist++;
		}
	}
	clock_t endTime = clock();
	cout << "exist num: " << exist << " binsearch time: " << (double)(endTime - startTime)/CLOCKS_PER_SEC * 1000 << "ms" << endl;
}

void compare::generalPrime()
{
	int maxPrime = 99999;
	int flag;
	vector visited(maxPrime, true);
	for (int i = 2; i < maxPrime; ++i)
	{
		findData.push_back(i);
		if (visited[i])
		{
			dataVector.push_back(i);
			dataHash[i] = 1;
			flag = i;
			for (int ii = 2, flag = i * ii; flag < maxPrime; ++ii, flag *= ii)
			{
				visited[flag] = false;
			}
		}
	}
}

void compare::hashTest()
{
	clock_t startTime = clock();
	int exist = 0;
	vector::iterator result;
	for (vector::iterator it = findData.begin(); it < findData.end(); it++)
	{
		if (dataHash.find(*it) != dataHash.end())
		{
			exist++;
		}
	}
	clock_t endTime = clock();
	cout << "exist num: " << exist << " hash time " << (double)(endTime - startTime)/CLOCKS_PER_SEC*1000 << "ms" << endl;
}
int main()
{
	compare com;
	com.findTest();
	com.binSearch();
	com.hashTest();
	return 1;
}