这是一个创建于 1459 天前的主题，其中的信息可能已经有所发展或是发生改变。
有 1000 个.txt 文件，大小均为 1G,每个文件每行为一个浮点数; 要求: 将 1000 个文件中所有的浮点数按从小到大的顺序排好，放置在一个文件中;
说思路
 |
1
murmur 2020-12-02 23:44:30 +08:00
如果是 utf-8 字符串表示的浮点数，那么如果全装进内存有没有可能加起来小于 1t，已知市面上比较好买的内存最大是单条 128g，这样一台 epyc 或者白金至强服务器带起 1t 内存就可以进行内存排序
腾讯么，不差钱 |
 |
2
liukrystal 2020-12-02 23:53:27 +08:00 via iPhone
个人提供一种思路，假设可用内存为 1G，那先对依次对每个 1G 文件内的浮点数进行快排，这样得到 1000 个已经排序的大小为 1G 的文件。然后依次扫描每个已经排序的文件，每个文件取出 1M 的内容，这样合起来大概是 1G，再对这些内容进行归并排序，结果写入硬盘，这样依次进行，其实是一种外排序的思路。
|
 |
3
jinhao7773 2020-12-03 00:00:03 +08:00 via iPhone  7
先对每个文件排序，再读取每个文件的第一行，对这 1000 个数字进行排序，把最小的那个数字进行 pop，再继续读取 pop 出来的数字的那个文件下一行放到那 1000 个数字里，继续 pop，如此循环，每次 pop 出来的数字写到输出文件里。
|
 |
4
iConnect 2020-12-03 00:06:22 +08:00 via Android
这个问题的结果会生成一个 1T 的 .txt 文件？
|
 |
5
across 2020-12-03 00:23:58 +08:00
大概想一下，应该要先估算数量。
float 32 位，最多 4294967296(2^32)个数字，建立一个 unint32 的数组（计数上限不能低于 2^32 ），这样内存占用 4294967296 * 4byte = 16G，这样就不用写出写入了。 比较 float 时，直接进行位比较，想等的话对应位数字++，最后完成排序后可以，按对应数字输出一边····· 就好了？ 细节实现可能有问题，IEEE 具体都忘了··· |
 |
7
Mohanson 2020-12-03 00:35:39 +08:00 via Android
看题目就是外归并了，反正万能算法：不论大文件去重还是排序，答案都是外归并
|
 |
8
lithbitren 2020-12-03 01:31:16 +08:00
外排序，一般标答都是纯归并，文件数不多的情况下也可以也可以基于堆做外排序的归并，1000 还是没问题的，嗯大概就是 3 楼那个意思，不过用堆比有序数组更正统，3 楼相当于插入排序了，复杂度还是有区别的。
|
 |
9
xupefei 2020-12-03 01:40:20 +08:00
@jinhao7773 你这方法复杂度爆表了，因为“对这 1000 个数字进行排序”重复了 n/1000 次。整体复杂度是 n^2 。
|
 |
10
wellsc 2020-12-03 01:45:23 +08:00 via iPhone
贱指 offer 貌似有这题
|
|
13
xupefei 2020-12-03 02:46:27 +08:00
@xupefei 仔细想了想，3L 如果是用最小堆进行 merge 的时候，最后的复杂度是 2*nlogn，的确是 nlogn 复杂度。
|
 |
15
yzbythesea 2020-12-03 04:17:11 +08:00
这不是经典的 merge sort 吗
|
 |
16
raaaaaar 2020-12-03 07:24:52 +08:00 via Android
昨天才看的排序，咋今天就有题了。典型的外排序，归并算法
|
|
17
jinhao7773 2020-12-03 07:28:38 +08:00 via iPhone
@xupefei 1000 个数字只需要刚读出来的排一次就行，后面 pop 之后依然是有序的。
|
 |
18
rioshikelong121 2020-12-03 08:56:56 +08:00
经典的外部排序问题。
|
 |
19
netnr 2020-12-03 09:03:10 +08:00 via Android
把所有行写入数据库(sqlite ），排序导出，根据实际情况分批处理
|
Select Language