s*****l
发帖数: 9 | 1 第四版10.4
Imagine you have a 20GB file with one string per line. Explain how you
would sort the file.
答案是external sort,先分若干chunk,把每个chunk放到memory里sort后放回去,然后再
merge.
我的疑问是
1）答案是one chunk by one chunk 的merge,这是不是代表不需要其他空间来merge,就
是速度慢了点，假设memory的size是1GB，是不是代表merge 20次？
2）如果采取20个一起merge的话，是不是系统还要再给个20GB的disk的临时空间,以便
存merge后的结果再放回去?
谢谢啦 | x*******6
发帖数: 262 | 2 N-way merge理论上只需要o（n）空间就行了 | s*****l
发帖数: 9 | 3 hi,谢谢回复，能否以这道题举个例子？就是回答一下我的两个问题~
谢谢啦~ | g**u
发帖数: 504 | 4 N-way merge 空间是怎么用的，我也一直不大明白。可以做到 in place 吗?
【在 x*******6 的大作中提到】
: N-way merge理论上只需要o（n）空间就行了
| p*****2
发帖数: 21240 | 5
20个一起merge只是需要O(20)的空间就可以了。
【在 s*****l 的大作中提到】
: 第四版10.4
: Imagine you have a 20GB file with one string per line. Explain how you
: would sort the file.
: 答案是external sort,先分若干chunk,把每个chunk放到memory里sort后放回去,然后再
: merge.
: 我的疑问是
: 1）答案是one chunk by one chunk 的merge,这是不是代表不需要其他空间来merge,就
: 是速度慢了点，假设memory的size是1GB，是不是代表merge 20次？
: 2）如果采取20个一起merge的话，是不是系统还要再给个20GB的disk的临时空间,以便
: 存merge后的结果再放回去?
|
|
