如何有效地对分区数组进行排序？

Question

我有K个文件.我叫他们X1,X2,......,XK.
这些文件中的每一个都是N×1的双精度数组.
这意味着我实际上有一个NK x 1阵列,以K阵列分区.让我们把这个大阵X.

我需要排序X,我无法将所有数据加载到内存中.执行此排序的有效算法是什么,并将结果保存在单独的文件中？

我知道(当然不确定有效)如何做,如果我只想排序H元素:

1. 排序X1并将其保存为sX1
2. 在Matlab中A = sX1(1:H,1) //
3. 排序X2和A.
4. 对其他文件重复步骤1,2和3

但是,由于记忆问题,H不能很大.

更新有限内存问题
的排序与此问题不同,尽管它有所帮助.如果我想使用那些问题答案或MikeB的答案,那么这也应该回答:我应该将K文件合并到一个文件中,然后使用外部排序算法.如果是,怎么样？

谢谢.

Answer 1

你正在尝试的是一种外部排序.每个分区都会自行排序.然后,您必须合并所有分区以构建最终的排序列表.如果您只是寻找前几个项目,您可以提前退出合并.

似乎有一些现有解决方案用于外部合并的matlab解决方案.以下是mathworks文件交换站点上的链接:http://www.mathworks.com/matlabcentral/fileexchange/29306-external-merge-sort/content/ext_merge/merge.m

更新:我链接的代码显示了它在matlab中的完成情况.具体来说,这里的代码:http://www.mathworks.com/matlabcentral/fileexchange/29306-external-merge-sort/content/ext_merge/extmerge.m获取需要合并的文件列表,并最终合并它们到一个文件.

在你原来的问题陈述中,你说你有来自X1到XK的K个文件.外部排序首先对这些文件进行排序,然后将它们合并到一个文件中.一个简单的实现会有这样的伪代码:

// external merge-sort algorithm
For each file F in (X1 ... XK)
    Read file F into memory array R
    Sort R
    Overwrite file F with sorted data from R
    Clear array R in memory
For N = K-1 down to 1
    in-order merge file XN+1 and XN into file X'
    erase file XN+1 and XN
    rename file X' as XN

您应该看到第一阶段是排序.我们将每个文件读入内存,对其进行排序,然后将其写回.这是I/O,但效率很高; 希望我们尽可能多地使用内存,以便尽可能地在内存中进行排序.在第一个循环结束时,我们有K个文件,每个文件都在自己的值域中排序.

鉴于K个已排序的文件,我们的下一步是合并它们.合并两个文件不使用任何内存,但会执行大量I/O. 合并两个文件看起来像这样,给定两个名为L和R的文件,我们可以将它们合并到O中:

// merge two files algorithm
Get value LV from L
Get value RV from R
While L is not EOF AND R is not EOF
    if ( LV <= RV )
        write LV into O
        get value LV from L
    else 
        write RV into O
        get value RV from R
While L is not EOF
    get LV from L
    write LV into O
While R is not EOF
    get RV from R
    write RV into O

合并排序中的第二个循环将两个文件N + 1和N合并为一个文件N.它循环遍历每个文件并合并它们.这会读取并重写大量数据,通过在循环中处理多个文件,您可以获得更高效的效果.但是我写的时候它工作得很好.