logo标签列表

在内存限制下如何对大量数据的文件进行排序

javafilesorting
50

要点：

  • 我们每天并发处理数千个平面文件。
  • 内存限制是一个主要问题。
  • 我们为每个文件处理使用线程。
  • 我们不按列排序。 文件中的每一行（记录）被视为一列。

无法执行的事情：

  • 我们不能使用Unix / Linux的排序命令。
  • 无论它们有多轻，我们都不能使用任何数据库系统。

现在，我们不能只是将所有内容加载到集合中并使用排序机制。 它将耗尽所有内存，并且程序将获得堆错误。

在这种情况下，您将如何对文件中的记录/行进行排序？

4
有没有使用数据库系统的原因？数据库系统专为此类场景设计，因为它们在处理大量数据时非常高效。 - keyboardP
是的，该系统已经运行了10年，他们不愿意更改。 - Erika Gomez
11
引入一个轻量级的非安装式数据库与引入一个自定义编写的程序有何不同？尽管两者从技术上都是“更改系统”，但前者具备一定的测试性能力，后者则不然。 - Joachim Sauer
8
试着向一个对编程一窍不通的高管解释这个。如果你能说服他，那么你就是我的导师！请注意，在翻译过程中，请勿使用任何粗俗或冒犯性语言。 - Erika Gomez
6
请将此帖子的链接发送给他:D - keyboardP
4
如果它是嵌入式数据库，执行者不需要知道它的存在。 - Valentin Rocher
15个回答
57

看起来你要找的是外部排序。

基本上，你需要先对小块数据进行排序，将其写回磁盘，然后迭代这些块以对所有数据进行排序。

4
据我的研究，我了解到如果您有一个包含1000条记录的文件，并且每次读取100条记录，将这100条记录排序并将排序后的版本放入一个临时文件中，这将创建10个临时排序文件。然后依次读取两个文件，并创建另一个已排序（现在更大）的文件，然后删除刚刚读取的另外两个文件。持续进行此过程，直到只剩一个文件为止。真的吗？现在假设您有一个包含1000万条记录的文件，并且每次读取5000条记录，那么您创建了多少个临时文件？获取最终版本需要多长时间？如果您有一个包含1000万条记录的文件，并且每次读取5000条记录，则需要创建2000个临时文件。获取最终版本所需的时间取决于您的计算机性能和文件的大小，无法确定具体时间。 - Erika Gomez
外部排序总是比内存排序慢，但您不再受RAM限制。 如果速度对您很重要并且有几台机器在手边，请看一下Hadoop（在其他回复中提到）。它执行外部排序，其中所有单独的排序操作可以在多台机器上并行发生。 - phisch
Erika: 当你合并排序后的较小文件时，可以打开两个以上的文件，只是使用两个临时文件来描述算法稍微更为直观一些。但是，如果需要对一个大于可用内存的文件进行排序，你最终仍然需要以这种方式操作，合并操作相对较快，因为它只需要保持N个文件指针打开，并找到N个“下一个记录”中最低的记录以了解下一个要发出的内容。我想调整的关键点是选择每个临时文件中保存多少条记录。 - Vatine
15

如其他人所述，您可以分步处理。

我想用自己的话解释一下（在第3点上有所不同）：

  1. 按顺序读取文件，在内存中每次处理N条记录（N是任意的，取决于您的内存限制和要创建的临时文件数T）。

  2. 将N条记录在内存中排序，并将它们写入一个临时文件。重复使用T直到完成。

  3. 同时打开所有T个临时文件，但仅从每个文件中读取一条记录。（当然，使用缓冲区）。对于这些T个记录中的每一个，找到最小值，将其写入最终文件，并只在该文件中前进。

优点：

  • 内存消耗尽可能低。
  • 与一切均在内存策略相比，磁盘访问量仅增加了一倍。还不错! :-)

数字示例：

  1. 原始文件包含100万条记录。
  2. 选择使用100个临时文件，因此每次读取和排序10,000条记录，并将它们放入自己的临时文件中。
  3. 同时打开100个临时文件，每次在内存中读取第一条记录。
  4. 比较第一条记录，写入更小的记录并前进这个临时文件。
  5. 重复步骤5一百万次。

已编辑

您提到了一个多线程应用程序，所以我想......

正如我们从这些讨论中所看到的，在这种情况下使用较少的内存会导致性能降低，这个因素是非常严重的。所以我还可以建议只使用一个线程来处理每次只进行一次排序，而不是作为多线程应用程序。

如果您使用十个线程，每个线程都有十分之一可用的内存，则性能将很差，远远低于初始时间的十分之一。如果您只使用一个线程，并将其他9个任务排队并依次处理它们，则总体性能将更好，您会更快地完成十个任务。

在阅读这篇回答后： Sort a file with huge volume of data given memory constraint 我建议您考虑使用分布式排序。在您的环境中，这可能是一个巨大的收益。

与我的建议相比，它的改进之处在于您不需要同时打开所有临时文件，只需打开其中一个即可。这能够救您一命! :-)

@Erika 嗯，这只是一个例子，让我们理解一下。需要在临时文件大小和数量之间做出选择。 - KLE
14

尽管您有限制，我仍然会使用嵌入式数据库SQLITE3。像您一样，我每周需要处理1000-1500万行的平面文件，使用SQLite非常快速地导入和生成排序数据，而且您只需要一个免费的可执行文件（sqlite3.exe）。例如：一旦您下载了.exe文件，在命令提示符中可以执行以下操作：

C:> sqlite3.exe dbLines.db
sqlite> create table tabLines(line varchar(5000));
sqlite> create index idx1 on tabLines(line);
sqlite> .separator '\r\n'
sqlite> .import 'FileToImport' TabLines

那么：

sqlite> select * from tabLines order by line;

or save to a file:
sqlite> .output out.txt
sqlite> select * from tabLines order by line;
sqlite> .output stdout
3
先插入数据再创建索引可能更快。 - Mark
13

您可以将文件分成较小的部分进行读取，对这些部分进行排序并将它们写入临时文件中。然后您再次顺序读取其中的两个部分并将它们合并成一个更大的临时文件，以此类推。如果只剩下一个，那么您就有了已排序的文件。基本上，这就是在外部文件上执行Megresort算法。它可很好地扩展到任意大的文件，但会导致一些额外的文件I/O。

编辑：如果您对文件行的可能变化有一些了解，可以使用更高效的算法（分布排序）。简单来说，您只需读取原始文件一次，并将每行写入一个只包含具有相同首字母（或某个特定范围的首字母）的行的临时文件中。然后，您按升序迭代所有（现在较小的）临时文件，在内存中对它们进行排序，并直接将它们附加到输出文件中。如果某个临时文件过大而无法在内存中排序，则可以基于行中的第二个字符重复相同的过程，以此类推。因此，如果您的第一个分区足够好以产生足够小的文件，则不管文件大小如何，您仅需要100％的I / O开销，但在最坏的情况下，它可能会比性能稳定的合并排序更多。

从我的研究中，我了解到如果你有一个包含1000条记录的文件，并且每次读取100条记录，那么将这100条记录排序并将排序后的版本放入一个临时文件中，这将创建10个临时排序文件。然后按顺序读取两个文件，并创建另一个已排序（现在更大）的文件，并删除刚刚读取的另外两个文件。继续进行，直到只剩下一个文件。真的吗？现在，假设你有一个包含1000万条记录的文件，并且每次读取5000条记录，你会创建多少个临时文件，以及获取最终版本需要多长时间？ - Erika Gomez
你可以通过取两个最小的临时文件并将它们合并成一个较大的临时文件来进行合并。这会导致比在内存中对所有内容进行排序多log2(n)倍的文件I/O操作（n是您开始使用的临时文件数）。因此，对于最初的8个部分，这将是300%的I/O开销，而对于128个部分，它将是700%。 - x4u
8
我会启动一个EC2集群并运行Hadoop的 MergeSort。 编辑: 不确定您需要多少细节或关于什么。 EC2是亚马逊的弹性计算云 - 它可以让您以低成本按小时租用虚拟服务器。 这是他们的网站。
Hadoop是一个开源的MapReduce框架，旨在用于大型数据集的并行处理。 当作业可以分成可以单独处理并然后合并在一起的子集时，通常通过按键进行排序（即分治策略），它是MapReduce的良好候选对象。 这是它的网站。
如其他帖子所述，外部排序也是一个很好的策略。 我认为我决定两者之间的方式取决于数据的大小和速度要求。 单台机器可能仅限于一次处理一个文件（因为您将使用可用内存）。 因此，只有在需要比这更快地处理文件时才查看类似EC2的东西。
详细说明一下？谢谢回复。 - Erika Gomez
3
您可以采用以下分治策略：
创建一个函数 H()，能够为输入文件中的每个记录分配一个数字。对于将在记录 r1 后进行排序的记录 r2，它必须返回比 r1 更大的数字。使用此函数将所有记录分成适合内存的单独文件，以便您可以对其进行排序。完成后，只需连接排序后的文件即可获得一个大的已排序文件。
假设您有这样一个输入文件，其中每行表示一个记录：
Alan Smith
Jon Doe
Bill Murray
Johnny Cash

让我们构建H()函数，使其使用记录中的第一个字母，这样您可能会得到多达26个文件，但在此示例中，您只会得到3个：

<file1>
Alan Smith

<file2>
Bill Murray

<file10>
Jon Doe
Johnny Cash

现在你可以对每个单独的文件进行排序。这将交换文件 <file10> 中的 "Jon Doe" 和 "Johnny Cash"。现在，如果你只是将这 3 个文件连接起来，你就会得到一个已排序的版本。
请注意，你先分割再征服（排序）。但是，你要确保分割的方式使得需要排序的结果不重叠，这将使合并结果更加简单。
实现分割函数 H() 的方法非常依赖于你输入数据的性质。一旦你搞清楚了这一点，其他部分应该很容易。
1
我知道这是一个旧答案，但是连接三个已排序的文件并不总是会导致排序版本。请读者不要认为这是一个有效的答案。 - Adel Ben Hamadi
2

如果您的限制只是不使用外部数据库系统，您可以尝试使用嵌入式数据库（例如Apache Derby）。这样，您就可以获得所有数据库的优点，而不需要任何外部基础设施依赖。

1
任何不会对虚拟机堆空间造成压力的解决方案都必须基于某种中间文件存储的概念。因此，你可能需要开始实现自己的数据库。因此，你可以使用一个已知可行的现有数据库。 - VoidPointer
1

这里有一种方法可以在不过度使用Java内部排序和不使用数据库的情况下完成。 假设：您有1TB的空间，并且文件包含或以唯一数字开头，但未排序

将文件分割N次。

逐个读取这N个文件，并为每个行/数字创建一个文件。

将该文件命名为相应的数字。在命名时保持计数器已更新以存储最小值。

现在您已经可以将文件的根文件夹标记为按名称排序，或者暂停程序以给您时间在操作系统上发出按名称排序的命令。您也可以通过编程方式执行此操作。

现在，您拥有了通过名称排序的文件夹，使用计数器开始逐个处理每个文件，将数字放入输出文件中，并关闭它。

完成后，您将获得一个带有排序数字的大型文件。

0

我知道你提到了不使用数据库，即使是轻量级的...所以，也许这不是一个选项。但是，内存中的hsqldb怎么样...提交它，通过查询进行排序，清除它。只是一个想法。

我编写的程序被部署在生产服务器上。该服务器由其他国家的某个团队处理。我没有直接访问该服务器的权限！ - Erika Gomez
你不需要访问服务器...尝试使用嵌入式选项。我在将数据从一个数据库迁移到另一个数据库时，使用了嵌入式hsqldb来映射数据库ID，但无法保持原始ID。它的表现非常好...性能出奇的好。 - PaulP1975
但是如果您仅在内存中使用嵌入式数据库，则数据仍需要适合可用内存。我相信hsqldb可以使用临时存储文件，因此仍然可以工作。只是想指出纯粹在内存中运行不能成为选项。 - VoidPointer
0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接