|
锁定老帖子 主题：两个上亿行的大文件取交集
精华帖 (2) :: 良好帖 (0) :: 新手帖 (1) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2012-03-22
最后修改：2012-03-23
前两天看到一哥们百度面试归来后发的帖子，并分享了其百度面试题，其中有一个题大意如下：
现有两个上亿行的文件，每一行都只有一个数字，求这两个文件的交集。 我的思路如下：首先是分别对这两个文件排序，然后，再同时遍历这两个文件。求出交集即可。 下面我对大文件的排序进行了简单的实现。 基本思路如下，首先对大文件进行拆分，一亿行的大文件可以拆分成10个小文件，并分别对这10个小文件进行排序，之后对这10个有序的小文件进行遍历，比较，再合并成一个大文件即可完成排序。【忘记说了，内存中装不下两个大文件。。。现在补上，2012年3月23号 添加。。。。】 里面文件的路径为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。 这样就可以取出二者的交集，代码到此结束。 声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
|
发表时间：2012-03-22
应该也行
sort filea> ta sort fileb> tb comm -12 ta tb |
| 返回顶楼 | |
|
发表时间：2012-03-23
用shell也不错。
|
| 返回顶楼 | |
|
发表时间：2012-03-23
根据文件里的数字范围，比如负数还是正数及数值范围直接构建1个或多个数组，数组下标可以直接采用文件中的数值或通过转换后的数值，读一个文件在相应标志位计数，然后遍历这些数组就能得到按顺序的，两个文件的交集了
|
| 返回顶楼 | |
|
发表时间：2012-03-23
这种方法很好想到，也是常规的做法。
有比较另类的做法么？ |
| 返回顶楼 | |
|
发表时间：2012-03-23
如果仅仅只是要取两个文件中都存在的数字，而不用管这个数字在两个文件中出现的次数的话，用BitSet就行了。
这个昨天有人讨论过，说给40亿个整数排序。 用数组显然是不行的，太大了，一个整形使用4Byte，1亿个int就会花400M左右的内存，10亿就是4G内存。 因为int的最大数是2^32 - 1 == 约43亿，用一个二进制的下标来表示一个int值，大概需要43亿个bit位，即约43亿/8 = 5.4亿Byte，即约540M的内存。这可以解决问题了。 这里一次只能解决全正数，或全负数，所以要分两次。 |
| 返回顶楼 | |
|
发表时间：2012-03-23
最后修改：2012-03-23
前几天再看 编程珠玑第二版，书中第一章就是想楼主那样类似的问题。
像楼主那样，虽然理论上可以实现，但是实际中过亿的数据放入内存，而且用list，系统资源的开销不能不考虑。 |
| 返回顶楼 | |
|
发表时间：2012-03-23
ding.wei 写道 根据文件里的数字范围，比如负数还是正数及数值范围直接构建1个或多个数组，数组下标可以直接采用文件中的数值或通过转换后的数值，读一个文件在相应标志位计数，然后遍历这些数组就能得到按顺序的，两个文件的交集了
你是说把文件全部读进去么？这道题的关键是内存装不下全部啊。。。。我把它分解为10个小文件，读取每个小文件的时候JavaW.exe占内存已经1G了。。。 |
| 返回顶楼 | |
|
发表时间：2012-03-23
iamxi 写道 前几天再看 编程珠玑第二版，书中第一章就是想楼主那样类似的问题。
像楼主那样，虽然理论上可以实现，但是实际中过亿的数据放入内存，而且用list，系统资源的开销不能不考虑。 恩，我是先把他分解为10个小文件，也就是每个小文件中有1千万行数据，对他们用快排进行排序，然后对这10个子文件进行合并，成为一个大文件即可。 |
| 返回顶楼 | |
|
发表时间：2012-03-23
用bit集吧，上亿行的数据又不大，可能数(负数)和下标需要对应一下。。。先所有位置默认为0，然后遍历一个文件，存在的位置改为1，然后遍历另一个文件，对比，如果在相应位置为1，则说明重复。
|
| 返回顶楼 | |
