【Practice】vector内の重複要素を除去する方法の比較

背景:重複のないホワイトリストを作成し、中で二分検索します.したがって、リストは秩序正しく、重複がなく、二分的に検索する必要があるため、反復器タイプにランダムにアクセスするコンテナを使用します.このような容器にはvector,array,dequeがある.明らかにvectorとdequeが適切であることは明らかであるが、dequeはその両端と中間挿入時間が固定で非線形であるという利点を示していない.本例はいずれも末尾に挿入され、vectorとdequeは同じ固定時間であるからである.一方dequeのランダムストレージは操作時間が長いためvectorを採用する.
一.STLアルゴリズムによるunique
まずvectorをソートし、ソートします.eraseを用いてuniqueアルゴリズムを組み合わせる.100万の整数を含んでいて、数字があまり繰り返されていない場合にテストします.

#include<fstream>
#include<iostream>
#include <vector>
#include<algorithm>
#include<ctime>

using namespace std;	
void main()
{
	ifstream fwhite;
	int number;
	vector<int> white_list;
	clock_t cost;
	fwhite.open("largeW.txt");
	if(!fwhite.is_open())
	{//or use .good .fail or directly use ! to judge if the file has been opened successfully
		cout<<"can't open file list"<<endl;
		exit(EXIT_FAILURE);
	}
	cost=clock();


	while(!fwhite.eof())
	{
		fwhite>>number;
		white_list.push_back(number);
	}
	cost=clock()-cost;
	cout<<"Time to load data : "<<cost<<endl;
	
	sort(white_list.begin(),white_list.end());
	white_list.erase(unique(white_list.begin(),white_list.end()),white_list.end());
	cost = clock()-cost;
	cout<<"Time to remove reduplicative data from vector : "<<cost<<endl;

	ofstream fout("sort_white.txt",ios::trunc);

	vector<int>::iterator iter=white_list.begin();
	while (iter!= white_list.end())
	{
		fout<<*iter<<endl;
		iter++;
	}
	cost = clock()-cost;
	cout<<"Time to write data into file : "<<cost<<endl;
	exit(EXIT_SUCCESS);
};

二.setでcopyを合わせる
データを読むときはsetを使ってvectorに直接コピーします.でもコピーするときはinsert_を使いますiteratorで挿入コピーを行います.(オーバーフローの問題)

#include<fstream>
#include<iostream>
#include <vector>
#include<set>
#include<algorithm>
#include<ctime>
#include <iterator>
using namespace std;	
void main()
{
	ifstream fwhite;
	int number;
	vector<int> white_list;
	set<int> ori_list;
	clock_t cost;
	fwhite.open("largeW.txt");
	if(!fwhite.is_open())
	{//or use .good .fail or directly use ! to judge if the file has been opened successfully
		cout<<"can't open file list"<<endl;
		exit(EXIT_FAILURE);
	}
	cost=clock();
	
	
	while(!fwhite.eof())
	{
		fwhite>>number;
		ori_list.insert(number);
	}
	cost=clock()-cost;
	cout<<"Time to load data : "<<cost<<endl;

	insert_iterator<vector<int> > it(white_list,white_list.begin());
	copy(ori_list.begin(),ori_list.end(),it);
	cost = clock()-cost;
	cout<<"Time to copy data from set to vector : "<<cost<<endl;

	ofstream fout("sort_white.txt",ios::trunc);
	vector<int>::iterator iter=white_list.begin();
	while (iter!= white_list.end())
	{
		fout<<*iter<<endl;
		iter++;
	}
	cost = clock()-cost;
	cout<<"Time to write data into file : "<<cost<<endl;
	exit(EXIT_SUCCESS);
};

三.時間オーバーヘッドはコンテナの構築開始からclockで計時する
1つ目の消費時間:8.477秒
2つ目の消費時間:23.246秒
見て、vectorをそのまま使えばいいので、uniqueに合わせたほうがいいです.原因:同じように100万個の整数を挿入し、setは長すぎて、テストで約18秒かかりました.メインコストです.
1つ目は、vectorオーバーヘッド5.852秒までファイルを読み込み、重複要素オーバーヘッド3.205秒をソートして除去し、ファイルオーバーヘッド15.624秒を書き込みます.総消費時間は約24秒程度です.
2つ目は、ファイルの読み取りからsetオーバーヘッドまで18.893秒、setコピーデータからvectorオーバーヘッドまで4.884秒、ファイルの書き込みオーバーヘッドまで20秒です.総消費時間は約44秒程度です.
しかし、プログラムがファイルを書くのが遅いことがわかります.この例ではiterator反復で値を取ってファイルを書くのですが、インデックスの下付きを直接使うともっと速くなりますか?またはcopy関数とstream_を使用します.interator?
四.1に基づいて、最後にファイルを書くときは反復器ではなく下付きを採用します.
明らかな改善は認められなかった.
五.統合レプリケーションを採用し、ostream_と連携iteratorは、この例では速度を半分近く短縮します.

#include<fstream>
#include<iostream>
#include <vector>
#include<algorithm>
#include<ctime>
#include <iterator>

using namespace std;	
void main()
{
	ifstream fwhite;
	int number;
	vector<int> white_list;
	clock_t cost;
	fwhite.open("largeW.txt");
	if(!fwhite.is_open())
	{//or use .good .fail or directly use ! to judge if the file has been opened successfully
		cout<<"can't open file list"<<endl;
		exit(EXIT_FAILURE);
	}
	cost=clock();


	while(!fwhite.eof())
	{
		fwhite>>number;
		white_list.push_back(number);
	}
	cost=clock()-cost;
	cout<<"Time to load data : "<<cost<<endl;
	
	sort(white_list.begin(),white_list.end());
	white_list.erase(unique(white_list.begin(),white_list.end()),white_list.end());
	cost = clock()-cost;
	cout<<"Time to remove reduplicative data from vector : "<<cost<<endl;

	ofstream fout("sort_white.txt",ios::trunc);

	/*vector<int>::iterator iter=white_list.begin();
	while (iter!= white_list.end())
	{
		fout<<*iter<<endl;
		iter++;
	}*/
	//for(unsigned int index = 0;index< white_list.size();index++)
	//{
	//	fout<<white_list[index]<<endl;
	//}

	copy(white_list.begin(),white_list.end(),ostream_iterator<int,char>(fout,"
"));
	cost = clock()-cost;
	cout<<"Time to write data into file : "<<cost<<endl;
	exit(EXIT_SUCCESS);
};

また,largeWファイルは『アルゴリズム4』のサイトから入手したものであるか,rand関数を用いてまず自分で作成することができる.各行にint型整数を1つ、100万行でよい.