Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 算法 » ,

外部排序

外部排序是指大量数据的排序,通常待排序的数据保存在外存储器上(比如硬盘),待排序的文件无法一次装入内存,需要在内存和硬盘之间进行多次数据交换,以达到排序整个文件的目的。外部排序最常用的算法是多路归并排序,本文将通过具体的代码讲解一个简单的外部排序算法实现。

简介

通常我们提到排序都是指内排序,比如快速排序,堆排序,归并排序等,所谓内排序就是可以在内存中完成的排序。但对于大数据集来说,所有的数据往往无法一次性装入内存,这时候需要使用外排序进行。由于硬盘的访问速度比内存的速度慢得多,于是外排序跟内排序的思想不太一致。

外排序最常用的算法是归并排序,一般分为两个步骤:预处理和合并。即首先根据内存的大小,将有m个记录的磁盘文件分批读入内存,采用有效的内存排序方法进行排序,将排序后的结果保存为若干个有序的子文件,然后采用归并的方法将这些排好序的子文件逐趟合并成最终有序的文件。
归并的思路是把每个子文件的第一个数据取出,从中选择最小的进行输出,然后从该数据所在文件继续读取下一个数据,重新选择最小的,直到所有的子文件都读取完毕为止。在以下的实现中,为了提高选择最小元素的效率,将使用小根堆进行实现。

缓冲

因为外排序涉及到很多硬盘I/O操作,由于硬盘的访问速度比内存慢得多,于是整个排序过程的性能瓶颈主要在磁盘的I/O操作上,我们要尽量减少访问磁盘的次数。
除了在算法上进行优化,一个最基本的思想是使用缓冲。如果每次要读取一个数据时都进行一次访问硬盘,那么整体的速度必然无法接受,于是我们可以创建一个缓冲区,先把硬盘上连续一段的数据读取到内存中,然后每次读取数据时都从这个内存缓冲区进行读取,仅当缓冲区为空时再次进行批量的数据读取,这样就大大减少了访问硬盘的次数。

目前标准I/O库提供了尽可能地减少使用read和write调用次数的缓冲,对每个I/O流自动地进行缓冲管理,从而避免了应用程序需要考虑这一点所带来的麻烦。标准I/O提供了三种类型的缓冲:

  • 全缓冲:填满I/O缓冲区后才进行实际I/O操作,对于磁盘文件通常是由标准I/O库实施全缓冲。缓冲区可由标准I/O例程自动冲洗,也可以调用函数fflush冲洗。
  • 行缓冲:当在输入输出中遇到换行符时,标准I/O库执行I/O操作。允许一次输出一个字符,但只有输出一行后才进行实际I/O操作,但缓冲区的长度是固定的,所以只要填满了缓冲区,那么即使没有写一个换行符,也进行I/O操作。终端通常使用行缓冲。
  • 无缓冲:标准I/O库不对字符进行缓冲存储。例如,每次write系统调用将这些字符立即写至相关联的文件中。

我们使用C/C++的fopen等文件读取操作时,系统默认使用了缓冲机制:系统自动地在内存区为每一个正在使用的文件开辟一个缓冲区。从磁盘向内存读入数据时,则一次从磁盘文件将一些数据输入到内存缓冲区(充满缓冲区),然后再从缓冲区逐个地将数据送给接收变量;向磁盘文件输出数据时,先将数据送到内存中的缓冲区,装满缓冲区后才一起送到磁盘去。用缓冲区可以一次读入一批数据,或输出一批数据,而不是执行一次输入或输出函数就去访问一次磁盘,这样做的目的是减少对磁盘的实际读写次数,因为每一次读写都要移动磁头并寻找磁道扇区,花费一定的时间。缓冲区的大小由各个具体的C版本确定。

另外,我们也可以使用以下函数自定义缓冲区,其中stream可以是标准输入输出或文件输入输出,buf为缓冲区的地址。当buf设置为NULL时,指定不适用任何缓冲。

void setbuf(FILE *stream, char *buf);

下面是使用测试使用缓冲的代码,其中使用了clock函数进行计时。

void testbuf()
{
	clock_t st = clock();

	const unsigned int BUFSIZE = 1 << 30;
	char *buffer = new char[BUFSIZE];
	FILE *fp = fopen("test.txt", "w");
	setbuf(fp, buffer); 

	for (int i = 0; i < 100000000; i++)
		fprintf(fp, "%d\n", (rand() << 15) | rand()); //rand一般产生15位随机数(32767),扩展成30位

	fclose(fp);
	delete(buffer);

	clock_t ed = clock();
	printf("Time usage: %.2lfs\n", (ed - st) / 1000.0);
}

该测试代码的各种输出情况如下:

  • 无缓冲: Time usage: 1880.86s
  • 默认缓冲: Time usage: 61.04s
  • 自定义缓冲:Time usage: 62.03s

以下的程序中为了代码的简介及算法思路的清晰,将使用系统默认的缓冲机制,而且不对各种异常情况进行检测(如新建文件失败)。

代码实现

首先为了方便实验,先产生一个包含若干数据的文本文件,其中的数据是随机产生的30位正整数,每个占据一行。

//在filename文件中随机产生m个数据,每个一行
void genData (string filename, int m)
{
	FILE *fp = fopen(filename.c_str(), "w");
	if (fp == NULL)
	{
		printf("Could NOT open file %s.\n", filename.c_str());
		exit(-1);
	}

	srand(time(0));
	for (int i = 0; i < m; i++)
	{
		int tem = (rand() << 15) | rand(); //rand一般产生15位随机数(32767),扩展成30位
		fprintf(fp, "%d\n", tem);
	}

	fclose(fp);
}

外部排序分成两个部分。

首先是把文件分割成若干个子文件,每个分别对其包含的数据进行内部排序,保存到对应的临时文件中。

//把infile文件(总数据量为m)分割成子文件,每个包含n个数据
void split(string infile, int m, int n) 
{
	FILE *in = fopen(infile.c_str(), "r");

	int *a = new int[n], k = ceil(double(m) / n);
	for (int i = 0, j; i < k; i++) //分割成k部分
	{
		for (j = 0; j < n; j++)
		{
			if (fscanf(in, "%d", a+j) != 1)
				break;
		}
		int num = j;
		sort(a, a + num); //使用内部排序
		
		char temfile[50]; //保存到临时子文件
		sprintf(temfile, "temp-file-%02d.txt", i);
		FILE *temfp = fopen(temfile, "w");
		for (j = 0; j < num; j++)
			fprintf(temfp, "%d\n", a[j]);
		fclose(temfp);
	}

	fclose(in);
}

然后是对子文件的合并,使用一个小根堆保存每个子文件的当前数据,即堆里的每个数据包括该数据本身以及该数据所在的文件。每次取出堆顶的最小元素,然后从该元素中所在文件中读取下一个元素并放入堆中。

//小根堆的仿函数
struct cmp
{
	bool operator() (const pair<int, int> &a, const pair<int, int> &b)
	{
		return a.first > b.first;
	}
};

//合并所有子文件,保存到outfile中。
void merge(string outfile, int m, int n)
{
	FILE *out = fopen(outfile.c_str(), "w");

	int k = ceil(double(m) / n);
	FILE **fp = new FILE*[k]; //每个子文件的描述符
	vector<pair<int, int> > heap(k); //小根堆
	for (int i = 0; i < k; i++)
	{
		char temfile[50];
		sprintf(temfile, "temp-file-%02d.txt", i);
		fp[i] = fopen(temfile, "r");
		
		int tem; fscanf(fp[i], "%d", &tem);
		heap[i] = pair<int, int>(tem, i);
	}
	make_heap(heap.begin(), heap.end(), cmp()); //初始化

	while (1)
	{
		int minVal = heap.front().first, minFile = heap.front().second;
		if (minVal == INT_MAX) break;

		fprintf(out, "%d\n", minVal);

		pop_heap(heap.begin(), heap.end(), cmp()); heap.pop_back();
		int tem; 
		if (fscanf(fp[minFile], "%d", &tem) != 1) //该子文件数据全部读取完毕
			heap.push_back(pair<int, int> (INT_MAX, minFile));
		else 
			heap.push_back(pair<int, int> (tem, minFile));
		push_heap(heap.begin(), heap.end(), cmp());
	}

	for (int i = 0; i < k; i++)
		fclose(fp[i]);
	fclose(out);
}

最后是外部排序总的调用接口,需要提供原始数据文件,排序后的文件,总的数据量及每个子文件需要的数据量。

//外部排序
void sort(string infile, string outfile, int m, int n)
{
	split(infile, m, n);
	merge(outfile, m, n);
}

测试

下面的主函数对以上的代码进行测试,讲解如何使用提供的外部排序代码。同时使用了计时函数对程序的性能进行测试。其中涉及到的头文件请在程序的最开始处添加。
注意,程序产生的临时文件并没有自动删除,允许程序结束后进行查看,并手动删除。

#include <cstdio>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <string>
using namespace std;

int main()
{
	//testbuf();

	clock_t st = clock();

	int m = 100000000, n = 1000000;
	string inFile("data_ori.txt"),outFile("data_sorted.txt");
	genData(inFile, m);
	sort(inFile, outFile, m, n);	

	clock_t ed = clock();
	printf("Time usage: %.2lfs\n", (ed - st) / 1000.0);
}
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论