Java大文件内容排序,多路归并排序算法

gemini 贡献于2012-02-03

作者 china  创建于2012-01-05 02:59:00   修改者china  修改于2012-01-05 02:59:00字数6059

文档摘要:外部排序指的是大文件的排序,即待排序的记录存储在外存储器上,待排序的文件无法一次装入内存,*需要在内存和外部存储器之间进行多次数据交换,以达到排序整个文件的目的。*外部排序最常用的算法是多路归并排序,即将原文件分解成多个能够一次性装人内存的部分,*分别把每一部分调入内存完成排序。然后,对已经排序的子文件进行归并排序
关键词:

package com.igo.util.file; import java.io.BufferedReader; import java.io.File; import java.io.FileReader; import java.util.HashSet; import java.util.List; import java.util.Set; import java.util.SortedSet; import java.util.TreeSet; import org.slf4j.Logger; /** * * 外部排序指的是大文件的排序,即待排序的记录存储在外存储器上,待排序的文件无法一次装入内存, * 需要在内存和外部存储器之间进行多次数据交换,以达到排序整个文件的目的。 * 外部排序最常用的算法是多路归并排序,即将原文件分解成多个能够一次性装人内存的部分, * 分别把每一部分调入内存完成排序。然后,对已经排序的子文件进行归并排序。 * @author ZhaoWeikai * Company: * 2010-12-23 下午02:25:00 */ public class MergeSort { private static final Logger log = org.slf4j.LoggerFactory.getLogger(MergeSort.class); /** 拆分大小 , 单位:行 */ private static int SPLIT_SIZE = 100000; public static void main(String[] args) throws Exception { List list = FileUtil.listFiles("E:\\log\\test"); mergeFile(list, "e:/log/testMergeSort.txt"); } public static boolean mergeSort(List originFileList, String outPutFilePath, String tempPath) throws Exception { log.info("mergeSort start............................................."); FileUtil.createDir(tempPath); if (originFileList == null || originFileList.size() == 0) { log.warn("Warning: mergeSort failure, originFileList is empety"); return false; } long beginTime = System.currentTimeMillis(); //拆分文件 splitFile(originFileList, tempPath); log.info("Start Sort and Merge Files, Maybe it takes long time...."); List splitFileFileList = FileUtil.listFiles(tempPath); //合并文件 FileUtil.createFile(outPutFilePath); Set emptySet = new HashSet(); FileUtil.writeFile(outPutFilePath, emptySet, false);//若文件有内容,把文件清空 mergeFile(splitFileFileList, outPutFilePath); log.info("MergeSort end, take time {}S", (System.currentTimeMillis() - beginTime) / 1000 + "" ); //删除拆分临时文件 System.gc(); List listFiles = FileUtil.listFiles(tempPath); int delNum = 0; for (File f : listFiles) { f.delete(); delNum ++; } log.info("delete temp files:{}", delNum ); return true; } /** * 分割文件 * @param inputPath * @return split file num * @throws Exception */ private static int splitFile(List fileList, String tempPath) throws Exception { int fileNum = 1; String line = ""; /*采用默认的String字典比较器, 自动排序*/ //SortedSet set = new TreeSet(new StringInfoComparator()); SortedSet set = new TreeSet(); BufferedReader bufferedReader = null; String fileName = ""; long allFileLength = 0; for (File file : fileList) { allFileLength += file.length(); String parentDirName = FileUtil.getParentDirName(file); bufferedReader = new BufferedReader(new FileReader(file)); fileName = file.getName(); while ((line = bufferedReader.readLine()) != null) { line = line.trim() + " " + parentDirName + " " + fileName; //添加附加信息,便于日后统计 set.add(line); //超过拆分数,写入子文件 if (set.size() >= SPLIT_SIZE) { FileUtil.createFile(tempPath + File.separator + fileNum + ".txt"); FileUtil.writeFile(tempPath + File.separator + fileNum + ".txt", set, false); set.clear(); fileNum++; } } } //对应剩余的行set写入文件 if (set.size() > 0) { FileUtil.createFile(tempPath + File.separator + fileNum + ".txt"); FileUtil.writeFile(tempPath + File.separator + fileNum + ".txt", set, false); set.clear(); } if (bufferedReader != null) { bufferedReader.close(); } log.info("split file end, split file num:{}, all File Length:{}(M)", fileNum, allFileLength/1024/1024); return fileNum; } /** * 合并排序文件 *

* 1.txt(1、3、5、7、9)和2.txt(6、8、9)
* 首先1和6进入treeset。
* 输出1,发现是来自于1.txt的,再读入3,此时set中的元素是6和3。
* 输出3,发现还是来自于1.txt的,再读入5,此时set中的元素是6和5。
* 输出5,发现还是来自于1.txt的,再读入7,此时set中的元素是6和7。
* 输出6,发现来自于2.txt的,读入8,此时set中的元素是8和7。
* 输出7,发现来自于1.txt的,读入9,此时set中的元素是8和9。
* 输出8,发现来自于2.txt的,读入9,此时set中的元素是9和9。 *

* @param splitFilePathList * @param outputPath * @throws Exception */ private static void mergeFile(List splitFileFileList, String outputPath) throws Exception { //fileInfo添加到set SortedSet fileInfoSet = new TreeSet(new FileInfoComparator()); if (fileInfoSet.isEmpty()) { /*初始化每一个文件, 初始化reader*/ long allFileLen = 0; for (File file : splitFileFileList) { FileReader fileReader = new FileReader(file); BufferedReader bufferedReader = new BufferedReader(fileReader, 1024 * 80); FileInfo fileInfo = new FileInfo(); fileInfo.setFileIndex(Integer.parseInt(file.getName().substring(0, file.getName().indexOf(".txt"))));//文件号 fileInfo.setReader(bufferedReader);//reader引用 String value = bufferedReader.readLine(); if (value != null) { fileInfo.setValue(value);//当前值 fileInfo.setLineNum(fileInfo.getLineNum() + 1);//当前行号 fileInfoSet.add(fileInfo); } allFileLen += file.length(); } log.info("MergeSort: All {} files length: {}(M)", splitFileFileList.size(), allFileLen/1024/1024); } /*LinkedHashSet, TreeSet*/ //Set valueSet = new LinkedHashSet(); Set valueSet = new TreeSet(); boolean isSplit = false; //输出set元素 int count = 0; int num = 0; while (!fileInfoSet.isEmpty()) { FileInfo currentFileInfo = fileInfoSet.first(); if (valueSet.add(currentFileInfo.getValue())) count ++; //已经排序号的批量写入文件 if (count >= SPLIT_SIZE) { num ++; FileUtil.writeFile(outputPath, valueSet, true); valueSet.clear(); isSplit = true; log.info("MergeSort: {} lines had finished", num * SPLIT_SIZE); count = 0; } //clone fileInfo FileInfo nextFileInfo = new FileInfo(); nextFileInfo.setFileIndex(currentFileInfo.getFileIndex()); nextFileInfo.setLineNum(currentFileInfo.getLineNum()); nextFileInfo.setValue(currentFileInfo.getValue()); nextFileInfo.setReader(currentFileInfo.getReader()); boolean isSuccess = nextFileInfo.readNextValue(); //未到文件末尾,set中fileInfo重新排序 if (isSuccess) { if (fileInfoSet.remove(currentFileInfo)) { fileInfoSet.add(nextFileInfo); } } //已到文件末尾,从set中移除该fileInfo else { fileInfoSet.remove(currentFileInfo); } } //从未拆分过则一次性写入文件 if (valueSet.size() > 0 && valueSet.size() < SPLIT_SIZE && !isSplit) { FileUtil.writeFile(outputPath, valueSet, false); } //曾拆分过剩余部分写入文件 else if (valueSet.size() > 0 && valueSet.size() < SPLIT_SIZE && isSplit) { FileUtil.writeFile(outputPath, valueSet, true); } log.info("MergeSort: {} lines had finished", num * SPLIT_SIZE + valueSet.size() ); } } package com.igo.util.file; import java.util.Comparator; /** * 文件比较器 */ public class FileInfoComparator implements Comparator { public int compare(FileInfo o1, FileInfo o2) { String mobile1Str = o1.getValue().split("\\s+", 2)[0]; String mobile2Str = o2.getValue().split("\\s+", 2)[0]; long mobile1 = parseLong(mobile1Str); long mobile2 = parseLong(mobile2Str); // if (!mobile1Str.matches("\\d{11,14}$") || !mobile2Str.matches("\\d{11,14}$")) // return -1; if (mobile1 != mobile2) { return (int)(mobile1 - mobile2); } //如果存在重复值则使用文件号比较 else { return o1.getFileIndex() - o2.getFileIndex(); } } public long parseLong(String str) { try { return Long.parseLong(str); } catch (Exception e) { return 0L; } } }

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 5 金币 [ 分享文档获得金币 ] 12 人已下载

下载文档