s********a
发帖数: 2796 | 1 If you have a 2 GB file with one string per line, which sorting algorithm
would you use to sort the file and why?
书里给出的解法是：
1. Divide the file into K chunks, where X * K = 2 GB. Bring each chunk into
memory and sort the lines as usual using any O(n log n) algorithm. Save the
lines back to the file.
2. Now bring the next chunk into memory and sort.
3. Once we’re done, merge them one by one.
其中一个假定是每次不使用超过X的memory,但是最后一步怎么能满足这个条件呢？ |
M********6
发帖数: 67 | 2 这个是external sorting吧
merge阶段的buffer是不超过memory的 |
l*********d
发帖数: 78 | 3 比如说有 9G 的 file, 但是内存只有 1G。
首先分成 9段，每段 1G。分段读入内存排序，写到临时的文件。
归并阶段，对每个排好序的小段，读入 100M，总共 900 M，然后用剩下的 100M 作为
buffer。
每次 buffer 满了就写入到最终的文件。 |
M********6
发帖数: 67 | 4 merge的时候每当output buffer满就输出写一次，每当input buffer空就从相应input
读一次 |
s******c
发帖数: 99 | 5 最后一步是multi-way merge，这时每一行已经是排好序的，分别取每行的第一个data
（最小），拿到内存里，所以是K个data在内存，只要k < x 就没有问题。整个merge过
程建一个heap,每次找到最小的元素，写到output里，同时最小的元素从哪一行来的，
就从那一行再取下一个元素，然后maintain这个heap，再找到最小的继续写到output。
最后直到这个heap空了为止 |
