1. 100万(10`7)条记录的文本文件，取出重复数最多的前10条。
示例文本： 098 123 234 789 …… 234 678 654 123
首先遍历一遍文本，得到每个记录出现次数O(n)
然后取十次K大值O(m) k为1、2、3…… m最大为整数边界
由于n>>m 所以复杂度为O(n) 空间复杂度为O(2`32) 需要内存2G
二>可以用哈希表key记录值，value记录出现的次数
2. 100亿（10`11）条记录文本文件，取出重复数最多的前10条。刚才是100万的数据，你的计算机可以单批正帯处理，现在有100亿的数据，假设由于你的计算机内存、cpu限制，无法单批处理 ……
将100亿条分成10000 组，每组取前10条。
然后将这10万条再取前十条。
hash方法的实现：
data.txt
codes:012 123 123 121 012 121 123 111 222 222 222 2222 222 333 902 121 131 121 343 345 422
运行结果：// BigData_hash.cpp : Defines the entry point for the console application.
//
#include <iostream>
#include <map>
#include <fstream>
using namespace std;
int main(int argc, char* argv[])
{
ifstream readtxt;
readtxt.open("data.txt");
if(!readtxt)
{
cerr<<"Error opening input stream" << endl;
return -1;
}
map<int,unsigned int>mymap;
int temp_num;
pair<map<int,unsigned int >::iterator,bool>check_pair;
map<int,unsigned>::iterator it;
while (readtxt.good())
{
readtxt>>temp_num;
check_pair=mymap.insert(make_pair(temp_num,1));
if (check_pair.second==false)
{
mymap[temp_num]=(mymap.find(temp_num))->second+1; //it equals to the next two lines
// it=mymap.find(temp_num);
// it->second++;
}
}
for(it=mymap.begin();it!=mymap.end();it++)
{
cout<<it->first<<" --- "<<it->second<<endl;
}
return 0;
}
12 --- 2
111 --- 1
121 --- 4
123 --- 3
131 --- 1
222 --- 4
333 --- 1
343 --- 1
345 --- 1
422 --- 1
902 --- 1
2222 --- 1
Press any key to continue
评论