当前位置：首页 > news >正文

【Java面试】10GB，1GB内存，如何排序？

news 2025/7/1 7:02:35

🔍 一、外部排序步骤

1️⃣ 分块排序（分割阶段）

步骤：
1. 将10GB文件分割为多个内存可容纳的小块（如每个块900MB，共约11块），避免内存溢出。
2. 逐块读取到内存，使用高效排序算法（如Collections.sort()或Arrays.sort()）排序。
3. 将排序后的块写入临时文件，生成11个有序子文件。

关键代码：

List<File> splitAndSort(File input) throws IOException {List<File> chunks = new ArrayList<>();try (BufferedReader reader = new BufferedReader(new FileReader(input))) {List<String> buffer = new ArrayList<>();String line;while ((line = reader.readLine()) != null) {buffer.add(line);if (buffer.size() >= 10_000_000) { // 控制块大小chunks.add(sortAndSave(buffer));buffer.clear();}}if (!buffer.isEmpty()) chunks.add(sortAndSave(buffer));}return chunks;
}File sortAndSave(List<String> data) throws IOException {Collections.sort(data); // 内部排序File tempFile = File.createTempFile("chunk", ".txt");tempFile.deleteOnExit();try (BufferedWriter writer = new BufferedWriter(new FileWriter(tempFile))) {for (String str : data) {writer.write(str);writer.newLine();}}return tempFile;
}

2️⃣ 多路归并（合并阶段）

原理：使用最小堆（PriorityQueue）合并有序子文件，减少磁盘IO次数。
优化：
- 缓冲区管理：为每个子文件分配约100MB缓冲区，预读数据到内存。
- 堆优化：堆中存储每个文件的当前最小元素，弹出最小值后补充新元素。

关键代码：

void mergeFiles(List<File> chunks, File output) throws IOException {PriorityQueue<BufferedLine> minHeap = new PriorityQueue<>();List<BufferedReader> readers = new ArrayList<>();// 初始化堆和读取器for (File file : chunks) {BufferedReader reader = new BufferedReader(new FileReader(file));readers.add(reader);String line = reader.readLine();if (line != null) minHeap.add(new BufferedLine(line, reader));}try (BufferedWriter writer = new BufferedWriter(new FileWriter(output))) {while (!minHeap.isEmpty()) {BufferedLine min = minHeap.poll();writer.write(min.line.replaceAll("\\d+$", "")); // 删除行尾序号writer.newLine();String nextLine = min.reader.readLine();if (nextLine != null) minHeap.add(new BufferedLine(nextLine, min.reader));}}// 关闭所有读取器for (BufferedReader reader : readers) reader.close();
}class BufferedLine implements Comparable<BufferedLine> {String line;BufferedReader reader;public BufferedLine(String line, BufferedReader reader) {this.line = line; this.reader = reader;}@Overridepublic int compareTo(BufferedLine o) {return this.line.compareTo(o.line); // 按字符串排序}
}

🚀 二、优化策略

减少IO开销：
- 增大缓冲区（如100MB/文件），减少磁盘读取次数。
- 使用BufferedReader和BufferedWriter加速读写]。
动态分块：
- 根据数据特征调整分块策略，若数据分布均匀可用桶排序（如按数值范围分桶）。
归并路数控制：
- 内存限制下，归并路数k需满足：k * 缓冲区大小 ≤ 1GB。例如11个文件需每个缓冲区≤90MB。
资源清理：
- 临时文件用File.deleteOnExit()自动删除。