给定内存约束时,对具有大量数据的文件进行排序

Question

要点:

• 我们同时处理数千个平面文件.
• 内存约束是一个主要问题.
• 我们为每个文件进程使用线程.
• 我们不按列排序.文件中的每一行(记录)都被视为一列.

做不到:

• 我们不能使用unix/linux的sort命令.
• 我们不能使用任何数据库系统,无论它们有多么轻盈.

现在,我们不能只加载集合中的所有内容并使用排序机制.它会占用所有内存,程序会出现堆错误.

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

Answer 1

看起来你正在寻找的是 外部排序.

基本上,您首先对小块数据进行排序,将其写回磁盘,然后迭代这些数据以对所有数据进行排序.

Answer 2

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

编辑:如果您对文件中行的可能差异有一些了解,则可以使用更有效的算法(分发排序).简化后,您将读取原始文件一次,并将每行写入临时文件,该文件仅包含具有相同第一个字符(或特定范围的第一个字符)的行.然后按升序迭代所有(现在很小的)临时文件,在内存中对它们进行排序并将它们直接附加到输出文件中.如果临时文件太大而无法在内存中进行排序,则可以根据行中的第二个字符重新为此进行相同的处理,依此类推.因此,如果您的第一个分区足够好以生成足够小的文件,那么无论文件有多大,您都只有100%的I/O开销,

Answer 3

尽管有限制,我还是会使用嵌入式数据库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

Answer 4

我会启动一个EC2集群并运行Hadoop的MergeSort.

编辑:不确定您想要多少细节,或者什么.EC2是亚马逊的弹性计算云 - 它允许您以低成本按小时租用虚拟服务器.这是他们的网站.

Hadoop是一个开源MapReduce框架,专为大型数据集的并行处理而设计.作业是MapReduce的一个很好的候选者,它可以被分割成可以单独处理然后合并在一起的子集,通常是通过对键进行排序(即分而治之的策略).这是它的网站.

正如其他海报所提到的,外部排序也是一个很好的策略.我认为我在两者之间决定的方式取决于数据的大小和速度要求.一台机器可能会被限制为一次处理一个文件(因为您将耗尽可用内存).因此,只有在需要以更快的速度处理文件时,才能查看类似EC2的内容.

Answer 5

正如其他提到的,您可以按步骤处理.
我想用我自己的话解释这一点(第3点不同):

1. 按顺序读取文件,在内存中一次处理N条记录(N是任意的,具体取决于您的内存约束和您想要的临时文件的数量T.).

2. 对内存中的N条记录进行排序,将它们写入临时文件.循环在T上,直到你完成.

3. 同时打开所有T temp文件,但每个文件只读一条记录.(当然,有缓冲区).对于这些T记录中的每一个,找到较小的记录,将其写入最终文件,并仅在该文件中前进.

好处:

• 该内存消耗,你想要的低.
• 与内存中的所有内容策略相比,您只能执行双倍的磁盘访问.不错!:-)

例如:

1. 原始文件有100万条记录.
2. 选择有100个临时文件,因此一次读取和排序10 000条记录,并将它们放在自己的临时文件中.
3. 一次打开100个临时文件,读取内存中的第一条记录.
4. 比较第一个记录,写下较小的并提前该临时文件.
5. 循环在第5步,一百万次.

EDITED

你提到了一个多线程应用程序,所以我想知道......

正如我们从这些关于这种需求的讨论中看到的那样,使用更少的内存会降低性能,在这种情况下具有显着的影响.所以我也建议一次只使用一个线程来处理一种,而不是多线程应用程序.

如果你处理十个线程,每个线程有十分之一的可用内存,你的性能将会很糟糕,远远低于初始时间的十分之一.如果您只使用一个线程,并将其他9个需求排队并依次处理它们,那么您的全局性能会更好,您将更快地完成十个任务.

阅读此响应之后: 在给定内存约束的情况下对具有大量数据的文件进行排序 我建议您考虑这种分发排序.在你的背景下,这可能是巨大的收获.

我的提议的改进是你不需要一次打开所有临时文件,只打开其中一个.它可以节省您的一天!:-)