java将巨大的整数文件（在一行中）拆分为具有内存限制的已排序块

Question

我最近需要将一个单行文件（整数以“，”分隔）排序为更小的块，并考虑内存限制和效率。我目前正遵循这一逻辑：

File file = new File("bigfile.txt");
FileInputStream fis = new FileInputStream(file);
BufferedInputStream bis = new BufferedInputStream(fis);
int BUFFER_SIZE = 10; // can and should be bigger
byte[] bytes = new byte[BUFFER_SIZE];
while ((bis.read(bytes)) != -1) {
   // convert bytes to string
   // split bytes to String[]
   // save the last number if was cut in the middle and save it for the next round of reading and remove it from the current String[]
   // fix cut number if necessary and put it in the String[]
   // sort the String[]
   // write the String[] into a file
   // call Garbage collector to prevent memory leak?
}
bis.close();

假设我的内存限制为5MB，并且必须读取一行文件，其中10000000个整数由“，”分隔：

• 如果我使用非常小的缓冲区大小（例如10）来读取文件，那么我将 创建数千个文件
• 如果我使用一个合适但仍然很小的缓冲区大小（例如100KB），那么我会 仍然有很多文件
• 如果我使用更大的缓冲区大小（例如4MB），那么我将拥有堆 由于限制，在内存中对结果进行排序和拆分时出现问题

对于我来说，获取最少已排序文件（或每个文件最大数据块）的最佳方法是什么

Answer 1

这项任务并不容易。我相信这不是最好的方法，但总比没有好：

1. 使用size和comparator构造函数参数查找或创建类似list的PriorityQueue。应知道尺寸（根据您的要求）
   • 方法add(..)应该匹配O(log n)并在插入项时对其进行排序
   • 当列表完全填充时，方法add(..)应返回false（否则true）
2. 立即执行流读取和（无缓冲）将整数添加到集合中。如果没有可用空间，请创建新列表
3. 现在您有了一个排序列表的集合。最后一步是通过列表对数据进行排序： [1,4,5],[3,8,9],[2,6,7]>[1,2,3], [4,5,6], [7,8,9] 例如，通过从列表#1和列表#2中选取最小值，比较它们，等等

注意：您还可以同时执行步骤#3

关于#2： 我没注意到你有字符串数据。所以将字节序列解析为整数是个坏主意。但是，应该可以逐个字符解析数据，然后在出现逗号时转换为int。此外，还可以计算缓冲区大小（最大数字长度*每个符号的字节数）——>；UTF-8中的2147483647,是11*1

Answer 2

我相信你可以用Two-Pass Multiway Mergesort (TPMMS)来解决这个问题

我将向您提供您可以做什么的总体想法，但是，如果您阅读更多有关胎压监测系统的内容，则会更好：

//每次读取数据块时，必须确保没有遗漏任何数字（如果最后一位是数字，则继续逐位读取，直到到达“，”）

• 给定有限数量的RAM并遵循TPPM，您必须将文件分成块，对其排序，然后将每个块保存到单独的文件中
• 对于每个文件，创建一个PriorityQueue并读取一定数量的字节（这样您就可以读取所有小文件），然后将它们转换回数字以将其存储在队列中。为了方便起见，我将此优先队列列表称为pqs
• 创建另一个PriorityQueue（pq），其大小等于您拥有的小文件数，并推送每个队列的第一个值pqs
• 现在是有趣的部分；由于您使用的是PriorityQueue（pq），并且在pqs中弹出了每个PriorityQueue的第一个值，因此可以保证pq中的第一个值是最小值（对于在pq中弹出的每个元素，您可以直接将其写入最终文件，也可以将其保存在数组中，并在数组已满时将其写入最终文件，我更喜欢最后一个选项。）
• 每次弹出pq时，必须从获取该值的文件中读取下一个数字，将其放入pqs中正确的优先级队列，然后弹出该优先级队列的第一个值
• 重复上一步，直到pqs中的所有优先级队列都为空

由于内存量有限，您必须调整每个缓冲区的大小