5

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

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

我知道（当然不确定是否有效）如果我只想对 H 元素进行排序，该怎么做：

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

但是H不能很大，同样是因为内存问题。

Update
The Sort with the limited memory question 与此问题不同，尽管它有所帮助。如果我想使用那个问题的答案或 MikeB 的答案，那么也应该回答这个问题：我是否应该将 K 个文件合并到一个文件中，然后使用外部排序算法。如果是，如何？

谢谢。

4

1 回答 1

7

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

似乎有一些用于外部合并的现有解决方案 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 中。它遍历每个文件并合并它们。这会读取和重写大量数据，并且您可以通过在循环中处理多个文件来获得更高的效率。但它工作正常，因为我已经写了它。

于 2012-12-18T16:10:48.197 回答