步骤:
- 生成500MB左右的单个文件，一行一个数字
- 利用置换-选择算法，基于败者树进行分段按从小到大的顺序写入多个对应段号(从1开始)的文件
- 对多个有序段号的文件进行归并排序为一个有序文件
置换-选择排序的部分：
defination.h
#define MAXNUM 0xfffff
#define w 1073741824
// 1GB=1024*1024*1024=1073741824 w的值基本上不影响内存
int k=6;
// 500MB情况下 最高支持142路归并排序(暂时不清楚为什么,理论应该不止这个数)
readfile.h
int readline(FILE*fp){
int buff;
if (fscanf(fp, "%d", &buff) > 0){
// 判断是否读到文件终止符了
//printf("in:%d\n",buff);
return buff;
}
else{
return EOF;
}
}
writefile.h
void writeline(FILE*&fp,int input){
fprintf(fp,"%d\n",input);
fflush(fp);
// 必须fflush要不然缓冲区要溢出
//printf("w:%d\n",input);
counts++;
}
generatefile.h
// 生成随机数，一行一个数
int generate_num(){
int a;
a = rand();
return a;
}
// 根据k值生成对应数量的文件,根据weight设置k个文件之和的大小，每个文件大小均匀
void generatefile(int k,int weight){
int i,j;
srand((unsigned)time(NULL));
for(i=0;i<k;i++){
FILE *fp = NULL;
string s=".txt";
s=to_string(i)+s;
fp = fopen(s.c_str(), "w+");
for(j=0;j<w/k;j++){
fprintf(fp, "%d\n",generate_num()%1000+1);
}
fclose(fp);
}
}
losetree.h
class losetree{
public:
// 叶节点
int *key;
// 非叶节点
typedef struct{
int value;
// 存放具体数值
int scope;
// 属于哪个块
}leaf;
leaf*l;
// 二叉败者树的非叶节点，负责索引到对应叶节点，大小为k
losetree(int k){
l=new leaf[k];
key=new int(k);
}
~losetree(){
delete[] l;
delete[] key;
}
// 用于置换-选择排序(分段)的初始化,必须从后往前推，因为要保证0这个点最后被覆盖
void build(FILE*fp){
// 初始化叶节点
int i;
// memset(key,0,k*sizeof(int));
// 读取k个数字填充败者树
for(i=k-1;i>=0;i--){
key[i]=0;
l[i].scope=0;
l[i].value=0;
}
for(i=k-1;i>=0;i--){
l[i].scope=1;
insert(readline(fp),i);
}
}
void insert(int input,int position){
// position 在叶节点上的位置(为了方便，我们允许它的值大于k，
// 从而实现leaf还有losertree两个不同类型数据的操作共享)
// now从叶节点循着父节点(now/2)往上冒泡
int now=k+position;
// 比较胜者点之前的value与当前插入的值,从而决定是否对scope进行修改
if(input>=l[key[0]].value){
l[position].scope;
}
else{
l[position].scope+=1;
}
// 用输入对胜者点进行替换(需要放在scope修改之后，因为key[0]在大部分操作中=position，要不然永远相等了)
l[position].value=input;
// position存放胜出值对应的leaf点位置,now则是树非叶节点的位置
while(now!=0){
// 考虑我(position)失败的情况，即父节点段号更小或者段号相等但是值更小，将胜者position用父节点指向的节点位置覆盖
if(l[key[(now/2)]].scope<l[position].scope||(l[key[(now/2)]].scope==l[position].scope&&l[key[(now/2)]].value<l[position].value)){
int temp=key[now/2];
key[now/2]=position;
position=temp;
}
// 考虑我胜利的情况,啥都不用做
else{
}
now/=2;
}
key[0]=position;
}
int get_block(FILE* fp,int pre_scope){
FILE* out=NULL;
if(l[key[0]].value==MAXNUM){
return 0;
}
else{
string s=".txt";
string folder="./txt/";
string filename=(folder+to_string(pre_scope)+s);
//printf("%s\n",filename.c_str());
out=fopen(filename.c_str(),"w+");
// 每次都要先摘掉tree头部的min值然后再insert知道下个段的min值替代了tree的头
writeline(out,l[key[0]].value);
}
int i;
while(1){
// 不断从文件读取数据输入败者树，
// 如果段号更新则输出前一个段号的所有数据
int input=readline(fp);
//printf("input:%d\n",input);
// 发现读到初始文件句尾了
if(input==EOF){
// 填充MAXNUM把里面残余的数据挤出来
// 先修改scope,反正读到MAXNUM就退出
l[key[0]].scope=MAXNUM;
insert(MAXNUM,key[0]);
}
else{
// 正常插入
insert(input,key[0]);
}
// scope更新说明已经刷新到下一个段了
if(l[key[0]].scope>pre_scope){
if(l[key[0]].value==MAXNUM){
fclose(out);
// 返回0表示已经读完最后一个段了
return 0;
}
pre_scope=l[key[0]].scope;
break;
}
writeline(out,l[key[0]].value);
}
fclose(out);
// 返回1表示还有别的段没读完
return 1;
}
};
depart.cpp
#include <stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string>
#include<vector>
using namespace std;
int counts=0;
// 统计写进去的数字个数，避免读取的初始文件数据在计算中缺失没有写进各个段文件中
// 把宏定义统一写到一块更方便
#include "defination.h"
#include "generatefile.h"
// 生成初始文件
#include "readfile.h"
#include "writefile.h"
// 败者树
#include "losetree.h"
/*
本程序负责生成一组(0,1000]的随机整数并写入txt文件中，并通过置换排序算法生成多个子文件，
生成的文件中数据已经按从小到大顺序排好序
*/
int main(){
// generatefile(1,w); 生成1个含w个数字的文件
FILE*fp=fopen("1GB.txt", "r+");
// 4GB的没办法读直接返回-1
int i,j;
/*处理代码*/
losetree ls(k);
// 初始化
ls.build(fp);
/*初始化结束*/
// 初始化段号
int pre_scope=1;
while(ls.get_block(fp,pre_scope++)){
//printf("ok\n"); 少打点省内存
}
printf("\nfilenum:%d\n",pre_scope-1);
printf("counts:%d",counts);
fclose(fp);
}
- 小结：
-
因为用的是系统自带的int（4B），最大能表示
，k值在windows系统下最高设置为142（不清楚具体的原因理论上应该可以设置为内存大小），所以理论上最多能对
个数字（略大于6098个亿）进行排序。如果是
wb以二进制写入的话，用空格（占1B）隔开，可能要占用2840GB大小的空间。 -
i5-8250U的CPU占用40%，内存占用极低基本上可以忽略不计。每次循环的FILE*建议不要重复使用，要不然可能无法释放之前读取的数据，造成内存溢出。
-
一次性打开/读/写的文件大小一般有限制，fopen的缓冲区一般最大2个GB。用fwrite函数写数据的时候，fwrite先将数据写到内存中的缓冲区内，等程序结束（理论上是fclose）后才会将数据由缓冲区写入文件。所以每次fwrite之后必须fflush。
-
读写文件如果是
wb这种理论上更节约空间，w+是以文本方式打开文件，wb是二进制方式打开文件，以文本方式打开文件时，fwrite函数每碰到一个0xdata时，就在它的前面加入0x0D，要额外占用硬盘空间。
- linux操作系统是32位操作系统文件大小只能是4G
k路平衡归并算法
defination.h
#define MAXNUM 0xfffff
#define w 1073741824
// 1GB=1024*1024*1024=1073741824 w的值基本上不影响内存
int k=6;
// 500MB情况下 最高支持142路归并排序(暂时不清楚为什么,理论应该不止这个数)
// 文件信息
typedef struct{
int scope;
int size;
}fileinfo;
// 文件大小堆排序
struct cmp{
bool operator()(fileinfo&a, fileinfo&b){
if(a.size == b.size)return a.size>b.size;
return a.size>b.size;
}
};
getFileName.h
// 遍历文件夹下的文件，获取文件的段名和文件大小的信息
void getAllFileNames(priority_queue<fileinfo,vector<fileinfo>,cmp>&filesinfo,const string& folder_path)
{
_finddata_t file;
long flag;
string filename = folder_path + "\\*";//遍历制定文件夹内的jpg文件
if ((flag = _findfirst(filename.c_str(), &file)) == -1)//目录内找不到文件
{
cout << "There is no such type file" << endl;
}
else
{
//通过前面的_findfirst找到第一个文件.和第二个文件..
string name = folder_path + "\\" + file.name;//file.name存放的是遍历得到的文件名
//依次寻找以后的文件
_findnext(flag, &file);
while (_findnext(flag, &file) == 0)
{
string name = string(folder_path + "\\" + string(file.name));
//cout << file.name << endl;
fileinfo f;
f.scope=atoi(file.name);
f.size=txt_file_size(name.c_str());
filesinfo.push(f);
}
}
_findclose(flag);
}
txtSize.h
// 获取文件大小
#include <sys/stat.h>
int txt_file_size(const char* filename)
{
struct stat statbuf;
stat(filename,&statbuf);
int size=statbuf.st_size;
return size;
}
int get_size_by_int(int t){
string folder="./txt/";
string name = string(folder + to_string(t));
return txt_file_size(name.c_str());
}
losetree.h
class losetree{
public:
// 叶节点
int *key;
// 非叶节点
typedef struct{
int value;
// 存放具体数值
int scope;
// 属于哪个块
}leaf;
leaf*l;
// 二叉败者树的非叶节点，负责索引到对应叶节点，大小为k
losetree(int k){
l=new leaf[k];
key=new int(k);
int i;
for(i=k-1;i>=0;i--){
key[i]=0;
l[i].scope=0;
l[i].value=0;
}
//memset(&l,0,k*sizeof(leaf));
//memset(&key,0,k*sizeof(int));
}
// 用于置换-选择排序(分段)的初始化,必须从后往前推，因为要保证0这个点最后被覆盖
void build(FILE*fp){
// 初始化叶节点
int i;
// memset(key,0,k*sizeof(int));
// 读取k个数字填充败者树
for(i=k-1;i>=0;i--){
l[i].scope=1;
insert(readline(fp),i);
}
}
void insert(int input,int position){
// position 在叶节点上的位置(为了方便，我们允许它的值大于k，
// 从而实现leaf还有losertree两个不同类型数据的操作共享)
// now从叶节点循着父节点(now/2)往上冒泡
int now=k+position;
// 比较胜者点之前的value与当前插入的值,从而决定是否对scope进行修改
if(input>=l[key[0]].value){
l[position].scope;
}
else{
l[position].scope+=1;
}
// 用输入对胜者点进行替换(需要放在scope修改之后，因为key[0]在大部分操作中=position，要不然永远相等了)
l[position].value=input;
// position存放胜出值对应的leaf点位置,now则是树非叶节点的位置
while(now!=0){
// 考虑我(position)失败的情况，即父节点段号更小或者段号相等但是值更小，将胜者position用父节点指向的节点位置覆盖
if(l[key[(now/2)]].scope<l[position].scope||(l[key[(now/2)]].scope==l[position].scope&&l[key[(now/2)]].value<l[position].value)){
int temp=key[now/2];
key[now/2]=position;
position=temp;
}
// 考虑我胜利的情况,啥都不用做
else{
}
now/=2;
}
key[0]=position;
}
int get_block(FILE* fp,int pre_scope){
FILE* out=NULL;
if(l[key[0]].value==MAXNUM){
return 0;
}
else{
string folder="./txt/";
string filename=(folder+to_string(pre_scope));
//printf("%s\n",filename.c_str());
out=fopen(filename.c_str(),"w+");
// 每次都要先摘掉tree头部的min值然后再insert知道下个段的min值替代了tree的头
writeline(out,l[key[0]].value);
}
int i;
while(1){
// 不断从文件读取数据输入败者树，
// 如果段号更新则输出前一个段号的所有数据
int input=readline(fp);
//printf("input:%d\n",input);
// 发现读到初始文件句尾了
if(input==EOF){
// 填充MAXNUM把里面残余的数据挤出来
// 先修改scope,反正读到MAXNUM就退出
l[key[0]].scope=MAXNUM;
insert(MAXNUM,key[0]);
}
else{
// 正常插入
insert(input,key[0]);
}
// scope更新说明已经刷新到下一个段了
if(l[key[0]].scope>pre_scope){
if(l[key[0]].value==MAXNUM){
fclose(out);
// 返回0表示已经读完最后一个段了
return 0;
}
pre_scope=l[key[0]].scope;
break;
}
writeline(out,l[key[0]].value);
}
fclose(out);
// 返回1表示还有别的段没读完
return 1;
}
// 简化版的基于最佳归并树BMT的k路归并排序 返回最终的resfile名字
int kmerge(priority_queue<fileinfo,vector<fileinfo>,cmp>&q){
// 每次轮回前检查以下待排序的文件数量filenum有没有>=k个，不足的就记录下来用MAXNUM灌水，
// 写入的文件名=filenum+1
// 如果发现输出了MAXNUM说明结束了，返回
// 如果没有输出MAXNUM则接着读，如果有个别分支读不出来数据但是又没读到MAXNUM就用MAXNUM替代-1然后就不用管了
// fclose()
int i,j;
int resfile=-1;
int end=q.size();
string folder="./txt/";
for(i=1;;i++){
//int size=q.size();
if(q.size()==1){
break;
}
FILE*out=fopen((folder+to_string(end+i)).c_str(),"w+");
//FILE*leafs=(FILE*)malloc(k*sizeof(FILE*));
FILE*leafs[k];
int blank=0;
if(q.size()>=k){
j=k;
while(j){
leafs[j-1]=fopen((folder+to_string(q.top().scope)).c_str(),"r+");
j--;
q.pop();
}
// build
for(j=k-1;j>=0;j--){
l[j].scope=1;
insert(readline(leafs[j]),j);
}
// circle read
while(l[key[0]].value!=MAXNUM){
writeline(out,l[key[0]].value);
int newinput=readline(leafs[key[0]]);
if(newinput==EOF){
// 如果其中一个段读到底了就用MAXNUM封一下
insert(MAXNUM,key[0]);
}
else{
insert(newinput,key[0]);
}
}
for(j=0;j<k;j++){
fclose(leafs[j]);
}
}
else{
j=q.size();
blank=k-q.size();
while(j){
leafs[j-1]=fopen((folder+to_string(q.top().scope)).c_str(),"r+");
j--;
q.pop();
}
//build
for(j=k-1;j>=k-blank;j--){
l[j].scope=1;
insert(MAXNUM,j);
}
for(j=k-blank-1;j>=0;j--){
l[j].scope=1;
insert(readline(leafs[j]),j);
}
// circle read
while(l[key[0]].value!=MAXNUM){
writeline(out,l[key[0]].value);
int newinput=readline(leafs[key[0]]);
if(newinput==EOF){
// 如果其中一个段读到底了就用MAXNUM封一下
insert(MAXNUM,key[0]);
}
else{
insert(newinput,key[0]);
}
}
for(j=0;j<q.size();j++){
fclose(leafs[j]);
}
}
//delete[]leafs;
fclose(out);
// out 写完记得加到priority_queue的队列里面去
fileinfo f;
f.scope=end+i;
f.size=get_size_by_int(f.scope);
q.push(f);
// 每次losetree用完都要重新置为0
for(j=k-1;j>=0;j--){
key[j]=0;
l[j].scope=0;
// l[j].value=0;
}
}
return q.top().scope;
}
};
网友评论