c********p
发帖数: 1969 | 1 空间不够，文件太大。分成几个chunk排序，然后把chunk两两merge。
可是，每个chunk的大小和memory一样大。那merge的时候，怎么merge啊？因为只能
merge一半，而且，根本读不下2个chunk啊。。。
看到这里，非常confused...
求牛人开导。 |
h**o
发帖数: 548 | 2 干嘛不让每个chunk的大小和 1/2 memory一样大
【在 c********p 的大作中提到】
: 空间不够，文件太大。分成几个chunk排序，然后把chunk两两merge。
: 可是，每个chunk的大小和memory一样大。那merge的时候，怎么merge啊？因为只能
: merge一半，而且，根本读不下2个chunk啊。。。
: 看到这里，非常confused...
: 求牛人开导。
|
h**o
发帖数: 548 | 3 干嘛不让每个chunk的大小和 1/2 memory一样大
【在 c********p 的大作中提到】
: 空间不够，文件太大。分成几个chunk排序，然后把chunk两两merge。
: 可是，每个chunk的大小和memory一样大。那merge的时候，怎么merge啊？因为只能
: merge一半，而且，根本读不下2个chunk啊。。。
: 看到这里，非常confused...
: 求牛人开导。
|
c********p
发帖数: 1969 | 4 可是两两merge了之后还不是一样的问题。。。
【在 h**o 的大作中提到】
: 干嘛不让每个chunk的大小和 1/2 memory一样大
|
g*********e
发帖数: 14401 | 5 不要把整个chunk读进来
读一部分 然后merge 空间用光了就把当前结果写到硬盘上 继续读 merge ... |
h**o
发帖数: 548 | 6 http://en.wikipedia.org/wiki/External_sorting
please read from step 4.
【在 c********p 的大作中提到】
: 可是两两merge了之后还不是一样的问题。。。
|
n*******k
发帖数: 100 | 7 你是求理论解释，还是相关代码啊？
【在 c********p 的大作中提到】
: 空间不够，文件太大。分成几个chunk排序，然后把chunk两两merge。
: 可是，每个chunk的大小和memory一样大。那merge的时候，怎么merge啊？因为只能
: merge一半，而且，根本读不下2个chunk啊。。。
: 看到这里，非常confused...
: 求牛人开导。
|
c********p
发帖数: 1969 | 8 both
您都说说吧，谢谢！
【在 n*******k 的大作中提到】
: 你是求理论解释，还是相关代码啊？
|
D****6
发帖数: 278 | 9 merge一部分，放进一个file,merge下一部分，append进同一个file,一直到完，那个
file不就是sorted吗。 |
c********p
发帖数: 1969 | 10 比如5个file，一共要两两比较多少次？
【在 D****6 的大作中提到】
: merge一部分，放进一个file,merge下一部分，append进同一个file,一直到完，那个
: file不就是sorted吗。
|
|
|
D****6
发帖数: 278 | |
c********p
发帖数: 1969 | 12 怎么会是4次啊？
比如array 1 和array2 比较了之后 array 1里放的都是比array2小的，
然后array 3再和array1比较，array1里边放的是比array3小的，但未必array 3放的是
比array 2小的。。。
这样下去，，要比较多少次？
另外，又想起来一个问题，怎样in place的sort两个sorted array啊，就算是merge
sort也不是in place的。
【在 D****6 的大作中提到】
: 四次。你纠结在哪？
|
c********p
发帖数: 1969 | 13 我确实纠结死了。。
【在 D****6 的大作中提到】
: 四次。你纠结在哪？
|
D****6
发帖数: 278 | 14 首先每个array都是sorted是吧，arr1和2merge完之前没其他arr的事啊，完后生成新的
sorted arr在和3 merge. 还有为什么“ array 1里放的都是比array2小的”？你来个
简单的实际的例子。 |
c********p
发帖数: 1969 | 15 arr1 和 arr2 merge之后生成的是2个array 还是1个array，因为memory不够大不是么
。。。
【在 D****6 的大作中提到】
: 首先每个array都是sorted是吧，arr1和2merge完之前没其他arr的事啊，完后生成新的
: sorted arr在和3 merge. 还有为什么“ array 1里放的都是比array2小的”？你来个
: 简单的实际的例子。
|
D****6
发帖数: 278 | 16 一个，但不是array,是write到disk里的一个file. 你是说external merge sort吧？
【在 c********p 的大作中提到】
: arr1 和 arr2 merge之后生成的是2个array 还是1个array，因为memory不够大不是么
: 。。。
|
i****y
发帖数: 84 | 17 你用了min heap。。lz意思是不用min heap直接merge sort？
【在 n*******k 的大作中提到】
: 你是求理论解释，还是相关代码啊？
|
n*******k
发帖数: 100 | 18 如果一直是两两merge应该不难吧。
【在 i****y 的大作中提到】
: 你用了min heap。。lz意思是不用min heap直接merge sort？
|
n*******k
发帖数: 100 | 19 就老老实实的取2个文件f1，f2（比如整数）的头元素放在变量v1，v2里面，较小的值
写入磁盘结果文件，（判断读完与否，feof() ）
while(f1未读完且f2也未读完)
如果v1 <= v2， fwrite(&v1,4Byte,1,res_file)，从f1读取下一个数；
否则fwrite(&v2,4Byte,1,res_file),从f2读取下一个数。
if (f1读完，f2没被读完)
flush f2剩余元素进入res_file
if (f2读完，f1没被读完)
flush f1剩余元素进入res_file
这样不就行了吗？
fread/fwrite可以利用文件缓冲区。如果自己想偷懒，不想切文件，定义和管理文件缓
冲区，直
接这样用就可以了。出来的文件就是globally sorted。 |
t***t
发帖数: 6066 | |
c********p
发帖数: 1969 | 21 狗狗每次都考它？那我更要赶紧问问了啊。。。
【在 t***t 的大作中提到】
: 多路归并排序，不是标准的么？狗狗几乎必考啊。
|
