`
java-mans
  • 浏览: 11741573 次
文章分类
社区版块
存档分类
最新评论

微软笔试题 大型文件外部排序（二路归并和k路归并的实现和比较）

 
阅读更多

这两种排序方法都是先将一个无序的大的外部文件，分成若干块，分别读到内存中。

将每一块都先排好序，放到一个新的外部文件中。

  1. 二路归并的思路是每次将外部排序的文件两两合并，变成一个二倍大小的文件，然后对二倍大小的文件继续两两合并。直到最终合并为一个文件为止。
  2. k路归并是将外部排好序的子文件一次合并。先在各个文件中取出第一个数据，放到一个优先级队列中。然后选出最小的数据输出到外部结果文件里。并从最小数据对应的文件中读取下一个数据。这种方法的关键在于，要将每次从文件中读到的数据和对应的文件关联起来。这样才可以持续的读取。另一个重要的地方在于，当一个文件读取结束时，放置一个最大的数据MAX到优先级队列中当做标记。当某一次从优先级队列中读到的数据是MAX时，表明所有文件都已经读取完毕。结果文件输出完成。

二路归并的C++代码：

////对n(10000000)个整数排序，采用二路归并的方法。每次总是将两个文件合并排序为一个。
string get_file_name(int count_file)
{
	stringstream s;
	s<<count_file;
	string count_file_string;
	s>>count_file_string;
	string file_name="data";
	file_name+=count_file_string;
	return file_name;
}
////用二路归并的方法将n个整数分为每个大小为per的部分。然后逐级递增的合并
//void push_random_data_to_file(const string& filename ,unsigned long number)
//{
//		if (number<100000)
//		{
//			vector<int> a;
//			push_rand(a,number,0,number);
//			write_data_to_file(a,filename.c_str()); 
//		} 
//		else
//		{
//			vector<int> a;
//			const int per=100000,n=number/per;
//			push_rand(a,number%per,0,number);
//			write_data_to_file(a,filename.c_str()); 
//			for (int i=0;i<n;i++)
//			{
//				a.clear();
//				push_rand(a,100000,0,100000);
//				write_data_append_file(a,filename.c_str()); 
//			}
//		}
//}
//void split_data(const string& datafrom,deque<string>& file_name_array,unsigned long per,int& count_file)
//{
//	unsigned long position=0;
//	while (true)	
//	{
//		vector<int> a;
//		a.clear();
//		//读文件中的一段数据到数组中 
//		if (read_data_to_array(datafrom,a,position,per)==true)
//		{
//			break;
//		}
//		position+=per;
//		//将数组中的数据在内存中排序
//		sort(a.begin(),a.end());
//		ofstream fout;
//		string filename=get_file_name(count_file++);
//		file_name_array.push_back(filename);
//		fout.open(filename.c_str(),ios::in | ios::binary);
//		//将排好序的数组输出到外部文件中
//		write_data_to_file(a,filename.c_str());
//		print_file(filename);
//		fout.close();
//	}
//}
//void sort_big_file_with_binary_merge(unsigned long n,unsigned long per)
//{
//	unsigned  long traverse=n/per;
//	vector<int> a;
//	//制造大量数据放入文件中
//	cout<<"对"<<n<<"个整数进行二路归并排序，每一路的大小为"<<per<<endl
//		<<"全部数据被分割放在"<<traverse<<"个文件中"<<endl;
//	
//	SingletonTimer::Instance();
//	//将待排序文件分成小文件，在内存中排序后放到磁盘文件中
//	string datafrom="data.txt";
//	deque<string> file_name_array;
//	int count_file=0;
//	split_data(datafrom,file_name_array,per,count_file);
//
//	SingletonTimer::Instance()->print("将待排序文件分成小文件，在内存中排序后放到磁盘文件中");
//	//合并排序，二路归并的方法。
//	while (file_name_array.size()>=2)
//	{
//		//获取两个有序文件中的内容，将其合并为一个有序的文件，直到最后合并为一个有序文件
//		string file1=file_name_array.front();
//		file_name_array.pop_front();
//		string file2=file_name_array.front();
//		file_name_array.pop_front();
//		string fileout=get_file_name(count_file++);
//		file_name_array.push_back(fileout);
//		merge_file(file1,file2,fileout);
//		print_file(fileout);
//	}
//	SingletonTimer::Instance()->print("获取两个有序文件中的内容，将其合并为一个有序的文件，直到最后合并为一个有序文件");
//	cout<<"最终的文件中存放所有排好序的数据，其中前一百个为："<<endl;
//	print_file(file_name_array.back(),100);
//
//}


k路归并的C++代码：

////k路归并排序大文件1000*10000
//
//void write_random_data_to_file(unsigned long number)
//{
//	cout<<"writing "<<number<<" to file data ..."<<endl;
//	unsigned  long traverse=number/100000;
//	cout<<traverse<<"s times have to write."<<endl;
//	////制造大量数据放入文件中
//	vector<int> a;
//	if (number<100000)
//	{
//		push_rand(a,number,0,number);
//		write_data_to_file(a,"data"); 
//	}
//	else
//	{
//		push_rand(a,100000,0,1000000);
//		write_data_to_file(a,"data"); 
//		cout<<"the "<<0<<" times finished."<<endl;
//		for (unsigned long i=1;i<traverse;i++)
//		{
//			a.clear();
//			push_rand(a,100000,0,100000);
//			write_data_append_file(a,"data"); 
//			cout<<"the "<<i<<" times finished."<<endl
//				<<(traverse-1-i)<<" times left."<<endl;
//		}
//	}
//	cout<<number<<" integers wrote to file data finished."<<endl;
//	///////////////////TEST/////////////////
//	//print_file("data",100);
//	//sort(a.begin(),a.end());
//	//print(a.begin(),a.end());
//}
//list<string> divide_big_file_into_small_sorted_file(long number)
//{
//	vector<int> a;
//	a.clear();
//	long position=0;
//	int count_file=0;
//	list<string> file_name_array;
//	//get part files and file names
//	while (true)
//	{
//		a.clear();
//		if (read_data_to_array("data.txt",a,position,number)==true)
//		{
//			break;
//		}
//		position+=number;
//		sort(a.begin(),a.end());
//		string filename=get_file_name(count_file++);
//		file_name_array.push_back(filename);
//		write_data_to_file(a,filename.c_str());
//		cout<<"sorted file"<<(count_file-1)<<" builded."<<endl;
//	}
//
//	return file_name_array;
//}
//void k_way_merge_sort(const list<string>& file_name_array)
//{
//
//	//get ifstreams and put them to list<ifstream> readfiles
//	vector<ifstream> readfiles;
//	for (list<string>::const_iterator i=file_name_array.begin();
//		i!=file_name_array.end();i++)
//	{
//		readfiles.push_back(ifstream());
//		readfiles.back().open(i->c_str(),ios::binary | ios::in );
//	}
//	//init priority queue by read one data from each file
//	//初始化优先队列：从每个文件中读取第一个数据
//	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int> > > prioritydata;
//	for (vector<ifstream>::size_type i=0;
//		i<readfiles.size();i++)
//	{
//		int temp;
//		readfiles[i].read(reinterpret_cast<char*>(&temp),sizeof(int));
//		prioritydata.push(make_pair(temp,i));
//	}
//	//merge sort file
//	ofstream fout;
//	fout.open("result",ios::binary);
//	while (true)
//	{
//		int onedata=prioritydata.top().first;
//		if (onedata==numeric_limits<int>().max())
//		{
//			break;
//		}
//		else
//		{
//
//			fout.write(reinterpret_cast<const char*>(&onedata),sizeof(int));
//			//从第i个文件中读取一个整数
//			int i=prioritydata.top().second;
//			prioritydata.pop();
//			int temp;
//			readfiles[i].read(reinterpret_cast<char*>(&temp),sizeof(int));
//			if (readfiles[i].eof())
//			{
//				//当此文件读到最后结束时，放入标记到优先级队列中
//				prioritydata.push(make_pair(numeric_limits<int>().max(),i));
//			}
//			else
//			{
//				//否则将读取到的数据直接放到优先级队列中
//				prioritydata.push(make_pair(temp,i));
//			}
//		}
//	}
//	//关闭所有打开的文件
//	fout.close();
//	for (vector<ifstream>::size_type i=0;
//		i<readfiles.size();i++)
//	{
//		readfiles[i].close();
//	}
//}
//void sort_big_file_with_k_way_merge(unsigned long n,unsigned long partitionfilesize)
//{
//	
//	//write_random_data_to_file(n);
//	timer t;
//	k_way_merge_sort(divide_big_file_into_small_sorted_file(partitionfilesize));
//	//将待排序文件分成小文件，在内存中排序后放到磁盘文件中
//	//假设内存只有1MB，26W个整数
//	cout<<n/partitionfilesize<<"路归并排序大文件 "<<n<<" ,内存一次排序 "<<partitionfilesize<<endl;
//	print(t.elapsed());
//	print("秒");
//	print_file("result",1000);
//}


输出结果及其比较：

K路归并

4路

209秒

8路

190秒

16路

223秒

二路归并

4个子文件

257秒

8个子文件

281秒

从上面多次实验结果来看，在外部排序时，二路归并的方法不是最优的。因为它每次总是合并两个文件，这样做造成了全部数据被遍历的次数比较多。在外部排序中，由于数据量比较大，所以遍历的次数直接影响了排序的时间。而k路归并强调一次将k个排好序的子文件合并为一个最终的结果文件，所以，遍历了文件两次，读一次，写一次。其他的时间主要花在优先级队列的出队，入队的调整上。所以k的值不能过大，太大，导致调整堆占用了过多的时间，太小导致内部排序占用过大内存。上面的结果说明，8路归并排序速度最快。

分享到：
| C++学习之继承
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    搜狗2010招聘笔试题

    4. **外部排序算法：多路归并排序** - **外部排序**：由于数据量太大，无法一次性加载到内存中进行排序，需要通过磁盘I/O操作完成。 - **多路归并排序**：将大文件分割成多个小文件，在内存中分别进行排序，然后...

    百度笔试题 百度笔试题

    外部排序是大数据处理的关键技术，可能使用多路归并排序或其他外部存储友好的算法。 8. **二叉树链接叶子节点**： 将二叉树的所有叶子节点链接起来。这可以通过深度优先搜索（DFS）或广度优先搜索（BFS）实现，...

    JAVA软件工程师笔试题

    JAVA软件工程师笔试题涵盖了许多Java基础、性能优化、系统分析设计、软件工程、数据库理论以及智力题等多个方面。以下是对这些知识点的详细说明： 1. **Interface与Abstract Class的区别**： - 接口（Interface）...

    软件工程师笔试题 .doc

    由于数据量大（10万个），可以考虑使用外部排序算法，如多路归并排序，先分块读取成绩，对每个块进行内部排序，然后合并这些已排序的块。 三、综述题： 1. ARM9是ARM公司设计的一种32位RISC处理器内核，采用冯·...

    华为Java笔试题 面试笔试题大汇总

    同时，熟悉排序算法（如冒泡排序、快速排序、归并排序等）和搜索算法（如二分查找、深度优先搜索、广度优先搜索等）也是必不可少的。 对于Java集合框架的理解也非常重要。List、Set、Queue和Map接口以及它们的实现...

    笔试\百度-2009-科大-笔试题

    第二题要求在O(N)时间内完成排序，且空间复杂度为O(1)，可以使用外部排序，如多路归并排序，将文件分成若干块，每块内部排序，然后逐块合并。 **系统设计题** 这道题目要求设计一个链接分发程序，将数据均匀分配到...

    百度笔试题2009年

    7. **外部排序**：在有限内存条件下对大量电话号码排序，可能需要使用多路归并排序或磁盘排序算法。 8. **二叉树操作**：连接二叉树的叶子节点，可以通过层次遍历（广度优先搜索）实现。 9. **字典序最小排列**：...

    去哪儿网2013笔试题

    【去哪儿网2013笔试题】主要针对的是软件开发工程师的能力考察，涵盖了算法、文件处理、数据库管理和问题解决等多个方面。以下是对这些题目中涉及的知识点的详细解析： 1. **相对地址转化为绝对地址**：这是一个...

    百度2008笔试题，华中科技大等5套

    可以采用外部排序的方法，比如多路归并排序。先将文件分割成多个小块，对每个小块内部进行排序，然后合并这些小块，确保总体时间复杂度为O(N)。 - **常数空间排序**：要求O(1)空间复杂度的排序算法，可以考虑原地...

    各种查找与排序算法-笔试面试必备

    根据算法的工作原理和效率，可以分为内部排序和外部排序。 ##### 2.1 内部排序 内部排序是指数据全部在内存中完成排序的过程。常见的内部排序算法有插入排序、Shell排序、堆排序、冒泡排序、快速排序、归并排序等...

    2009-百度笔试题

    第一个要求在读取文件次数为 O(N) 的限制下进行排序，可以使用外部排序算法，如多路归并排序。第二个问题则要求读写文件次数为 O(N)，空间复杂度为 O(1)，这可能需要使用原地排序算法，如冒泡排序或快速选择排序，但...

    最新秋招360笔试题.docx

    4. 若外部存储上有3110400个记录，做6路平衡归并排序，计算机内存工作区能容纳400个记录，则排序好所有记录，需要作几趟归并排序（C） 知识点：算法设计、归并排序、时间复杂度分析 5. 以下程序段预实现计算prod=...

    百度校园招聘笔试试题.doc

    可以使用分治策略、分布式计算或外部排序来处理大数据量。为了提高效率，可以采用哈希表预先对 URL 的 domain、site 进行预处理，减少排序中的比较次数，再进行排序。 3. 从缓存效率角度看，A 段代码可能更好，因为...

    几个搜狗招聘笔试题，对找工作有帮助。

    多路归并排序是最常用的方法，它将大文件分成若干个小文件，分别在内存中进行排序，然后将这些已排序的小文件合并成一个大文件，实现整体的排序。 Q9: 在对空间和时间都有限制的实时系统中，常使用的排序算法？ ...

    阿里巴巴2014年笔试题.pdf

    15. 归并排序：使用多路归并排序，若要求三趟归并完成，根据归并趟数公式s=logk(m)，代入m=100和s=3，解得k=5。 16. 文件排序：对于n个元素的文件，若要三趟归并完成排序，归并路数至少为5，因为log5(100) ≦ 3。 ...

    腾讯2009笔试题电子科技大学

    2. **排序算法**：题目中提到了稳定性和不稳定性的排序方法，比如归并排序、基数排序是稳定的，而插入排序、希尔排序、堆排序、快速排序、选择排序和冒泡排序中，除了归并排序和基数排序，其余都是不稳定的。...

    朝歌宽带笔试题_嵌入式-常用知识&面试题库_大厂面试真题.doc

    - 二路归并排序是将两个已排序的子序列合并成一个有序序列的过程，其时间复杂度为O(nlogn)，是一种稳定的排序算法。 10. **快速排序**： - 快速排序由高斯·帕特里克·兰道夫·富兰克林发明，采用分治策略，通过...

    京东校园招聘笔试题.docx

    - **内存限制下的排序**：在内存有限的情况下，适合使用外部排序，如归并排序。因此，A是最佳选择，尽管插入排序和冒泡排序在某些情况下可能更优，但它们无法处理大规模数据。 6. **TCP/IP协议**： - **TCP/IP...

    应聘软件开发的笔试题，

    归并排序和基数排序是稳定的排序算法，而堆排序、快速排序、选择排序和希尔排序则不是。 #### 多级存储体系 - 在多级存储体系中，“Cache-主存”结构主要用于缓解主存与CPU之间的速度不匹配问题，提高数据访问速度...

    2021年京东财务校招笔试题答案.pdf

    【京东财务校招笔试题答案解析】 1. **操作系统死锁**：死锁是指两个或多个并发进程在执行过程中，因争夺资源而造成的一种互相等待的现象。四个必要条件包括：互斥条件（资源不可共享）、占有并等待条件（已占有...

Magicbox
Global site tag (gtag.js) - Google Analytics