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

Question

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

algorithmmatlabsorting

5

我有K个文件。我把它们称为X1，X2，...，XK。
这些文件中的每一个都是一个N x 1双精度数组。
这意味着我实际上有一个NK x 1的数组，分成了K个数组。我们称这个大数组为X。

我需要对X进行排序，但我无法将所有数据加载到内存中。有什么高效的算法可以执行此排序并将结果保存在单独的文件中吗？

当然我知道如何做到排序H个元素，但是H不能太大，因为会出现内存问题：

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

但是由于内存限制，H不能太大。

更新:
有限内存下的排序问题与此问题不同，尽管它有所帮助。如果我想使用那个问题的答案或MikeB的答案，那么这个问题也应该得到回答：我应该将K个文件合并为一个文件，然后使用外部排序算法进行排序。如果是，如何操作？

谢谢。

- Ramin

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- MikeB · Accepted Answer

你正在尝试进行外部排序。每个分区都被单独排序。然后，您必须合并所有分区以构建最终排序列表。如果您只想查找前几个项目，则可以提前退出合并。

似乎有一些现有的解决方案，用于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接受需要合并的文件列表，并最终将它们合并为一个文件。

在你的原始问题陈述中，你说你有K个文件，从X1到XK。外部排序首先对这些文件进行排序，然后将它们合并成一个文件。一个简单的实现将具有如下伪代码：

// 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。它遍历每个文件并将它们合并。这会读取和重写大量数据，通过在循环中处理多个文件，您可以变得更加高效。但是按照我编写的方式也可以正常工作。