这个题目有一个前提条件,大文件的中的数据有有一个特点,那就是不存在重复的数据。就算是重复的数据,也只让你求出去除重复之后的那些数据的排序结果。
如果题目变成了这样,我们就可以考虑创建一个大的数组。数组的下表表示一个整数,数组的内容在我遍历文件的时候再赋值。如果数组下标代表的那个整数存在,我们就把数组的这个元素赋值为1,否则赋值为0.这样我们就可以再次遍历数组,把元素的值为1的那些下标输出到另一个文件,这样另一个文件中就存放了排好序的数据了。
上面的那个数组,其实我们可以用vector<bool>,或者bitset<n>;来实现,这就是所谓的位图算法,实现如下:
//对10^7个整数的文件进行排序,整数无重复,将排序的结果写到sorted_data.txt文件中。
//用位图的方法。
void sort_big_file_with_single_data()
{
timer t;
//生成一个大数集合,随机排列
const int n=5000000;
vector<int> a;
for (int i=0;i<n;i++)
a.push_back(i);
variate_generator<mt19937, uniform_int<> > myrandom (mt19937(), uniform_int<>(0,n-1));
for (int i=0; i<n; ++i)
swap(a[myrandom()],a[myrandom()]);
//写数据到文件
ofstream fout("data.txt",ios::binary);
if (!fout)
{
cout<<"can not open file to write"<<endl;
}
for (int i=0;i<n;i++)
{
fout.write(reinterpret_cast<const char*>(&a[i]),sizeof(int));
}
fout.close();
//从文件中读取前100个数据并显示
ifstream fin;
fin.open("data.txt",ios::binary);
for (int i=0,num=0;i<100;i++)
{
fin.read(reinterpret_cast<char*>(&num),sizeof(int));
if (fin.eof())
{
break;
}
cout<<num<<" ";
}
fin.close();
//对文件排序
bitset<n> bit;
bit.reset();
//ifstream fin;
fin.open("data.txt",ios::binary);
int i=0;
while (true)
{
fin.read(reinterpret_cast<char*>(&i),sizeof(int));
if (fin.eof())
{
break;
}
bit[i]=true;
}
fin.close();
//将排序的文件输出到sorted_data.txt
//ofstream fout;
fout.open("sorted_data.txt",ios::binary);
for (int i=0;i<n;i++)
{
if (bit[i]==true)
{
fout.write(reinterpret_cast<const char*>(&i),sizeof(int));
}
}
fout.close();
cout<<"sort data "<<t.elapsed()<<" seconds needed"<<endl;
//读取已经排序的文件并显示前100个数据
fin.open("sorted_data.txt",ios::binary);
for (int i=0,num=0;i<100;i++)
{
fin.read(reinterpret_cast<char*>(&num),sizeof(int));
if (fin.eof())
{
break;
}
cout<<num<<" ";
}
fin.close();
}
上面对5百万个整数的文件进行排序,将结果输出到另外一个文件中,并显示输出文件的一部分作为测试结果。
这里的计时器用到了boost库中的timer,如果没有,下载boost的文件,解压后将boost文件夹放到VC++ IDE的include文件中即可
分享到:
相关推荐
微软笔试题
最新的笔试试题,里面有笔试面试经验。以及试题答案的详细解析。
微软笔试题2010 微软笔试题2010 微软笔试题2010 微软笔试题2010 微软笔试题2010 微软笔试题2010
9.29 微软笔试题 题面及答案,供学习交流
很经典 微软笔试试题 微软笔试题解析和答案.doc
微软华为等计算机各类笔试题
C++笔试题 Sony笔试题 几道题目及自做答案 北电 普天C++笔试题 我所收集的intel比试题 面试题 2005年腾讯招聘 微软 微软亚洲技术支持中心面试题目 微创笔试题目(微创,微软在中国的合资公司) Intel笔试面试题目 ...
照片照出的微软综合题,有几个单词没照下来
微软笔试题 微软笔试题 近年题目2 要求描述没啥可说的
2012年微软中国实习生笔试题,附带答案分析,
微软亚洲技术支持中心面试题目、微创笔试题目(微创,微软在中国的合资公司)、Intel笔试面试题目、IBM笔试题目、阿尔卡特(中国)的面试题目、Google、 戴尔、Sony笔试题、华为笔试题、大唐电信、网通笔试题、中软...
微软2014校园招聘笔试试题.docx
C++面试题笔试题C++ 数据结构算法笔试题资料合集: 50个C、C++面试题.pdf C++ 数据结构、算法笔试题.docx C++基础面试题.docx C++开发工程师面试题库.docx C++技能测试试卷一及答案.docx C++技能测试试卷二及答案....
微软笔试题,推理题,应用题,计算题,专业题,反应题等等
java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 ...
微软2015校园招聘笔试题 一共4道题,超叼有没有,然并卵,你能做出来吗?
大连华信去年的笔试题,可以给各位即将工作的同学一些参考
微软 百度等 很多大公司的笔试题的总结 非常有用
微软笔试题.docx