2

我有一个包含大量数据的文件，我想对它进行排序，在任何给定时间只保存内存中的一小部分数据。

我注意到合并排序在外部排序中很受欢迎，但我想知道它是否可以用堆（最小或最大）来完成。基本上我的目标是在 100 个项目列表中获得前 10 个项目（使用任意数字），同时在内存中永远不会超过 10 个项目。

我主要了解堆，并且了解堆化数据会将其按适当的顺序排列，从中我可以将其最后一部分作为我的解决方案，但我不知道如何在没有 I/O 的情况下处理对于每一个该死的项目。

想法？

谢谢！:D

4

4 回答 4

5

使用堆排序需要在文件中进行大量查找操作，以便最初创建堆以及删除顶部元素。因此，这不是一个好主意。

但是，您可以使用合并排序的变体，其中每个堆元素都是一个排序列表。列表的大小取决于您要在内存中保留多少。您可以通过加载数据块、对它们进行排序然后将它们写入临时文件来从输入文件创建这些列表。然后，您将每个文件视为一个列表，读取第一个元素并从中创建一个堆。删除顶部元素时，将其从列表中删除并在必要时恢复堆条件。

尽管有一个方面使得这些关于排序的事实无关紧要：您说您想确定前 10 个元素。为此，您确实可以使用内存堆。只需从文件中取出一个元素，将其推送到堆上，如果堆的大小超过 10，则删除最低的元素。为了提高效率，只有在大小低于 10 或高于最低元素时才将其推送到堆上，然后替换并重新堆化。将前十名放在堆中允许您只扫描一次文件，其他所有内容都将在内存中完成。使用二叉树而不是堆也可以，并且可能同样快，对于像 10 这样的小数字，您甚至可以使用数组并对元素进行冒泡排序。

注意：我假设 10 和 100 只是示例。如果您的数字真的那么低，那么任何关于效率的讨论都可能没有实际意义，除非您每秒执行几次此操作。

于 2013-05-16T20:50:56.247 回答
2

是的，您可以使用堆来查找k大文件中的顶部项目，仅在内存中保存堆 + 一个 I/O 缓冲区。

下面将k通过使用长度为 的最大堆来获得最小项k。您可以按顺序读取文件，为每个项目执行 I/O，但将块中的数据加载到 length 的辅助缓冲区通常会快得多b。该方法在O(n*log(k))使用O(k + b)空间的操作中运行。

while (file not empty)

    read block from file

    for (i = all items in block)
        if (heap.count() < k)
            heap.push(item[i])
        else
        if (item[i] < heap.root())
            heap.pop_root()
            heap.push(item[i])
        endif
    endfor

endwhile
于 2013-05-16T20:52:54.327 回答
0

堆需要大量的非顺序访问。Mergesort 非常适合外部排序，因为它执行了大量的顺序访问。

在旋转的磁盘上，顺序访问要快得多，因为磁头不需要移动。固态磁盘上的顺序访问也可能比堆排序的访问快得多，因为它们在块中进行访问，这些块可能比文件中的单个内容大得多。

于 2013-05-16T20:18:35.000 回答
-1

通过使用合并排序并通过引用传递两个值，您只需将两个比较值保存在缓冲区中，然后在整个数组中移动，直到它被排序到位。

于 2013-05-16T20:21:25.120 回答