java - 将巨大的整数文件(一行)拆分为具有内存限制的排序 block

Question

我最近需要将一个单行文件(用“,”分隔的整数)排序​​为更小的 block ，同时考虑到内存限制和效率。我目前遵循这个逻辑:

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，并且必须读取一个包含 10,000,000 个由“,”分隔的整数的单行文件:

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

对于我来说，获得最少数量的排序文件(或每个文件可能的最大数据 block )的最佳方法是什么？

Answer 1

我相信您可以申请Two-Pass Multiway Mergesort (TPMMS)来解决问题。

我将为您提供有关您可以做什么的一般概念，但是，如果您阅读有关 TPMMS 的更多信息会更好:

//每次读取一个 block 时，您必须确保没有遗漏任何数字(如果最后一位是数字，请继续一点点读取，直到到达“，”)

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

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