今晚上电面腾讯的一道算法题,求解

[dwadewyp]

有 1000 个.txt 文件，大小均为 1G,每个文件每行为一个浮点数; 要求: 将 1000 个文件中所有的浮点数按从小到大的顺序排好，放置在一个文件中;

说思路

[murmur]

如果是 utf-8 字符串表示的浮点数，那么如果全装进内存有没有可能加起来小于 1t，已知市面上比较好买的内存最大是单条 128g，这样一台 epyc 或者白金至强服务器带起 1t 内存就可以进行内存排序

腾讯么，不差钱

[liukrystal]

个人提供一种思路，假设可用内存为 1G，那先对依次对每个 1G 文件内的浮点数进行快排，这样得到 1000 个已经排序的大小为 1G 的文件。然后依次扫描每个已经排序的文件，每个文件取出 1M 的内容，这样合起来大概是 1G，再对这些内容进行归并排序，结果写入硬盘，这样依次进行，其实是一种外排序的思路。

[jinhao7773]

先对每个文件排序，再读取每个文件的第一行，对这 1000 个数字进行排序，把最小的那个数字进行 pop，再继续读取 pop 出来的数字的那个文件下一行放到那 1000 个数字里，继续 pop，如此循环，每次 pop 出来的数字写到输出文件里。

[iConnect]

这个问题的结果会生成一个 1T 的 .txt 文件？

[across]

大概想一下，应该要先估算数量。
float 32 位，最多 4294967296(2^32)个数字，建立一个 unint32 的数组（计数上限不能低于 2^32 ），这样内存占用 4294967296 * 4byte = 16G，这样就不用写出写入了。
比较 float 时，直接进行位比较，想等的话对应位数字++，最后完成排序后可以，按对应数字输出一边····· 就好了？ 细节实现可能有问题，IEEE 具体都忘了···

[across]

@across
这样问题可以转化成，将所有 float 数字按顺序一边吧。

[Mohanson]

看题目就是外归并了，反正万能算法：不论大文件去重还是排序，答案都是外归并

[lithbitren]

外排序，一般标答都是纯归并，文件数不多的情况下也可以也可以基于堆做外排序的归并，1000 还是没问题的，嗯大概就是 3 楼那个意思，不过用堆比有序数组更正统，3 楼相当于插入排序了，复杂度还是有区别的。

[xupefei]

@jinhao7773 你这方法复杂度爆表了，因为“对这 1000 个数字进行排序”重复了 n/1000 次。整体复杂度是 n^2 。

[wellsc]

贱指 offer 貌似有这题

[fline]

@xupefei 但整体不还是 nlogn 么……

[xupefei]

@fline 就算 1000 个文件是排过序的，把他们 merge 起来已经是 nlogn 了。

[xupefei]

@xupefei 仔细想了想，3L 如果是用最小堆进行 merge 的时候，最后的复杂度是 2*nlogn，的确是 nlogn 复杂度。

[binux]

@xupefei 但是每次 pop add 一个是插入排序 logn 整体依旧是 nlogn

[yzbythesea]

这不是经典的 merge sort 吗

[raaaaaar]

昨天才看的排序，咋今天就有题了。典型的外排序，归并算法

[jinhao7773]

@xupefei 1000 个数字只需要刚读出来的排一次就行，后面 pop 之后依然是有序的。

[rioshikelong121]

经典的外部排序问题。

[netnr]

把所有行写入数据库(sqlite ），排序导出，根据实际情况分批处理