【Practice】ホワイトリストフィルタ
背景:largeWファイルの数字に基づいてlargeTファイルをフィルタし、largeWにない場合resultを格納することが要求される.txtファイルにあります.LargeWとlargeTファイルのデータは100万ドルです.『アルゴリズム4』の公式サイトから入手.
質問:largeWは無秩序で、重複項目があり、二分検索を行います.ランダムアクセス反復器のあるコンテナを使用する必要があります.vectorシーケンスコンテナを選択します.Dequeはフロントエンドと中部を固定時間に挿入する利点を示さないため,逆にランダムアクセスが遅いという劣勢がある.
質問:largeWは無秩序で、重複項目があり、二分検索を行います.ランダムアクセス反復器のあるコンテナを使用する必要があります.vectorシーケンスコンテナを選択します.Dequeはフロントエンドと中部を固定時間に挿入する利点を示さないため,逆にランダムアクセスが遅いという劣勢がある.
#include<fstream>
#include<iostream>
#include <vector>
#include<algorithm>
#include<iterator>
using namespace std;
bool BinarySearch(int key,vector<int>& dict)
{
vector<int>::iterator begin = dict.begin();
int lo=0;
int hi=dict.size()-1;
int mid;
while(lo<=hi)
{
mid = (lo+hi)/2;
if(key<dict[mid])
hi=mid-1;
else if(key>dict[mid])
lo = mid+1;
else
return true;
}
return false;
}
#include<windows.h>
void main()
{
ifstream fwhite;
ifstream fnumber;
int number;
vector<int> white_list;
fnumber.open("largeT.txt");
fwhite.open("largeW.txt");
if(!fnumber.is_open() || !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);
}
while(!fwhite.eof())
{
fwhite>>number;
white_list.push_back(number);
}
sort(white_list.begin(),white_list.end());
white_list.erase(unique(white_list.begin(),white_list.end()),white_list.end());
ofstream fout("sort_white.txt",ios::trunc);
copy(white_list.begin(),white_list.end(),ostream_iterator<int,char> (fout,"
"));
ofstream fresult("result.txt");
while(!fnumber.eof())
{
fnumber>>number;
if(!BinarySearch(number,white_list))
{
fresult<<number<<endl;
}
}
exit(EXIT_SUCCESS);
};