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币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!