`
feikiss
  • 浏览: 100006 次
  • 性别: Icon_minigender_1
  • 来自: 西安
社区版块
存档分类
最新评论

两个上亿行的大文件取交集

阅读更多
前两天看到一哥们百度面试归来后发的帖子,并分享了其百度面试题,其中有一个题大意如下:
现有两个上亿行的文件,每一行都只有一个数字,求这两个文件的交集。

我的思路如下:首先是分别对这两个文件排序,然后,再同时遍历这两个文件。求出交集即可。
下面我对大文件的排序进行了简单的实现。
基本思路如下,首先对大文件进行拆分,一亿行的大文件可以拆分成10个小文件,并分别对这10个小文件进行排序,之后对这10个有序的小文件进行遍历,比较,再合并成一个大文件即可完成排序。
里面文件的路径为D://bigfile

代码如下。
main函数在bigFile中。
package com.fly.lee.bigfile;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BigFile {
	private List<String> subFileNameList = new ArrayList<String>();
	private String bigFilePath = "D:/bigfile/";

	private String bigFileName = "Source1.txt";
	private FileGenerator fGenerator = new FileGenerator();
	
	private static final int theMaxNumber = 10000000;
	private List<Integer> theContentWritingToSubFile = new ArrayList<Integer>(theMaxNumber);
	
	public void sortTheBigfile(String destination){
		splitTheBigFile();
		SourceFolder sFolder = new SourceFolder();
		sFolder.setFilenameList(subFileNameList);
		sFolder.setDestination(destination);
		try {
			sFolder.compareFiles();
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		removeTheSubFiles();
	}
	
	public void setBigFilePath(String bigFilePath) {
		this.bigFilePath = bigFilePath;
	}
	
	public void setBigFileName(String bigFileName) {
		this.bigFileName = bigFileName;
	}
	
	private void removeTheSubFiles() {
		for(String fileName:subFileNameList){
			File file = new File(fileName);
			if(file.exists()&&file.canWrite()){
				System.out.println(fileName+":"+file.delete());;
			}
		}
	}

	public void splitTheBigFile(){
		System.out.println("begin to spliting the big files...");
		int counter = 0;
		File file = new File(bigFilePath+bigFileName);
        BufferedReader reader = null;
        FileReader fReader;
        int fileFlag = 1;
        try {
        	fReader = new FileReader(file);
            reader = new BufferedReader(fReader);
            String tempString = null;
            while ((tempString = reader.readLine()) != null) {
            	if(tempString.trim().equals("")){
            		break;
            	}
            	int tempInt = Integer.valueOf(tempString);
            	theContentWritingToSubFile.add(tempInt);
            	if(isTheListFull(counter)){
            		handleTheFullList(fileFlag);
            		theContentWritingToSubFile.clear();
            		fileFlag ++;
            	}
            }
            handleTheFullList(fileFlag);
            fReader.close();
            reader.close();
            System.out.println("finishing the spliting work.");
        }catch(Exception e){
        	e.printStackTrace();
        }
	}

	private void handleTheFullList(int fileFlag) throws Exception {
		System.out.println("handle the full list...");
		String tempFilePath = bigFilePath + fileFlag + ".txt";
		writeTheContentToSubFile(tempFilePath);
		subFileNameList.add(tempFilePath);
		theContentWritingToSubFile.clear();
		System.out.println("the full list is clear now...");
	}
	
	private void writeTheContentToSubFile(String tempFilePath) throws Exception {
		System.out.println("begin to write the content to sub file...");
		System.out.println("sub file path:"+tempFilePath);
		Collections.sort(theContentWritingToSubFile);
		fGenerator.setFileName(tempFilePath);
		fGenerator.setTheListNeedToWriteTofile(theContentWritingToSubFile);
		fGenerator.writeToFileFromTheList(true);
		System.out.println("finishing this loop of writing the content to sub file...");
	}
	
	private boolean isTheListFull(int counter) {
		return theContentWritingToSubFile.size() >= theMaxNumber; 
	}
	
	public static void main(String[] args) {
		BigFile bf = new BigFile();
		bf.setBigFileName("Source1.txt");
		bf.sortTheBigfile("D:/bigfile/Source1_sorted.txt");
	}
}


SourceFolder.java: 主要负责对文件夹下拆分后的小文件进行比较并合并成一个新的有序文件。
package com.fly.lee.bigfile;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class SourceFolder {
	private List<String> filenameList;
	private Map<Integer, Integer> numberCache;
	private List<BufferedReader> bufferedReaderList;
	private int endFlagNumber = 0;
	private List<Integer> contentListWritingToFile;
	private FileGenerator fileGenerator; 
	private String destination = "D:/bigfile/AllSource.txt";
	

	public SourceFolder() {
		contentListWritingToFile = new ArrayList<Integer>();
		filenameList = new ArrayList<String>();
		bufferedReaderList = new ArrayList<BufferedReader>();
		fileGenerator = new FileGenerator();
	}

	public void setDestination(String destination) {
		this.destination = destination;
	}
	public void addFile(String filename) {
		this.filenameList.add(filename);
	}
	public void setFilenameList(List<String> filenameList) {
		this.filenameList = filenameList;
	}

	public void compareFiles() throws Exception {
		System.out.println("filenameList:"+filenameList);
		initTheBufferedReaderList();
		initTheNumberCache();
		while(!isAllFilesFinishTheComparing()){
			int theIndexOfReaderNeedingToMove = findTheLastIndexOfTheMinNumber();
			addTheNumberToFile(theIndexOfReaderNeedingToMove);
			updateNumberCache(theIndexOfReaderNeedingToMove);
		}
		addTheLastListToFile();
		closeAllIOStreams();
	}
	
	private void closeAllIOStreams() throws IOException {

		for(BufferedReader bReader:bufferedReaderList){
			if(bReader != null){
				bReader.close();
			}
		}
		
	}

	private int findTheLastIndexOfTheMinNumber() {
		int theIndexOfTheMinNumber = 0;
		int mixNumber = getTheFirstNumberFromTheCache();
		for (int index = 0; index < numberCache.size(); index++) {
			if(numberCache.get(index) == null){
				continue;
			}
			int theNumberWillBeCompared = numberCache.get(index);
			if (mixNumber >= theNumberWillBeCompared) {
				mixNumber = theNumberWillBeCompared;
				theIndexOfTheMinNumber = index;
			}
		}
		return theIndexOfTheMinNumber;
	}

	private int getTheFirstNumberFromTheCache() {
		for (int index = 0; index < numberCache.size(); index++) {
			if(numberCache.get(index) == null){
				continue;
			}
			return numberCache.get(index);
		}
		return 0;
	}

	private void addTheNumberToFile(int theIndexOfReaderNeedingToMove) throws Exception {
		contentListWritingToFile.add(numberCache.get(theIndexOfReaderNeedingToMove));
		if(contentListWritingToFile.size() == 1000000){
			fileGenerator.setTheListNeedToWriteTofile(contentListWritingToFile);
			fileGenerator.setFileName(destination);
			fileGenerator.writeToFileFromTheList( false);
			contentListWritingToFile.clear();
		}
	}
	
	private void updateNumberCache(int index) throws Exception {
		BufferedReader bufferedReader = bufferedReaderList.get(index);
		String tempString = null;
		if ((tempString = bufferedReader.readLine()) != null) {
			if (!"".equals(tempString.trim())) {
				int tempInt = Integer.valueOf(tempString);
				numberCache.put(index, tempInt);
			}
		} else {
			numberCache.put(index, null);
			endFlagNumber ++;
		}
	}
	
	private void addTheLastListToFile() throws Exception {
		fileGenerator.setTheListNeedToWriteTofile(contentListWritingToFile);
		fileGenerator.setFileName(destination);
		fileGenerator.writeToFileFromTheList(false);
	}

	

	private void initTheBufferedReaderList() throws FileNotFoundException {
		System.out.println("begin to initial the buffered reader...");
		for (String filename : filenameList) {
			BufferedReader bufferedReader = new BufferedReader(new FileReader(
					filename));
			bufferedReaderList.add(bufferedReader);
		}
		System.out.println("finish initialing the buffered reader...");
	}

	private void initTheNumberCache() throws Exception {
		System.out.println("begin to initial the number cache...");
		numberCache = new HashMap<Integer, Integer>(filenameList.size());
		for (int index = 0; index < filenameList.size(); index++) {
			updateNumberCache(index);
		}
		System.out.println("finish initialing the number cache...");
	}

	private boolean isAllFilesFinishTheComparing() {
		
		return endFlagNumber == filenameList.size();
	}
}

FileGenerator.java主要是负责将生成好的链表写入到一指定的文件中,可以选择是覆盖文件或者是在文件后添加。里面也有生成上亿行文件的方法(测试时可以事先用此方法生成大文件。 : ) ).
package com.fly.lee.bigfile;

import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

public class FileGenerator {
	private int wholeLineNumber = 100000000;

	private List<Integer> theListNeedToWriteTofile;
	private String fileName;
	private FileWriter fWriter = null;

	//	public void write
	public static void main(String[] args) {
		String fileName = "D:/bigfile/Source_yiwan.txt";
		FileGenerator fileGenerator = new FileGenerator();
		fileGenerator.setFileName(fileName);
		try {
			fileGenerator.createRandomFile();
			fileGenerator.closeFileWriter();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	public void setFileName(String fileName) {
		this.fileName = fileName;
	}

	public void setWholeLineNumber(int wholeLineNumber) {
		this.wholeLineNumber = wholeLineNumber;
	}
	
	public void setTheListNeedToWriteTofile(List<Integer> theListNeedToWriteTofile) {
		this.theListNeedToWriteTofile = theListNeedToWriteTofile;
	}
	public void createRandomFile() throws Exception {
		int listSize = 10000000;
		theListNeedToWriteTofile = new ArrayList<Integer>(listSize);
		for(int i = 0; i < wholeLineNumber; i ++){
			int tempRandomInt = (int)(Math.random()*100000000);
			theListNeedToWriteTofile.add(tempRandomInt);
			if(theListNeedToWriteTofile.size()==listSize){
				System.out.println("begin to write to the file...");
				writeToFileFromTheList(false);
				theListNeedToWriteTofile.clear();
				System.out.println("finish this loop...");
			}
		}
		writeToFileFromTheList(false);
}

	public void writeToFileFromTheList(boolean isNeedToCreateNewFile) throws Exception {
		System.out.println("write the content to file...");
		try {
			if(isNeedToCreateNewFile){
				createNewFile(fileName);
			}
			StringBuilder contentWritingToFile = new StringBuilder();
			int cycleLineNumber = 1000000;
			int counter = 0;
			fWriter = new FileWriter(fileName,true);
			for(int index = 0; index < theListNeedToWriteTofile.size(); index ++){
				int tempRandomInt = theListNeedToWriteTofile.get(index);
				contentWritingToFile.append(tempRandomInt+"\n");
				if(counter == cycleLineNumber){
					fWriter.append(contentWritingToFile.toString());
					counter = 0;
					contentWritingToFile = new StringBuilder();
				}
			}
//			while(theListNeedToWriteTofile.size() != 0){
//				int tempRandomInt = theListNeedToWriteTofile.remove(0);
//				contentWritingToFile.append(tempRandomInt+"\n");
//				if(counter == cycleLineNumber){
//					fWriter.append(contentWritingToFile.toString());
//					counter = 0;
//					contentWritingToFile = new StringBuilder();
//				}
//			}
			fWriter.append(contentWritingToFile.toString());
			System.out.println("done..........");
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} finally{
			closeFileWriter();
		}
	}

	private void closeFileWriter() throws IOException{
		if(fWriter != null){
			fWriter.close();
		}
	}
	private void createNewFile(String fileName) throws IOException {
		File file = new File(fileName);
		if(file.delete()){
			file.createNewFile();
		}
	}
}

至此,完成了大文件的排序。至于下一步就是对着两个有序的大文件进行遍历比较了,
1.两个索引分别指向两个大文件的第一行。
2.如果两个索引所指的数据一样,记录当前数据到新的文件,并将两个指针分别下移一位。
如果二者不相等,则将数据较小的指针下移一位。
3.判断是否到其中一个文件的结尾,如果是,结束比较,否则重复步骤2。
这样就可以取出二者的交集,代码到此结束。
分享到:
评论

相关推荐

    C# 两个datatable中的数据快速比较返回交集 并集或差集

    1. **交集(Intersection)**:两个DataTable中都存在的行集合。 2. **并集(Union)**:包含两个DataTable所有不重复行的集合。 3. **差集(Difference)**:在一个DataTable中存在的,但在另一个DataTable中不存在...

    计算两个点圈交集

    在计算机科学和地理信息系统(GIS)中,计算两个点集构成的封闭图形的交集是一项常见的几何操作。这个过程涉及到几何对象的操作,如线、多边形和点,以及它们之间的关系判断。以下是对这个任务的详细解释: 首先,...

    opencv和图形计算求取图形交集

    5. **计算交集**:有了两个图形的轮廓后,我们可以进行布尔运算,例如使用`bitwise_and()`函数计算两个图形的交集。这个函数会按像素级别进行比较,返回的结果是两个图形重叠部分的像素值。 6. **结果展示**:最后...

    利用vbs代码提取两个txt文件的交集

    有2个txt文件:qq1.txt和qq2.txt,现用vbs代码实现:提取两者的交集保存为qq3.txt

    Python实现求两个csv文件交集的方法

    本文实例讲述了Python实现求两个csv文件交集的方法。分享给大家供大家参考,具体如下: #!/usr/bin/env python rd3 = open('data_17_17_2.csv') base = open('data_17_17_3.csv') wr3 = open('delNoBuyed3...

    合取范式转析取范式python.zip

    例如,逻辑表达式 (A ∧ B) ∨ (¬C ∧ D) 是一个合取范式,其中 (A ∧ B) 和 (¬C ∧ D) 是两个子句。 析取范式则是由一个或多个子句的析取(OR)组成,每个子句是若干个变量或其否定的合取(AND)。例如,(A ∨ B...

    js代码-两个数组的交集

    本示例将深入探讨如何找到两个数组的交集。交集是指存在于两个数组中的共同元素,它可以帮助我们进行数据过滤和分析。让我们首先从`main.js`文件中的代码开始。 在`main.js`中,我们可能会看到以下用于找出两个数组...

    1.3.2交集、并集.doc

    在数学中,交集(Intersection)和并集(Union)是集合论的基本概念,用于描述两个或多个集合之间元素的共享关系。交集表示两个集合共同拥有的元素组成的集合,而并集则包含两个集合中所有的元素,不区分重复。 在...

    2_链表_求la和lb的交集_源码.zip

    这个压缩包文件“2_链表_求la和lb的交集_源码.zip”似乎包含了一个关于如何寻找两个链表(称为la和lb)交集的源代码实现。下面我们将深入探讨链表以及如何找到它们的交集。 首先,让我们理解链表的基本概念。链表...

    数据结构单链表实现交、并集

    交集(Intersection)是指两个集合中都存在的元素组成的集合,而并集(Union)则是将两个集合中的所有元素合并,不考虑重复。 在单链表中实现这些操作,我们需要遍历两个链表,并进行适当的比较和操作。以下是一个...

    JIHE.rar_交集 并集_数据结构 界面

    例如,对于两个有序表A和B,要找到它们的交集,我们只需从较小的表开始,逐个比较元素,如果元素同时存在于两个表中,就将其添加到结果集中。对于并集,我们可以简单地将两个表连接起来,然后去重,保持原有的排序...

    300 万条《野蛮时代》的玩家数据分析.rar

    这是一份手游《野蛮时代》的用户数据,共有训练集...数据处理:将两个数据文件合并,只取分析要用的字段。然后把数据写到 mysql。 &gt;只取用于分析的字段,因为字段数太多,去掉没用的字段可以极大的节省内存和提高效率

    时间区间取并集Orace存储过程算法实现

    根据提供的文件信息,本文将详细解释“时间区间取并集Oracle存储过程算法实现”的核心概念、设计思路以及具体实现步骤。 ### 一、背景与需求分析 在许多业务场景中,比如日程管理、时间线合并等,我们需要对一系列...

    python 集合 并集、交集 Series list set 转换的实例

    在此代码段中,首先将两个Series对象转换为集合,然后使用intersection方法求出两个集合的交集。交集结果又被转换为一个Series对象,该对象最后被保存为CSV文件。这里还展示了如何将Python集合中的元素提取到一个...

    易语言取数组内容异同源码.7z

    “取数组内容异同”通常指的是比较两个数组之间的差异。在实际编程中,可能存在多种情况:元素个数不同、元素值不同、部分元素相同等。下面是一些处理这类问题的常见方法: 1. **循环遍历法**:通过两个for循环分别...

    Rhino转换Catia文件

    3. 交集计算:Rhino中,当两个自由曲面相交时,Rhino会准确的依据用户所设置的公差值生成相交线。Rhino 默认的精度(公差)为 1/100 mm。 Rhino转换 Catia 文件时,我们需要注意模型的封闭性、破面的问题、精度问题...

    取数组内容异同.rar

    若关注的是只在一个数组中存在的元素,可以使用“并集”和“差集”的概念,即找出两个数组的元素之并,然后减去交集,得到的就是差异元素。 四、易语言取数组内容异同源码 易语言的源码可能包含以下部分: 1. 定义...

    一元一次不等式组导学案(1).pdf

    - 大小、小大取交集:如果两个不等式中一个是“大于”另一个是“小于”,解集取两者解集的交集部分。 6. 课堂应用:通过在数轴上表示不等式的解集,学生可以更加直观地掌握一元一次不等式组的概念,理解解集的含义...

    Python实现快速大文件比较代码解析

    在比较两个大文件时,我们可以先将每个文件中的数据读取到两个列表(list)中,然后转换成集合,最后通过集合的`difference`方法来找出两个集合的差集,即两个文件中不同之处。 以下是一个简单的Python代码示例,展示...

    百度编程大赛初赛练习题

    - 输入文件为`input.txt`,包含多组测试数据,每组数据由两行组成,每行包含两个整数,分别表示一个区间的端点。 - 文件中的每个整数范围在`1`至`1,000,000`之间。 **输出格式**: 对于每组测试数据,输出一个整数...

Global site tag (gtag.js) - Google Analytics