大文件在有限的内存进行排序

2024-07-10 19:07| 来源: 网络整理| 查看: 265

外部排序

题目：给有限的内存，无限的空间，只有100M的内存，需要对10G的文件进行排序，如何实现？采用外部排序，就是去储存有序的文件，一行一行的整合，不会将整个文件读取到内存中因为是模拟，就不去做这么大的数据量了，这里将题目修改为100M的文件，但是只有100K的内存，进行排序。

0、定义全局遍历

指定一下路径，方便书写

private static final String BASIC_PATH = "D:/sort/"; private static final String SOURCE_PATH = "D:/sort/source.txt"; private static final String RESULT_PATH = "D:/sort/result.txt"; private static final String NEWLINE = "\n"; 1、创建源文件

每一行是一串数字，创建10000000行，简单使用随机数实现创建文件

/** * 创建文件 */ public static void createFile () { try { File file = new File(SOURCE_PATH); int numCount = 10000000; //如果文件存在删除 if (file.exists()) { file.delete(); } Random random = new Random(); FileWriter fw = new FileWriter(file); for (int i = 0; i e.printStackTrace(); } } 2、读取文件并写入新文件

由于内存限制 100K ，所以我们每次只能够读取 10000行，近似100K，主要为了方便看文件读取：

读取整个文件，按行去分割文件，这里的选择是 `10000``行，读取完成后，调用排序并写入，同时记录写入的文件名需要注意未达到长度10000的记录，也需要保存读取完整个文件后，返回写入新文件的文件名列表

内容读取并排序：

读到内存中的数据，可以采用比较快的排序算法对其进行排序，比如快排这里我是直接调用 Java API，也可以自己去实现一个快排，效果都一样的 /** * 外部排序 */ public static List sort() { // 保存分割文件的名称 List fileNames = new ArrayList(); // 读取文件 try { // 读取文件 File file = new File(SOURCE_PATH); BufferedReader fr = new BufferedReader(new FileReader(file)); // 一次读取 10000条记录 final int SIZE = 10000; // 临时存放分割的记录 int[] nums = new int[SIZE]; // 记录分割段 int i = 0; // 分割记录行数 int index = 0; while(true){ i++; // 读取每一行 String num = fr.readLine(); // 当前文件读取完成 if(num == null){ fileNames.add(sortAndSave(nums, index, i)); break; } // 转换每一行的值 nums[index] = Integer.parseInt(num); index++; // 当前段读取完成 if(index == SIZE){ fileNames.add(sortAndSave(nums, index, i)); // 重置，读取下一段 index = 0; } } // 关闭流 fr.close(); } catch (IOException e) { e.printStackTrace(); } return fileNames; } /** * 排序并保存 * 采用快排 * @param nums 要排序数组 * @param size 大小s * @return 排序后的文件名称 */ public static String sortAndSave(int[] nums, int size, int x){ // 可以自己实现，或调用Java API Arrays.sort(nums); // 保存排序后的结果 String fileName = BASIC_PATH + x + "分离.txt"; try { // 创建文件 File file = new File(fileName); BufferedWriter writer = new BufferedWriter(new FileWriter(file)); // 写入文件 for (int i = 0; i e.printStackTrace(); } return fileName; } 3、文件合并排序

在经过 1、2 两步后，文件已经由源文件变成了101个已排序的子文件，多出来的一个是因为空行问题，但也不影响。由于会有空行问题，所以读取字符串判空的时候，不能单单只判断null，还需要判断一下0的情况，可以写一个共用方法

/** * 字符串判空 */ public static boolean strIsEmpty(String str){ return str == null || str.length() == 0; }

通过上一步去获取到文件名列表，进行归并排序，每两个文件去进行比较合并，由于这里我使用的是迭代 + 递归的比较麻烦的实现方案，所以需要判断在最后去判断奇偶的问题（困扰了一小段时间）常用的是递归实现的归并排序比较多，可以尝试使用递归实现然后就是分别读取两个文件进行比较了，比较简单。

/** * 文件合并排序 */ public static void mergeSort(List fileName) { List tempFileNames = new ArrayList(); // 每两个对比一次 for (int i = 0; i // 读取文件 File file1 = new File(fileName.get(i)); // 定义结果名称 String resultName = BASIC_PATH + UUID.randomUUID() + "sortPath.txt"; // 写出流 BufferedWriter bw = new BufferedWriter(new FileWriter(resultName)); //添加到临时结果 tempFileNames.add(resultName); // 读取第一个文件 BufferedReader br = new BufferedReader(new FileReader(file1)); if(i + 1 num1 = Integer.parseInt(numVal1); num2 = Integer.parseInt(numVal2); // 升序排序 if(num1 bw.write(num2 + NEWLINE); numVal2 = br2.readLine(); } } // 读取剩下的内容 while(!strIsEmpty(numVal1)){ bw.write(numVal1 + NEWLINE); numVal1 = br.readLine(); } // 读取剩下的内容 while(!strIsEmpty(numVal2)){ bw.write(numVal2 + NEWLINE); numVal2 = br2.readLine(); } // 关闭流 bw.close(); br.close(); br2.close(); // 删除两个文件 file1.delete(); file2.delete(); } }catch (IOException e){ e.printStackTrace(); } } // 奇数 + 1 if(fileName.size() % 2 != 0){ tempFileNames.add(fileName.get(fileName.size() - 1)); } // 判断是否完成 if(tempFileNames.size() > 1){ // 向下继续合并 mergeSort(tempFileNames); } else{ File file = new File(tempFileNames.get(0)); file.renameTo(new File(RESULT_PATH)); } }

至此，简单实现了外部排序贴出整个文件代码，可以供测试使用

全部代码 package outsideSort; import java.io.*; import java.util.*; /** * @description: * @author: HWH * @create: 2022-08-31 10:35 **/ public class Sort { private static final String BASIC_PATH = "D:/sort/"; private static final String SOURCE_PATH = "D:/sort/source.txt"; private static final String RESULT_PATH = "D:/sort/result.txt"; private static final String NEWLINE = "\n"; /** * 主程序执行 */ public static void main(String[] args) throws IOException, InterruptedException { // 创建文件 createFile(); mergeSort(sort()); } /** * 字符串判空 */ public static boolean strIsEmpty(String str){ return str == null || str.length() == 0; } /** * 文件合并排序 */ public static void mergeSort(List fileName) { List tempFileNames = new ArrayList(); // 每两个对比一次 for (int i = 0; i // 读取文件 File file1 = new File(fileName.get(i)); // 定义结果名称 String resultName = BASIC_PATH + UUID.randomUUID() + "sortPath.txt"; // 写出流 BufferedWriter bw = new BufferedWriter(new FileWriter(resultName)); //添加到临时结果 tempFileNames.add(resultName); // 读取第一个文件 BufferedReader br = new BufferedReader(new FileReader(file1)); if(i + 1 num1 = Integer.parseInt(numVal1); num2 = Integer.parseInt(numVal2); // 升序排序 if(num1 bw.write(num2 + NEWLINE); numVal2 = br2.readLine(); } } // 读取剩下的内容 while(!strIsEmpty(numVal1)){ bw.write(numVal1 + NEWLINE); numVal1 = br.readLine(); } // 读取剩下的内容 while(!strIsEmpty(numVal2)){ bw.write(numVal2 + NEWLINE); numVal2 = br2.readLine(); } // 关闭流 bw.close(); br.close(); br2.close(); // 删除两个文件 file1.delete(); file2.delete(); } }catch (IOException e){ e.printStackTrace(); } } // 奇数 + 1 if(fileName.size() % 2 != 0){ tempFileNames.add(fileName.get(fileName.size() - 1)); } // 判断是否完成 if(tempFileNames.size() > 1){ // 向下继续合并 mergeSort(tempFileNames); } else{ File file = new File(tempFileNames.get(0)); file.renameTo(new File(RESULT_PATH)); } } /** * 外部排序 */ public static List sort() { // 保存分割文件的名称 List fileNames = new ArrayList(); // 读取文件 try { // 读取文件 File file = new File(SOURCE_PATH); BufferedReader fr = new BufferedReader(new FileReader(file)); // 一次读取 10000条记录 final int SIZE = 10000; // 临时存放分割的记录 int[] nums = new int[SIZE]; // 记录分割段 int i = 0; // 分割记录行数 int index = 0; while(true){ i++; // 读取每一行 String num = fr.readLine(); // 当前文件读取完成 if(num == null){ fileNames.add(sortAndSave(nums, index, i)); break; } // 转换每一行的值 nums[index] = Integer.parseInt(num); index++; // 当前段读取完成 if(index == SIZE){ fileNames.add(sortAndSave(nums, index, i)); // 重置，读取下一段 index = 0; } } // 关闭流 fr.close(); } catch (IOException e) { e.printStackTrace(); } return fileNames; } /** * 排序并保存 * 采用快排 * @param nums 要排序数组 * @param size 大小s * @return 排序后的文件名称 */ public static String sortAndSave(int[] nums, int size, int x){ // 可以自己实现，或调用Java API Arrays.sort(nums); // 保存排序后的结果 String fileName = BASIC_PATH + x + "分离.txt"; try { // 创建文件 File file = new File(fileName); BufferedWriter writer = new BufferedWriter(new FileWriter(file)); // 写入文件 for (int i = 0; i e.printStackTrace(); } return fileName; } /** * 创建文件 */ public static void createFile () { try { File file = new File(SOURCE_PATH); int numCount = 10000000; if (file.exists()) { file.delete(); } Random random = new Random(); FileWriter fw = new FileWriter(file); for (int i = 0; i e.printStackTrace(); } } } 总结

总体来说，还是比较简单的，需要注意的是

一定要关闭流，不然会出现奇奇怪怪的问题奇偶问题，要注意处理

本文中储存文件的方式是每行储存一个数，如果是不按行，而是用逗号分割，则需要用read 这里举例一个数据

1,2,3,4,534,453,53,34,9999999

这里不能够按行读取，一次性读取，因为如果没有换行的话，就相当于读取整个文件了，内存不足以去读取整个文件，所以需要按每个数据读取。

/** * 简单测试 */ public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new FileReader("D:/sort/abcs.txt")); // 一个数字 StringBuilder str = new StringBuilder(); while(true){ int a = reader.read(); if(a == ','){ System.out.println(str); str.delete(0, str.length()); continue; } // 终结符，结尾默认 -1 if (a == -1){ System.out.println(str); break; } str.append(a - '0'); } }

【本文地址】

公司简介

联系我们