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

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

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

代码如下。 
main函数在bigFile中。 
Java代码  

1. package com.fly.lee.bigfile;  
2.   
3. import java.io.BufferedReader;  
4. import java.io.File;  
5. import java.io.FileReader;  
6. import java.util.ArrayList;  
7. import java.util.Collections;  
8. import java.util.List;  
9.   
10. public class BigFile {  
11.     private List<String> subFileNameList = new ArrayList<String>();  
12.     private String bigFilePath = "D:/bigfile/";  
13.   
14.     private String bigFileName = "Source1.txt";  
15.     private FileGenerator fGenerator = new FileGenerator();  
16.       
17.     private static final int theMaxNumber = 10000000;  
18.     private List<Integer> theContentWritingToSubFile = new ArrayList<Integer>(theMaxNumber);  
19.       
20.     public void sortTheBigfile(String destination){  
21.         splitTheBigFile();  
22.         SourceFolder sFolder = new SourceFolder();  
23.         sFolder.setFilenameList(subFileNameList);  
24.         sFolder.setDestination(destination);  
25.         try {  
26.             sFolder.compareFiles();  
27.         } catch (Exception e) {  
28.             // TODO Auto-generated catch block  
29.             e.printStackTrace();  
30.         }  
31.         removeTheSubFiles();  
32.     }  
33.       
34.     public void setBigFilePath(String bigFilePath) {  
35.         this.bigFilePath = bigFilePath;  
36.     }  
37.       
38.     public void setBigFileName(String bigFileName) {  
39.         this.bigFileName = bigFileName;  
40.     }  
41.       
42.     private void removeTheSubFiles() {  
43.         for(String fileName:subFileNameList){  
44.             File file = new File(fileName);  
45.             if(file.exists()&&file.canWrite()){  
46.                 System.out.println(fileName+":"+file.delete());;  
47.             }  
48.         }  
49.     }  
50.   
51.     public void splitTheBigFile(){  
52.         System.out.println("begin to spliting the big files...");  
53.         int counter = 0;  
54.         File file = new File(bigFilePath+bigFileName);  
55.         BufferedReader reader = null;  
56.         FileReader fReader;  
57.         int fileFlag = 1;  
58.         try {  
59.             fReader = new FileReader(file);  
60.             reader = new BufferedReader(fReader);  
61.             String tempString = null;  
62.             while ((tempString = reader.readLine()) != null) {  
63.                 if(tempString.trim().equals("")){  
64.                     break;  
65.                 }  
66.                 int tempInt = Integer.valueOf(tempString);  
67.                 theContentWritingToSubFile.add(tempInt);  
68.                 if(isTheListFull(counter)){  
69.                     handleTheFullList(fileFlag);  
70.                     theContentWritingToSubFile.clear();  
71.                     fileFlag ++;  
72.                 }  
73.             }  
74.             handleTheFullList(fileFlag);  
75.             fReader.close();  
76.             reader.close();  
77.             System.out.println("finishing the spliting work.");  
78.         }catch(Exception e){  
79.             e.printStackTrace();  
80.         }  
81.     }  
82.   
83.     private void handleTheFullList(int fileFlag) throws Exception {  
84.         System.out.println("handle the full list...");  
85.         String tempFilePath = bigFilePath + fileFlag + ".txt";  
86.         writeTheContentToSubFile(tempFilePath);  
87.         subFileNameList.add(tempFilePath);  
88.         theContentWritingToSubFile.clear();  
89.         System.out.println("the full list is clear now...");  
90.     }  
91.       
92.     private void writeTheContentToSubFile(String tempFilePath) throws Exception {  
93.         System.out.println("begin to write the content to sub file...");  
94.         System.out.println("sub file path:"+tempFilePath);  
95.         Collections.sort(theContentWritingToSubFile);  
96.         fGenerator.setFileName(tempFilePath);  
97.         fGenerator.setTheListNeedToWriteTofile(theContentWritingToSubFile);  
98.         fGenerator.writeToFileFromTheList(true);  
99.         System.out.println("finishing this loop of writing the content to sub file...");  
100.     }  
101.       
102.     private boolean isTheListFull(int counter) {  
103.         return theContentWritingToSubFile.size() >= theMaxNumber;   
104.     }  
105.       
106.     public static void main(String[] args) {  
107.         BigFile bf = new BigFile();  
108.         bf.setBigFileName("Source1.txt");  
109.         bf.sortTheBigfile("D:/bigfile/Source1_sorted.txt");  
110.     }  
111. }  

SourceFolder.java: 主要负责对文件夹下拆分后的小文件进行比较并合并成一个新的有序文件。 
Java代码  

1. package com.fly.lee.bigfile;  
2.   
3. import java.io.BufferedReader;  
4. import java.io.FileNotFoundException;  
5. import java.io.FileReader;  
6. import java.io.IOException;  
7. import java.util.ArrayList;  
8. import java.util.HashMap;  
9. import java.util.List;  
10. import java.util.Map;  
11.   
12. public class SourceFolder {  
13.     private List<String> filenameList;  
14.     private Map<Integer, Integer> numberCache;  
15.     private List<BufferedReader> bufferedReaderList;  
16.     private int endFlagNumber = 0;  
17.     private List<Integer> contentListWritingToFile;  
18.     private FileGenerator fileGenerator;   
19.     private String destination = "D:/bigfile/AllSource.txt";  
20.       
21.   
22.     public SourceFolder() {  
23.         contentListWritingToFile = new ArrayList<Integer>();  
24.         filenameList = new ArrayList<String>();  
25.         bufferedReaderList = new ArrayList<BufferedReader>();  
26.         fileGenerator = new FileGenerator();  
27.     }  
28.   
29.     public void setDestination(String destination) {  
30.         this.destination = destination;  
31.     }  
32.     public void addFile(String filename) {  
33.         this.filenameList.add(filename);  
34.     }  
35.     public void setFilenameList(List<String> filenameList) {  
36.         this.filenameList = filenameList;  
37.     }  
38.   
39.     public void compareFiles() throws Exception {  
40.         System.out.println("filenameList:"+filenameList);  
41.         initTheBufferedReaderList();  
42.         initTheNumberCache();  
43.         while(!isAllFilesFinishTheComparing()){  
44.             int theIndexOfReaderNeedingToMove = findTheLastIndexOfTheMinNumber();  
45.             addTheNumberToFile(theIndexOfReaderNeedingToMove);  
46.             updateNumberCache(theIndexOfReaderNeedingToMove);  
47.         }  
48.         addTheLastListToFile();  
49.         closeAllIOStreams();  
50.     }  
51.       
52.     private void closeAllIOStreams() throws IOException {  
53.   
54.         for(BufferedReader bReader:bufferedReaderList){  
55.             if(bReader != null){  
56.                 bReader.close();  
57.             }  
58.         }  
59.           
60.     }  
61.   
62.     private int findTheLastIndexOfTheMinNumber() {  
63.         int theIndexOfTheMinNumber = 0;  
64.         int mixNumber = getTheFirstNumberFromTheCache();  
65.         for (int index = 0; index < numberCache.size(); index++) {  
66.             if(numberCache.get(index) == null){  
67.                 continue;  
68.             }  
69.             int theNumberWillBeCompared = numberCache.get(index);  
70.             if (mixNumber >= theNumberWillBeCompared) {  
71.                 mixNumber = theNumberWillBeCompared;  
72.                 theIndexOfTheMinNumber = index;  
73.             }  
74.         }  
75.         return theIndexOfTheMinNumber;  
76.     }  
77.   
78.     private int getTheFirstNumberFromTheCache() {  
79.         for (int index = 0; index < numberCache.size(); index++) {  
80.             if(numberCache.get(index) == null){  
81.                 continue;  
82.             }  
83.             return numberCache.get(index);  
84.         }  
85.         return 0;  
86.     }  
87.   
88.     private void addTheNumberToFile(int theIndexOfReaderNeedingToMove) throws Exception {  
89.         contentListWritingToFile.add(numberCache.get(theIndexOfReaderNeedingToMove));  
90.         if(contentListWritingToFile.size() == 1000000){  
91.             fileGenerator.setTheListNeedToWriteTofile(contentListWritingToFile);  
92.             fileGenerator.setFileName(destination);  
93.             fileGenerator.writeToFileFromTheList( false);  
94.             contentListWritingToFile.clear();  
95.         }  
96.     }  
97.       
98.     private void updateNumberCache(int index) throws Exception {  
99.         BufferedReader bufferedReader = bufferedReaderList.get(index);  
100.         String tempString = null;  
101.         if ((tempString = bufferedReader.readLine()) != null) {  
102.             if (!"".equals(tempString.trim())) {  
103.                 int tempInt = Integer.valueOf(tempString);  
104.                 numberCache.put(index, tempInt);  
105.             }  
106.         } else {  
107.             numberCache.put(index, null);  
108.             endFlagNumber ++;  
109.         }  
110.     }  
111.       
112.     private void addTheLastListToFile() throws Exception {  
113.         fileGenerator.setTheListNeedToWriteTofile(contentListWritingToFile);  
114.         fileGenerator.setFileName(destination);  
115.         fileGenerator.writeToFileFromTheList(false);  
116.     }  
117.   
118.       
119.   
120.     private void initTheBufferedReaderList() throws FileNotFoundException {  
121.         System.out.println("begin to initial the buffered reader...");  
122.         for (String filename : filenameList) {  
123.             BufferedReader bufferedReader = new BufferedReader(new FileReader(  
124.                     filename));  
125.             bufferedReaderList.add(bufferedReader);  
126.         }  
127.         System.out.println("finish initialing the buffered reader...");  
128.     }