2 luyi2 luyi2 于 2016.03.29 22:10 提问

如何将多个文件(每个文件大于1G)字符串进行行为单位排序,并且排序时内存小于50M.

现有N个文件(N>5):
• 每个文件包含了多行的字符串
• 每个文件大小大于1G
• 文件内字符串随机排列
要求实现:一个外部排序算法,以行为单位排序,满足以下需求:
需求
• 用C/C++/Java/C#实现
• 提供编译文件,如:
o GNU Makefile
o Visual Studio 工程文件
o Eclipse工程文件
o MAVEN文件等
• 编译文件需要生成两个可执行文件,且满足下文的接口需求:
o 测试文件生成程序: filesort_testgen
o 排序程序: filesort
• 排序程序使用内存不能大于50M
• 提供README文件,内容至少包括如何编译工程
filesort_testgen命令行接口
filesort_testgen FILE_COUNT LINES_PER_FILE PREFIX
其中:
• filesort_testgen为可执行文件名
• FILE_COUNT为需要生成的待排序文件的个数
• LINES_PER_FILE:每个待排序文件的行数
• PREFIX为生成文件的前缀
• 执行结果 其中${PREFIX}表示PREFIX参数的值
o 生成: ${PREFIX}1 ${PREFIX}2 ${PREFIX}3,
例子:

filesort_testgen 5 1000000 unsorted
Generated unsorted files:
unsorted1
unsorted2
unsorted3
unsorted4
unsorted5
结果会生出 unsorted1 unsorted2 unsorted3 unsorted4 unsorted5
filesort命令行接口
filesort INPUT_FILE_1 INPUT_FILE_2 ... OUTPUT_FILE
其中:
• INPUT_FILE_1表示输入文件的文件名(或路径)
• OUTPUT_FILE表示输出文件的文件名
• 执行结果:
o 输出排序完的文件
o 输出使用了多少内存
filesort unsorted1 unsorted2 unsorted3 unsorted4 unsorted5 sorted
Generate sorted file: sorted
Used memory: 4553333 B (4.34 M)
结果会生出排序后的文件sorted,并输出内存使用情况

2个回答

lx624909677
lx624909677   Ds   Rxr 2016.03.29 23:07

排序内存小于50M是什么意思?是说这个排序过程中不允许占用超过50M的内存么?那就只能一部分一部分的排序,之后写入临时文件,然后再读临时文件继续排序

bai596140538
bai596140538   2016.03.30 09:06

给你提供一个思路,你网上看看topk和桶排序

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
排序算法学习(3)
1.优化的起泡排序的排序趟数与参加排序的序列原始状态有关。(正确) 2.对任何用顶点表示活动的网络(AOV网)进行拓扑排序的结果都是唯一的。(错误) 3.在分配排序时,最高位优先分配法比最低位优先分配法简单。(错误) 4.在排序算法中每一项都与其他各项进行比较,计算出小于该项的项的个数,以确定该项的位置叫:枚举排序。   枚举排序,通常也被叫做秩排序,算法基本思想
海量数据的排序
前面提到的排序算法都是一些内排序算法,针对的是数据可以一次全部载入内存中的情况。但是面对海量数据,即数据不可能一次全部载入内存,需要用到外排序的方法。外排序采用分块的方法,首先将数据分块,对块内数据按选择一种高效的内排序策略进行排序。然后采用归并排序的思想对于所有的块进行排序,得到所有数据的一个有序序列。 例如,考虑一个1G文件,可用内存100M的排序方法。首先将文件分成10个100M,并依次载
海量数据排序——如果有1TB的数据需要排序,但只有32GB的内存如何排序处理?
1、外排序   传统的排序算法一般指内排序算法,针对的是数据可以一次全部载入内存中的情况。但是面对海量数据,即数据不可能一次全部载入内存,需要用到外排序的方法。外排序采用分块的方法(分而治之),首先将数据分块,对块内数据按选择一种高效的内排序策略进行排序。然后采用归并排序的思想对于所有的块进行排序,得到所有数据的一个有序序列。  例如,考虑一个1G文件,可用内存100M的排序方法。首先将文件分成
84 有 10个文件,每个文件1G 按照 query 的频度排序
3.有 10  个文件,每个文件 1G, 每个文件的每一行都存放的是用户的 query,每个文件的 query 都可能重复。 要求按照 query  的频度排序. /* 3.有 10 个文件,每个文件 1G, 每个文件的每一行都存放的是用户的 query,每个文件的 query 都可能重复。 要求按照 query 的频度排序. 典型的TOP K算法,解决方案如下: 方案1: 顺
【算法】对一个20GB大的文件排序
设想你有一个20GB的文件,每行一个字符串,说明如何对这个文件进行排序。 内存肯定没有20GB大,所以不可能采用传统排序法。但是可以将文件分成许多块,每块xMB,针对每个快各自进行排序,存回文件系统。 然后将这些块逐一合并,最终得到全部排好序的文件。 外排序的一个例子是外归并排序(External merge sort),它读入一些能放在内存内的数据量,在内存中排序后输出为一个顺串(
linux下如何查找文件大小大于n的几个文件
<br />//查找当前目录下文件大小大于1m的文件列表<br />find . -size +2046
大数据小内存排序
需求:有一个很大的文件需要对内容进行排序(ps:内容可简单理解为数字),如何在有限的内存下进行排序,内存很小。 分析: 1.文件很大我们需要分而治之,分为若干文件 2.内存小,划分小文件的时候要注意,文件内容应该可以足够放入内存 3.拆分小文件的时候,对改文件内容进行排序(ps:非本文章重点故省略) 4.对有序的文件进行归并排序以上就是大致的思路,下面直接上代码,代码略有粗糙,各位看客包涵
对一个无法一次读入内存的大文件进行排序的代码实例
基本思想:将大文件分割成小文件,对每个小文件进行排序,最后合并所有小文件
磁盘排序
转自大神 博客:http://blog.csdn.net/v_JULY_v/article/details/6451990 作者:July,yansha,5,编程艺术室。 出处:http://blog.csdn.net/v_JULY_v 。前奏 经过几天的痛苦沉思,最终决定,把原程序员面试题狂想曲系列正式更名为程序员编程艺术系列,同时,狂想曲创作组更名为编程艺术室。之所以要改名,我们考虑到三
给两个文件,分别有100亿个URL,我们只有1G内存,如何找到两个文件交集?分别给出精确算法和近似算法。
思路分析1G内存为10亿字节,所以无法把100亿直接载入内存,所以我们可以通过哈希与位图的结合来处理该问题。先哈希到位图上,在把俩个位图按位与求其交集。解法1.我们可以申请100个vector空间,每一个vector空间保存初始化过的1亿个无符号整数。 2.用字符串哈希函数对每个url的MD5结果进行哈希,然后把字符串哈希函数得到的整数结果再进行二次哈希,每个整数都模上100,把该结果作为vect