问题标签 [external-sorting]

如何对大型数据集实际使用归并排序？

假设我有几个带有以下数据的排序文件：

1.txt

2.txt

3.txt

假设我们不能同时将所有文件的内容保存在内存中（假设我们只能保存每个文件中的两个数字）。

我听说在这种情况下我可以使用某种 R-way 合并排序，但我不明白我该怎么做。

如您所见，第一次迭代将为我们提供以下排序序列：

，所以我们将它刷新到输出文件。但是，我们将在下一次迭代中1再次（从文件中）得到，所以整个结果序列是错误的！3.txt

我有以下情况：

1. 数据 = 大约 4 亿个 (string1, string2, score) 元组

2. 数据大小 ~ 20gb，不适合内存。

3. 数据以 csv 格式存储在文件中，不按任何字段排序。

4. 我需要有效地检索具有特定字符串的所有元组，例如所有元组 st string1 = 'google'。

我如何设计一个系统，以便我可以有效地做到这一点？

我已经尝试过使用 B-tree 索引和 GIN 索引的 postgresql，但是每个查询的速度不够快（> 20-30 秒）。

理想情况下，我需要一个解决方案，它按 string1 对元组进行排序，以排序方式存储它们，然后运行二进制搜索，然后进行顺序扫描以进行检索。但是，我不知道哪个数据库或系统实现了这样的功能。

更新：这是 postgres 的详细信息：

我使用 COPY 命令将数据批量加载到 postgres 中。然后我在 string1 上创建了两个索引，一个 b-tree 和一个 GIN。但是，postgres 没有使用它们中的任何一个。

创建表：

查询计划：

我正在练习，我遇到了一个关于从一个太大而无法放入内存的文件中排序数字的问题。我不知道如何做到这一点，所以我想我会试一试。我最终找到了外部排序，我基本上只是试图采用这个概念并编写一个解决这个问题的代码。我正在练习的文本文件没有那么大，无法放入内存。我只是想学习如何完成这样的事情。到目前为止，我正在从文件中读取 3 个块，每块 500 行，对块进行排序，然后将结果块写入它们自己的文件。这是有效的......虽然我不确定我的实现是如何实现外部排序过程：

我的问题是我应该如何将文件分成块？我碰巧确切地知道我的文件有多少行文本，因为我创建了它，所以编写这段代码很容易......但问题实际上告诉你文件的大小；就像在内存中一样，不是文件有多少行文本。我不确定如何将数据分解为“内存块”（以及如何调整它们的大小）而不是文本行。另外，如果我的代码有任何奇怪、错误或不良做法，请告诉我，因为我真的不知道自己在做什么；我只是在努力学习。至于将排序的文件重新合并在一起，我也不知道该怎么做，但我有一个想法。在我寻求这方面的帮助之前，我想尝试一下。谢谢！

我有来自我们设备上运行的 N 个不同服务的 N 个不同日志文件。我想将 N 个文件合并到一个保持时间顺序的文件中。文件大小可以从几 KB 到 GB 不等。

N个日志文件格式相同，如下：

由于我已经有 N 个不同的文件，到目前为止我所做的是应用一个外部排序算法，为每个文件读取一行：

它完全按照它应该做的，但它很慢。要合并 82 个大小从 1 KB 到 250 MB 的文件，并创建一个超过 6000000 行的最终文件，需要 70 分钟。

如何加快算法速度？任何帮助是极大的赞赏！

更新

我也用堆实现了这个版本：

数据.h：

数据.cpp：

主要.cpp：

完成所有这些工作后，我意识到昨天我在 Debug 中运行了该程序。在 Release 中启动这两个实现，我得到以下结果：

• 矢量实现：约 25 秒
• 堆实现：约 27 秒

因此，或者我的堆结构实现没有优化，或者两个实现在运行时间上相等。

我还能做些什么来加快执行速度吗？

根据第二个字段对文件的内容进行排序，例如

输入文件：

输出文件：

我们需要使用外部排序。
输入文件的大小可以为 4GB。内存为 1GB。

我使用了它，但它不起作用，因为它将所有内容都视为int. 我也怀疑与外部排序的每一轮中的缓冲区大小有关。如何决定呢？

这仅使用整数对文件进行排序。

我可以创建按第二个字段排序的临时文件，但是如何基于此合并它们？

考虑到机器只有 96 字节的可用内存，我需要模拟一个外部排序算法。我正在使用如下所示的 32 字节结构：

我已经将一个大的 tobesorted.txt 文件拆分为 3 个 Register32 二进制文件。例如：

分为8个文件，内部排序，从file0.bin到file7.bin，包含31个字节的垃圾，1个字节是用于始终对寄存器进行排序的键。

我的任务是在任何给定时间将这些文件中的 2、3 或 4 个“合并”到退出文件中，并继续合并它们，直到我把初始单词全部整理出来。示例：将 file0 与 file1 合并将在退出文件中输出 CEINRT。当然，合并功能应该概括为一次读取每个排序键并合并到退出文件中，而不管文件输入大小如何。我的 Merge 函数接收一个文件数组，该数组可以包含 2、3 或 4 个文件（函数未知）、所提及数组的最低索引、较高索引和退出文件。它看起来像这样：

TypeFile 只是一个typedef FILE* TypeFile;.

我知道如果我需要模拟内存限制，我应该一次比较每个寄存器的键，然后将最低值写入 exitfile，但我无法让自己想办法做到这一点。循环约束和输入长度为 6 个或更多关键字符的情况正在融化我的大脑。最后，我只想让最初的 tobesorted.txt 完全排序，一次将 2、3 或 4 个文件合并成一个更大的文件，然后继续下一个。这已经实现了，我只需要实现 Merge 功能。对不起，如果我让自己难以理解，英语不是我的母语。感谢你们能给予的任何帮助。

我知道有人问过类似的问题，但它们没有解决更详细的问题，也没有在 PHP 中......

我有一个带有逗号分隔的数字列表的 .txt 文件。对文件进行排序、拆分并保存到多个较小的文件中非常简单。将这些文件的小块重新组合在一起并对其进行排序的内存有效方法是什么？

我目前所做的所有尝试都导致了巨大的内存使用。

更具体的说法可能是：

1. 如何从文件中流式传输小块数据
2. 跟踪我已经处理了哪些数据
3. 创建一个缓冲区，当缓冲区已满时将其写出
4. 从 1 开始并重复，直到所有数据都已排序

我正在编写一个外部排序来对磁盘上的一个大 2 gig 文件进行排序

我首先将文件分成适合内存的块，并分别对每个块进行排序，然后将它们重写回磁盘。但是，在此过程中，我在函数 geModel 的 String.Split 方法中遇到 GC 内存开销异常。下面是我的代码。

它通过一次并从文件中排序约 250 MB 的数据。但是，在第二遍时，它会在 String.split 函数上引发 GC 内存开销异常。我不想使用外部库，我想自己学习。排序和拆分工作，但我不明白为什么 GC 在 string.split 函数上抛出内存开销异常。

多线程对我来说是新的，所以对错误感到抱歉。

我已经编写了以下程序，它将文件与多线程合并，但我无法弄清楚如何管理最后一个文件以及在一次迭代之后如何合并新创建的文件。

我正在尝试将排序文件与多线程合并。假设我有 50 个文件，我想将所有这些单独的文件合并到一个最终排序的文件中，但我想通过多线程加速和利用每个内核，但我无法做到。而且文件很大，所以不能放在堆/内存中，所以我必须读取每个文件并继续写入。

有关于合并排序文件或合并 K 排序文件的不错的文献。他们都基于这样一个理论，即每个文件的第一个元素都放在一个堆中，然后直到堆为空轮询该元素，然后从该元素所在的文件中获取另一个元素。只要可以将每个文件的一条记录放在堆中，这就会起作用。

现在让我们说我有 N 个已排序的文件，但我只能将 K 条记录放入堆中并且 K < N 并让我们说 N = Kc 其中“c”是乘数，意味着 N 太大以至于它是 c 的某个倍数. 显然，它需要一遍又一遍地进行 K 路合并，直到我们只剩下 K 个文件，然后我们将它们作为最后一次合并到最终排序中。我如何实现这一点，这将是什么复杂性？