x*****0
发帖数: 452 | 1 有两个很大的排好序的文件（不能放进内存），目标就是合并这两个文件。例如：
File 1:
beer
coke
redbull
File2:
cheeseburger
sandwich
taco
The output file should be:
beer
cheeseburger
coke
redbull
sandwich
taco
这道题最直接的思路当然就是一行行的读然后比较。请问有什么办法可以加速的吗？ |
s***c
发帖数: 639 | 2 external sort
【在 x*****0 的大作中提到】
: 有两个很大的排好序的文件（不能放进内存），目标就是合并这两个文件。例如：
: File 1:
: beer
: coke
: redbull
: File2:
: cheeseburger
: sandwich
: taco
: The output file should be:
|
x*******9
发帖数: 138 | 3 每次读文件都需要sys call，我们可以通过batching，即一次读多行来averaging这个
复杂度。
读写文件都是IO操作，排序是CPU操作，可以通过multi-thread或者asynchronous来提
高CPU利用率。
然后可以换用SSD获取更高的IO效率。不过顺序读的话，效果不大。
没想到别的了。求大神指点 。 |
x*****0
发帖数: 452 | 4 "读写文件都是IO操作，排序是CPU操作，可以通过multi-thread或者asynchronous来提
高CPU利用率"
请问是指：一个线程负责IO，再开一个线程负责排序吗？
【在 x*******9 的大作中提到】
: 每次读文件都需要sys call，我们可以通过batching，即一次读多行来averaging这个
: 复杂度。
: 读写文件都是IO操作，排序是CPU操作，可以通过multi-thread或者asynchronous来提
: 高CPU利用率。
: 然后可以换用SSD获取更高的IO效率。不过顺序读的话，效果不大。
: 没想到别的了。求大神指点 。
|
x*****0
发帖数: 452 | 5 "读写文件都是IO操作，排序是CPU操作，可以通过multi-thread或者asynchronous来提
高CPU利用率"
请问是指：一个线程负责IO，再开一个线程负责排序吗？
【在 x*******9 的大作中提到】
: 每次读文件都需要sys call，我们可以通过batching，即一次读多行来averaging这个
: 复杂度。
: 读写文件都是IO操作，排序是CPU操作，可以通过multi-thread或者asynchronous来提
: 高CPU利用率。
: 然后可以换用SSD获取更高的IO效率。不过顺序读的话，效果不大。
: 没想到别的了。求大神指点 。
|
A*******e
发帖数: 2419 | 6 两路归并，你还想咋样？
【在 x*****0 的大作中提到】
: 有两个很大的排好序的文件（不能放进内存），目标就是合并这两个文件。例如：
: File 1:
: beer
: coke
: redbull
: File2:
: cheeseburger
: sandwich
: taco
: The output file should be:
|
x*****0
发帖数: 452 | 7 其实就想看看多线程处理，比如一个线程负责io，一个负责sort，能不能speed up
【在 A*******e 的大作中提到】
: 两路归并，你还想咋样？
|
l******s
发帖数: 3045 | 8 那个“不能放进内存“的说明如何允许你同时做以下的多线程？
【在 x*****0 的大作中提到】
: 其实就想看看多线程处理，比如一个线程负责io，一个负责sort，能不能speed up
|
x*****0
发帖数: 452 | 9 不知道这样行不行。不能全部放入内存，但是可以部分放入内存。
三个buffer，其中两个负责存储分别从文件中
读来的数据（每次读整个buffer size的数据），
另一个负责存储sort结果。
开一个线程负责两个buffer的读，并且排序。
开另一个线程负责写第三个buffer（一旦满了以后）中的数据到结果文件中，
并且负责清空。
【在 l******s 的大作中提到】
: 那个“不能放进内存“的说明如何允许你同时做以下的多线程？
|
D***r
发帖数: 7511 | 10 我遇到过类似问题
说有些数需要排序，但是需要的空间是最大内存的十倍，应该怎么办 |
l******s
发帖数: 3045 | 11 how about idea of Merge Sort
【在 D***r 的大作中提到】
: 我遇到过类似问题
: 说有些数需要排序，但是需要的空间是最大内存的十倍，应该怎么办
|
x*****0
发帖数: 452 | 12 external sort 应该可以
【在 D***r 的大作中提到】
: 我遇到过类似问题
: 说有些数需要排序，但是需要的空间是最大内存的十倍，应该怎么办
|
D***r
发帖数: 7511 | 13 对，我那个时候学识浅，不知道external sort
但是也想到了分批sort然后写入外存，然后再merge，意思是一样的
然后他就问怎么从文件里读一部分数据什么的
【在 x*****0 的大作中提到】
: external sort 应该可以
|
n*******s
发帖数: 17267 | 14 这是让你买MapReduce的门票吗？
既然文件都很大， 是不是可以按26个字母把每个文件先chop, chop, 然后多进程搞搞？ |
