要点:
- 我们每天并发处理数千个平面文件。
- 内存限制是一个主要问题。
- 我们为每个文件处理使用线程。
- 我们不按列排序。 文件中的每一行(记录)被视为一列。
无法执行的事情:
- 我们不能使用Unix / Linux的排序命令。
- 无论它们有多轻,我们都不能使用任何数据库系统。
现在,我们不能只是将所有内容加载到集合中并使用排序机制。 它将耗尽所有内存,并且程序将获得堆错误。
在这种情况下,您将如何对文件中的记录/行进行排序?
要点:
无法执行的事情:
现在,我们不能只是将所有内容加载到集合中并使用排序机制。 它将耗尽所有内存,并且程序将获得堆错误。
在这种情况下,您将如何对文件中的记录/行进行排序?
看起来你要找的是外部排序。
基本上,你需要先对小块数据进行排序,将其写回磁盘,然后迭代这些块以对所有数据进行排序。
如其他人所述,您可以分步处理。
我想用自己的话解释一下(在第3点上有所不同):
按顺序读取文件,在内存中每次处理N条记录(N是任意的,取决于您的内存限制和要创建的临时文件数T)。
将N条记录在内存中排序,并将它们写入一个临时文件。重复使用T直到完成。
同时打开所有T个临时文件,但仅从每个文件中读取一条记录。(当然,使用缓冲区)。对于这些T个记录中的每一个,找到最小值,将其写入最终文件,并只在该文件中前进。
优点:
数字示例:
已编辑
您提到了一个多线程应用程序,所以我想......
正如我们从这些讨论中所看到的,在这种情况下使用较少的内存会导致性能降低,这个因素是非常严重的。所以我还可以建议只使用一个线程来处理每次只进行一次排序,而不是作为多线程应用程序。
如果您使用十个线程,每个线程都有十分之一可用的内存,则性能将很差,远远低于初始时间的十分之一。如果您只使用一个线程,并将其他9个任务排队并依次处理它们,则总体性能将更好,您会更快地完成十个任务。
在阅读这篇回答后: Sort a file with huge volume of data given memory constraint 我建议您考虑使用分布式排序。在您的环境中,这可能是一个巨大的收益。
与我的建议相比,它的改进之处在于您不需要同时打开所有临时文件,只需打开其中一个即可。这能够救您一命! :-)
尽管您有限制,我仍然会使用嵌入式数据库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
您可以将文件分成较小的部分进行读取,对这些部分进行排序并将它们写入临时文件中。然后您再次顺序读取其中的两个部分并将它们合并成一个更大的临时文件,以此类推。如果只剩下一个,那么您就有了已排序的文件。基本上,这就是在外部文件上执行Megresort算法。它可很好地扩展到任意大的文件,但会导致一些额外的文件I/O。
编辑:如果您对文件行的可能变化有一些了解,可以使用更高效的算法(分布排序)。简单来说,您只需读取原始文件一次,并将每行写入一个只包含具有相同首字母(或某个特定范围的首字母)的行的临时文件中。然后,您按升序迭代所有(现在较小的)临时文件,在内存中对它们进行排序,并直接将它们附加到输出文件中。如果某个临时文件过大而无法在内存中排序,则可以基于行中的第二个字符重复相同的过程,以此类推。因此,如果您的第一个分区足够好以产生足够小的文件,则不管文件大小如何,您仅需要100%的I / O开销,但在最坏的情况下,它可能会比性能稳定的合并排序更多。
Alan Smith
Jon Doe
Bill Murray
Johnny Cash
让我们构建H()函数,使其使用记录中的第一个字母,这样您可能会得到多达26个文件,但在此示例中,您只会得到3个:
<file1>
Alan Smith
<file2>
Bill Murray
<file10>
Jon Doe
Johnny Cash
如果您的限制只是不使用外部数据库系统,您可以尝试使用嵌入式数据库(例如Apache Derby)。这样,您就可以获得所有数据库的优点,而不需要任何外部基础设施依赖。
这里有一种方法可以在不过度使用Java内部排序和不使用数据库的情况下完成。 假设:您有1TB的空间,并且文件包含或以唯一数字开头,但未排序
将文件分割N次。
逐个读取这N个文件,并为每个行/数字创建一个文件。
将该文件命名为相应的数字。在命名时保持计数器已更新以存储最小值。
现在您已经可以将文件的根文件夹标记为按名称排序,或者暂停程序以给您时间在操作系统上发出按名称排序的命令。您也可以通过编程方式执行此操作。
现在,您拥有了通过名称排序的文件夹,使用计数器开始逐个处理每个文件,将数字放入输出文件中,并关闭它。
完成后,您将获得一个带有排序数字的大型文件。
我知道你提到了不使用数据库,即使是轻量级的...所以,也许这不是一个选项。但是,内存中的hsqldb怎么样...提交它,通过查询进行排序,清除它。只是一个想法。
你可以使用SQL Lite文件数据库,将数据加载到数据库中,然后让它为你排序并返回结果。 优点:无需担心编写最佳排序算法。 缺点:你需要磁盘空间,处理速度较慢。 https://sites.google.com/site/arjunwebworld/Home/programming/sorting-large-data-files