问题标签 [external-sorting]

我需要从 N 个小排序文件中创建一个巨大的排序文件。

我已经做了一个研究，发现外部排序算法是合适的。

但是我有一个内存限制（将字符串限制在内存中<N），所以我无法加载每个小文件的所有第一行，对它们进行排序，然后写入输出文件等。

例如，此链接https://www.algosome.com/articles/how-to-sort-large-file.html不适合，因为在合并阶段他将所有第一行都存储在内存中。

你能帮我找出适合我的案例的最佳分步算法或实现吗？

谢谢你。

我想知道进行并行外部排序时的复杂性是什么。

假设我有大数组 N 和有限的内存。Fe 10 亿个条目要排序，条目内存中只有 1k 个。

对于这种情况，我使用并行线程将大数组拆分为块大小为 B 的 K 个排序文件，并保存在磁盘中。

从所有文件中读取之后，使用 priprityQueue 和线程合并回新数组。

我需要用大 O 表示法计算复杂度。

如果我使用多进程让我们说 N 个处理器，复杂性会发生什么？

谢谢

我正在尝试了解快速排序的外部版本（当数据无法放入主内存时）。我在外部快速排序过程的Wiki上找到了以下链接和类似的解释：

定义：将 M/2 的第一个和最后一个元素读入缓冲区（缓冲区的作用类似于快速排序中的枢轴），并对它们进行排序。从头或尾读取下一个元素以平衡书写。如果下一个元素小于缓冲区的最小值，则将其写入开头的可用空间。如果大于最大，就写到最后。否则写入缓冲区的最大或最小，并将下一个元素放入缓冲区。保持写入最大的下键和最小的上键，以避免使用按顺序排列的中间元素。完成后，写入缓冲区。递归地对较小的分区进行排序，并循环对剩余的分区进行排序。

我有理解它的问题：

• 是M指主存的大小吗？我还有N-M一些驱动器上的剩余元素？

• The buffer acts like the pivot in quicksort- 这是否意味着我需要N-M将驱动器中的剩余元素分成两部分a，并且b其中的元素a低于缓冲区中的所有元素，而元素中的元素b大于或等于缓冲区中的最大元素？

• Read the next element from the beginning or end to balance writing.平衡写作是什么意思？应该从缓冲区（内存）还是从驱动器中读取下一个元素？

• Otherwise write the greatest or least of the buffer, and put the next element in the buffer- 如果我将下一个元素放入缓冲区（已经排序），我需要再次对缓冲区进行排序吗？

一些它如何工作的例子或更好的解释将非常有用。

在此处的官方 Python 文档中，提到：

堆在大磁盘排序中也非常有用。你可能都知道大排序意味着产生“运行”（这是预排序的序列，其大小通常与 CPU 内存的数量有关），然后是这些运行的合并通道，这种合并通常非常巧妙有组织的。
初始排序产生尽可能长的运行是非常重要的。锦标赛是实现这一目标的好方法。如果使用所有可用于举办锦标赛的内存来替换和过滤恰好适合当前运行的项目，那么您将生成两倍于随机输入内存大小的运行，并且对于模糊排序的输入要好得多。

此外，如果您在磁盘上输出第 0 个项目并获得一个可能不适合当前锦标赛的输入（因为该值“胜过”最后一个输出值），则它无法放入堆中，因此堆减少。释放的内存可以立即巧妙地重用于逐步构建第二个堆，该堆的增长速度与第一个堆融化的速度完全相同。
当第一个堆完全消失时，您切换堆并开始新的运行。聪明又有效！

我知道一种称为外部排序的算法，其中我们：

1. 将输入分解成更小的块。
2. 单独对所有块进行排序，并将它们一一写回磁盘。
3. 创建一个堆并在所有已排序的块之间进行 k 路合并。

我完全理解了维基百科上描述的外部排序，但是当他们说时我无法理解作者：

如果使用所有可用于举办锦标赛的内存，​​替换和过滤恰好适合当前运行的项目，您将生成两倍于随机输入内存大小的运行，并且对于模糊排序的输入更好。

和：

此外，如果您在磁盘上输出第 0 个项目并获得一个可能不适合当前锦标赛的输入（因为该值“胜过”最后一个输出值），则它无法放入堆中，因此堆减少。

这个堆在融化什么？

我正在从作者 Elmasri 和 Navathe 第 5 版的《数据库系统基础知识》一书中研究数据库，他们几乎在第 15 章开头简要解释了使用合并排序的外部排序。他们将算法分为两个阶段：

1）排序：他们使用下一个符号：

• b = 我们要排序的数据文件的块数。
• nb = 内存中可用于排序的缓冲区（块）数。
• nr = 份数。

在这个阶段，我们将尽可能多的数据文件块放入内存，我们使用任何内部排序算法对它们进行排序，并将它们写为临时排序的子文件。我们对文件的其余块重复此操作，因此我们将获得更多排序的子文件。这些子文件被他们称为“部分”，它们的数量是：

nr = ⌈ b / nb ⌉。

符号 ⌈ ⌉ 表示上限函数。此阶段的 I/O 成本为2b，因为我们需要读取每个块一次（b 次访问）。然后，为了保存所有部分，我们还需要进行 b 访问。

2）合并：他们说了类似的话（我用我的解释重写了它以使其更清晰）：

生成的部分（有序子文件）在一个或多个通道中混合。对于每一遍，在内存中保留一个输出块以放置混合结果，其余用作输入块，最大可达 nb - 1，并且每次放置一个块有序的部分，目的是混合它们。当输入块少于部分时，需要不止一次通过。此外，由于每个部分可以有多个块，因此每个 pass 被细分为迭代，在每个迭代中放置每个部分的一个块。

• dm = 混合程度，即每次可以混合的份数。

数字 dm 必须等于 (nb - 1) 和 nr 之间的最小值。如果我们将对数的底放在 ( ) 之间，并将其参数放在〖〗之间，则通过次数为：

⌈ log(dm)〖nr〗⌉。

我感到困惑的是，他们说这个阶段的成本是

2b * ⌈ log(dm)〖nr〗⌉,

所以他们基本上是在暗示，在每次传递中，我们只需要读取每个块一次并写入一次，但我不确定这是否正确。我怀疑可能需要更多访问权限。

因此，算法的总成本为 2b + 2b * ⌈log(dm)〖nr〗⌉

= 2b (1 + ⌈log(dm)〖nr〗⌉)

其实他们不是这么说的，而是：“一般情况下，对数取dm为底，表示访问块数的表达式如下：”

(2*b) + (2* (b* (log(dm)〖nr〗))),

这基本上是一样的。

例如，假设我们有一个包含 10 个块的文件，每个块有 3 条记录。内存（缓冲池）中的可用空间大小为 4 个块。让我们用 || 分隔文件的块

29,11,27 || 22,1,20 || 7,30,26 || 9,8,21 || 13,24,15 || 23,4,28 || 17,12,10|| 5,3,6 || 16,19,2 || 25,14,18

导致排序阶段的部分“nr”的数量是⌈10/4⌉ = 3。

p1 = 1,7,8 || 9,11,20 || 21,22,26 || 27,29,30

p2 = 3,4,5 || 6,10,12 || 13,15,17 || 23,24,28

p3 = 2,14,16 || 18,19,25

在meging阶段，dm = minimum{nb-1, nr} = minimum{4-1,3} = 3。那么，通过的次数是log(3)〖3〗=1。根据公式，我们在这个阶段应该进行 20 个 I/O。

迭代 1：我们将这些块放入内存中：

1,7,8 || 3,4,5 || 2,14,16

它们变成了这个（一次一个块，保存在磁盘中）：

1,2,3 || 4,5,7 || 8,14,16

6 访问磁盘。

迭代 2：

9,11,20 || 6,10,12 || 18,19,25

他们变成了这样：

6,9,10 || 11,12,18 || 19,20,25

6次访问磁盘（已经累积了12次）。

我做错了什么，我该如何继续？

我们有 200Gb 的文件，其中填充了除以“\n”的文本行。我们的服务器有板载 Linux、gcc、8GB RAM 和无限的硬盘空间。从我们的角度来看，要求是在 C++ 中实现对这个文件的行进行字典排序的最有效方法。

我已经正确地为输入文件（最大 2GB）按字典顺序对文本行进行了外部排序。但是当我使用大于 2GB 的文件进行测试时，输出不正确。最大文件大小需要测试大于 200GB。

下面是我的代码，它适用于小于 2GB 的文件大小。程序有 3 个参数作为命令行参数：输入文件名、输出文件名和内存限制（以字节为单位）（我们将使用不同的内存限制进行测试，而不仅仅是 8GB） 程序应该能够在简单的边界情况下正常工作，例如小文件、空文件、大于 200GB 的文件。它应该适用于非 ascii 符号，但我们可以假设文件中不存在零字节。我们还可以假设内存限制远大于最长行的大小。

这是代码。请帮我指出文件大小大于 2GB 时无法产生正确结果的原因。如果您能给我下面的代码的修改版本以使其适用于所有情况，我将不胜感激。

//人物结构

// Person的数组类型

Person我在我拥有的人里面有一个对象，id并且nPersonnPerson 是Person. 我想按 id 对数组进行排序，该排序也可以在nPerson数组内工作。

我需要在 PC 上以最短时间（数十 GB）对文件中的行进行排序。我应该使用 N 路归并排序，对吗？如何选择数字 N（一次要合并的文件数）？我应该在读取或写入和调整 N 时测量延迟吗？或者从系统中获取磁盘信息？如果我有 SSD，我可以一次合并所有排序的部分吗（程序需要以某种方式确定它是否是 SSD）？还可以进行哪些其他优化？

我目前正在实现一个使用“外部排序”方法的功能，因为我必须在 RAM 较低的设备上对一个大文件（+200K 行）进行排序，现在只是想让它在 Windows pc 上运行。我正在研究将文件拆分为微小排序文件的功能。

我面临的问题是，在函数创建的微小排序文件中，某些行上的数据被截断。

我很确定我在某个地方犯了一个错误，但还没有找到它。你能帮我发现问题吗？

这是 fp 文件的示例（每行以 结尾\r\n）：

我编写了一个方法private void merge2way(String f1, String f2, String f3)，它读取 2 个文件名并返回一个合并文件。我想使用此方法编写一个私有 void 合并（ int n ）方法，该方法采用先前排序的文件数并应用该 merge2way。我已经为数组递归地完成了它，但我在这里迷路了，因为我还认为我必须考虑文件数是偶数还是奇数。

这是我的 merge2way 方法。如果有人可以提供帮助，我将不胜感激！

} // 结束merge2way