w******1
发帖数: 520 | 1 如何处理几个文件的合并排序问题
几个文件都很大， 每个文件都是一行行排好序的字符串序列组成的，
如果把这个几个文件合成一个大文件， 也必须是一行行排好序的， 怎么做比较快呢？ |
w******1
发帖数: 520 | 2 我的想法是因为每个文件都是排好序的，
那么我是把每个文件存到ARRAY，
从头开始， 从每个ARRAY 的第一个开始比较。
被选中的最小值的行， 写入新的文件， 指针下行。
但是， 因为文件中存的是字符串， 而不是数据， 这个比较起来， 就很慢了。 |
g*******y
发帖数: 1930 | 3 google yixia external sort |
w******1
发帖数: 520 | 4 谢谢楼上的。
我用 external sort
结果被说是不SMART的一个方法。 拒了。
因为这是大文件系统。 |
g*******y
发帖数: 1930 | 5 then what's smarter way?
external sort cost is already minimal (in terms of I/O disk cost).
maybe you didn't describe clearly?
【在 w******1 的大作中提到】
: 谢谢楼上的。
: 我用 external sort
: 结果被说是不SMART的一个方法。 拒了。
: 因为这是大文件系统。
|
w******1
发帖数: 520 | 6 他说这个是可以的，能用。 但是不够SMART。不是他们想要的。
所以不考虑， MOVE ON.
这个输入的文件是几百GB的几个大文件。 已经按照时间排好序的， 要合成一个大的排
序文件。 |
g*******y
发帖数: 1930 | 7 那你把题目说清楚看看有没有其他的方法，
什么叫做一行行排好序的字符串，到底是对字符串排序还是按时间排序？
一行是一个record with 2个field，一个是char array，一个是time stamp？
sort的方法就那么些，他的方法能smart到哪儿去?
【在 w******1 的大作中提到】
: 他说这个是可以的，能用。 但是不够SMART。不是他们想要的。
: 所以不考虑， MOVE ON.
: 这个输入的文件是几百GB的几个大文件。 已经按照时间排好序的， 要合成一个大的排
: 序文件。
|
H*M
发帖数: 1268 | 8 小尾羊TX,你也申请作版主吧
【在 g*******y 的大作中提到】
: 那你把题目说清楚看看有没有其他的方法，
: 什么叫做一行行排好序的字符串，到底是对字符串排序还是按时间排序？
: 一行是一个record with 2个field，一个是char array，一个是time stamp？
: sort的方法就那么些，他的方法能smart到哪儿去?
|
g*******y
发帖数: 1930 | 9 我这阵子太忙了没有时间啊
【在 H*M 的大作中提到】
: 小尾羊TX,你也申请作版主吧
|
H*M
发帖数: 1268 | 10 这周结束就不忙了把
【在 g*******y 的大作中提到】
: 我这阵子太忙了没有时间啊
|
|
|
w******1
发帖数: 520 | 11 是对合并后的文件内容排序。
比如两个输入文件都是这种结构
1997 qwqqwqw
1999 jjjjj
2008 dfdf dfdf
2009 wewe
2010 eswd
【在 g*******y 的大作中提到】
: 那你把题目说清楚看看有没有其他的方法，
: 什么叫做一行行排好序的字符串，到底是对字符串排序还是按时间排序？
: 一行是一个record with 2个field，一个是char array，一个是time stamp？
: sort的方法就那么些，他的方法能smart到哪儿去?
|
s*******n
发帖数: 452 | 12 再给个输入文件，和输出文件，到底是按1997还是qwqqwqw 排序，
还是“1997 qwqqwqw”作为一个整体排序？
【在 w******1 的大作中提到】
: 是对合并后的文件内容排序。
: 比如两个输入文件都是这种结构
: 1997 qwqqwqw
: 1999 jjjjj
: 2008 dfdf dfdf
: 2009 wewe
: 2010 eswd
|
w******1
发帖数: 520 | 13 “1997 qwqqwqw”作为一个整体排序
【在 s*******n 的大作中提到】
: 再给个输入文件，和输出文件，到底是按1997还是qwqqwqw 排序，
: 还是“1997 qwqqwqw”作为一个整体排序？
|
s*******n
发帖数: 452 | 14 最多就是用个heap maintain每个文件最小的数，基本就是这样了吧？
【在 w******1 的大作中提到】
: 我的想法是因为每个文件都是排好序的，
: 那么我是把每个文件存到ARRAY，
: 从头开始， 从每个ARRAY 的第一个开始比较。
: 被选中的最小值的行， 写入新的文件， 指针下行。
: 但是， 因为文件中存的是字符串， 而不是数据， 这个比较起来， 就很慢了。
|
f***n
发帖数: 117 | 15 是算法题还是实际工程问题？
如果是实际工程问题，还是并行做吧，读出时间，记录offset，拿时间去排序，同时拍
offset和文件#，然后并行写道大文件里去。
如果是算法问题，只有一个cpu和几G内存的话，还能如何。。无非就是每次把数据读一
部分到内存里排序然后写道文件里，然后继续读剩下的。。。
他们所谓的smart方法是啥？
【在 w******1 的大作中提到】
: 如何处理几个文件的合并排序问题
: 几个文件都很大， 每个文件都是一行行排好序的字符串序列组成的，
: 如果把这个几个文件合成一个大文件， 也必须是一行行排好序的， 怎么做比较快呢？
|
w******1
发帖数: 520 | |
w******1
发帖数: 520 | 17 我开始也许这样想的， 但是， 输入的文件如果多了的话， 如果是N 个文件。
那么，这个复杂度就上来了。
【在 s*******n 的大作中提到】
: 最多就是用个heap maintain每个文件最小的数，基本就是这样了吧？
|
c***z
发帖数: 6348 | 18 Under unix?
cat + sort
【在 w******1 的大作中提到】
: 如何处理几个文件的合并排序问题
: 几个文件都很大， 每个文件都是一行行排好序的字符串序列组成的，
: 如果把这个几个文件合成一个大文件， 也必须是一行行排好序的， 怎么做比较快呢？
|
g*******y
发帖数: 1930 | 19 输入文件多了正好是external sort的用武之地啊，总的I/O cost = 2 × log_n(N), N
是文件
个数， n是内存的大小/page大小
除了这个，如果时间的分布比较的uniform，可以按时间划分bucket，然后对每个
bucket进行sort
【在 w******1 的大作中提到】
: 我开始也许这样想的， 但是， 输入的文件如果多了的话， 如果是N 个文件。
: 那么，这个复杂度就上来了。
|
w******1
发帖数: 520 | 20 不准用缺省的unix SORT 方法。
我觉得external sort已经够好了。 不知道他们为什么不满意。 |
H*M
发帖数: 1268 | 21 也不是不满意，就是想push u to the limit and watch you
-A3
【在 w******1 的大作中提到】
: 不准用缺省的unix SORT 方法。
: 我觉得external sort已经够好了。 不知道他们为什么不满意。
|
