给定内存约束时，对具有大量数据的文件进行排序
要点：
- 我们同时处理数千个平面文件。
- 内存约束是一个主要问题。
- 我们为每个文件进程使用线程。
- 我们不按列排序。 文件中的每一行（记录）都被视为一列。
做不到：
- 我们不能使用unix / linux的sort命令。
- 我们不能使用任何数据库系统，无论它们有多么轻盈。
现在，我们不能只加载集合中的所有内容并使用排序机制。 它会占用所有内存，程序会出现堆错误。
在那种情况下，您如何对文件中的记录/行进行排序？
看起来你正在寻找的是外部排序 。
基本上，您首先对小块数据进行排序，将其写回磁盘，然后迭代这些数据以对所有数据进行排序。
您可以读取较小部分的文件，对它们进行排序并将它们写入临时文件。 然后你再次按顺序读取其中的两个并将它们合并到一个更大的临时文件中，依此类推。 如果只剩下一个，则排序文件。 基本上就是在外部文件上执行的Megresort算法。 它可以很好地扩展到任意大文件，但会导致一些额外的文件I / O.
编辑：如果您对文件中行的可能差异有一些了解，则可以使用更有效的算法（分布排序）。 简化后，您将读取原始文件一次，并将每行写入临时文件，该文件仅使用具有相同第一个字符（或特定范围的第一个字符）的行。 然后按升序迭代所有（现在很小的）临时文件，在内存中对它们进行排序并将它们直接附加到输出文件中。 如果临时文件太大而无法在内存中进行排序，则可以根据行中的第二个字符重新为此进行相同的处理，依此类推。 因此，如果您的第一个分区足够好以生成足够小的文件，那么无论文件有多大，您都只有100％的I / O开销，但在最坏的情况下，它可以变得比性能明智的稳定合并排序更多。
尽管有限制，我还是会使用嵌入式数据库SQLITE3 。 像你一样，我每周工作10-15百万个平面文件行，导入和生成排序数据非常非常快，你只需要一点免费的可执行文件（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
我会启动一个EC2集群并运行Hadoop的MergeSort 。
编辑 ：不确定您想要多少细节，或者什么。 EC2是亚马逊的弹性计算云 – 它允许您以低成本按小时租用虚拟服务器。 这是他们的网站 。
Hadoop是一个开源MapReduce框架，专为大型数据集的并行处理而设计。 当MapReduce可以被分割成可以单独处理然后合并在一起的子集时，作业是MapReduce的一个很好的候选者，通常是通过对键进行排序（即分而治之的策略）。 这是它的网站 。
正如其他海报所提到的，外部排序也是一个很好的策略。 我认为我在两者之间决定的方式取决于数据的大小和速度要求。 一台机器可能会被限制为一次处理一个文件（因为您将耗尽可用内存）。 因此，只有在需要以更快的速度处理文件时，才能查看EC2之类的内容。
正如其他提到的，您可以按步骤处理。
我想用我自己的话解释这一点（第3点不同）：
-
按顺序读取文件，在内存中一次处理N条记录（N是任意的，具体取决于您的内存约束和您想要的临时文件的数量T.）。
-
对内存中的N条记录进行排序，将它们写入临时文件。 循环在T上，直到你完成。
-
同时打开所有T temp文件，但每个文件只读一个记录。 （当然，有缓冲区）。 对于这些T记录中的每一个，找到较小的记录，将其写入最终文件，并仅在该文件中前进。
优点：
- 内存消耗尽可能低。
- 与内存中的所有内容策略相比，您只能执行双倍的磁盘访问 。 不错！ 🙂
例如：
- 原始文件有100万条记录。
- 选择有100个临时文件，因此一次读取和排序10 000条记录，并将它们放在自己的临时文件中。
- 一次打开100个临时文件，读取内存中的第一条记录。
- 比较第一个记录，写下较小的并提前该临时文件。
- 在第5步循环，一百万次。
EDITED
你提到了一个multithreading应用程序，所以我想知道……
正如我们从这些关于这种需求的讨论中看到的那样，使用较少的内存会降低性能，在这种情况下具有显着的影响。 所以我也建议一次只使用一个线程来处理一种，而不是multithreading应用程序。
如果你处理十个线程，每个线程有十分之一的可用内存，你的性能将会很糟糕，远远低于初始时间的十分之一。 如果您只使用一个线程，并排队其他9个需求并依次处理它们，那么您的全局性能会更好，您将更快地完成十个任务。
阅读此响应后： 在给定内存约束的情况下对具有大量数据的文件进行排序我建议您考虑这种分布排序。 在你的背景下，这可能是巨大的收获。
我的提议的改进是你不需要一次打开所有临时文件，只打开其中一个。 它可以节省您的一天！ 🙂
如果您的限制只是不使用外部数据库系统，则可以尝试使用嵌入式数据库（例如Apache Derby ）。 这样，您就可以获得数据库的所有优势，而无需任何外部基础结构依赖性。
您可以使用以下分而治之的策略：
创建一个函数H（），它可以为输入文件中的每个记录分配一个数字。 对于将在记录r1后面排序的记录r2，它必须为r2返回比r1更大的数字。 使用此函数将所有记录分区为适合内存的单独文件，以便对其进行排序。 完成后，您可以连接已排序的文件以获取一个大的已排序文件。
假设您有此输入文件，其中每行代表一条记录
Alan Smith Jon Doe Bill Murray Johnny Cash
让我们构建H（），以便它使用记录中的第一个字母，这样你最多可以获得26个文件，但在这个例子中你将得到3个：
Alan Smith Bill Murray Jon Doe Johnny Cash
现在您可以对每个文件进行排序。 哪个会在
请注意，您先划分，然后再征服（排序）。 但是，确保以需要排序的结果部分不重叠的方式进行分区，这将使得合并结果更加简单。
实现分区函数H（）的方法在很大程度上取决于输入数据的性质。 一旦你找到了那部分，剩下的应该是轻而易举的。
我知道你提到不使用数据库，无论多么轻……所以，也许这不是一个选择。 但是，内存中的hsqldb呢…提交它，按查询排序，清除它。 只是一个想法。
您可以使用SQL Lite文件db，将数据加载到db，然后让它排序并为您返回结果。 优点：无需担心编写最佳排序算法。 缺点：您将需要磁盘空间，处理速度较慢。 https://sites.google.com/site/arjunwebworld/Home/programming/sorting-large-data-files
这是一种方法，无需大量使用内部Java并且不使用DB。 假设：您有1TB空间，文件包含或以唯一编号开头，但未分类
将文件分为N次。
逐个读取这N个文件，并为每个行/数创建一个文件
将该文件命名为具有相应编号的文件。同时命名保持计数器更新以存储最少计数。
现在，您已经可以将文件的根文件夹标记为按名称排序，或者暂停程序，以便您有时间在操作系统上触发命令以按名称对文件进行排序。 你也可以通过编程方式完成。
现在你有一个文件夹，其文件按名称排序，使用计数器开始逐个获取每个文件，将数字放在OUTPUT文件中，关闭它。
完成后，您将拥有一个包含已排序数字的大文件。
你只需要两个临时文件 – 源和目标 – 以及你想要的内存很少。 在第一步，您的源是原始文件，在最后一步，目标是结果文件。
在每次迭代时：
- 从源文件中读取一个缓冲区的一半数据块的滑动缓冲区;
- 整理缓冲区
- 写入目标文件缓冲区的前半部分。
- 将缓冲区的后半部分移到开头并重复
保留一个布尔标志，说明您是否必须在当前迭代中移动一些记录。 如果标志仍为false，则对文件进行排序。 如果已引发，请使用目标文件作为源重复此过程。
最大迭代次数:(文件大小）/（缓冲区大小）* 2
如果您可以在文件中向前/向后移动（搜索），并重写文件的某些部分，那么您应该使用冒泡排序 。
您必须扫描文件中的行，目前只需要在内存中有2行，然后如果它们的顺序不正确则交换它们。 重复此过程，直到没有要交换的文件。