一个手机号码剔重的问题

问题

QQ群上有人问了这样一个问题，

现有2个待推广手机号码数据文件，A文件1000W行，B文件是100W，文件中每行记录只有手机号，号码有重复，

请设计高效方案先对A、B数据文件分别进行号码剔重，再找出B文件中在A文件存在的号码，

请写出核心设计思想，并编写代码完整实现。（注：请用纯c实现，不许采用数据库、Memcached等第三方中间件，号码数据文件请自行模拟生成） 

答题要求：请同时提供Word设计文档，和程序源代码（如程序中使用了第三方Jar请注明，jar包请不要上传），打包上传。

思路及分析

我想了一下，看看《编程珠玑》，然后我决定用位图（Bit Map）来解决这个问题。 

有些朋友可能还不了解位图（Bit Map），在这里我先用一个例子来说明。

假设我有一个0到31的集合，集合里面的元素不重复，比如这样{0,3,1,5,2,19,7,8,31,21,10}。通过位图，我可以将这样的集合表示为11110001101000000001010000000001, 其中1表示该数值为下标的数存在在集合中，比如第一个1表示0存在集合中，第二个1表示1存在集合中，等等。通过这样做，我们起码可以得到两个好处

1） 节省空间--我们可以用二进制一个位来存储存储两个信息，一是存不存在，而是存在的数是多少（通过一个bit就可以得到这么多信息，真了不起）。

2） 排序--从左到右遍历这个为图，我们可以得到排序的集合，比如上例中，我们可以得到集合 {0,1,2,3,7,8，10，19,21,31}

如果将所有这电话号码用位图表示，那么需要9999999999个bit （10个9， 考虑到手机号码的第一位都是1）。 9999999999 bit = （9999999999/8） byte = (9999999999 / (8 * 1024)) KB = (9999999999 / 8 *1024*1024) M = 1192M

嗯....，1000万条手机号码装到内存中只用114M左右的内存空间，如果用位图表示，看起来用的内存更多。行不行啊.... 但是考虑到手机号码的前3位都差不多，而且总数最多30个，所有可能考虑把存放1000万条记录的手机号码的大文件拆分一下，这样就位图的位数就降2个数量级了。所以如果我们要在内存中装入手机号码后8位，需要99999999（8个9）个bit，算一下

99999999 bit = （99999999/8） byte = (99999999 / (8 * 1024)) KB = (99999999 / 8 *1024*1024) M = 11.92M

这样好办了，内存够用了。

号码剔重步骤

根据以上的思路，第一步要大文件进行拆分， 以下是Java代码

package art.programming.algorithm;import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.Writer;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;import org.junit.Test;public class BigFileSpliter {private Map fileWriterMap = new HashMap();public void split(File file) throws IOException{
InputStream is;
BufferedReader br;
String line;
is = new FileInputStream(file);
br = new BufferedReader(new InputStreamReader(is));while((line = br.readLine()) != null){
//System.out.println(line);
append(line.substring(0,3)+".txt", line);
}
closeAllWriters();
br.close();
is.close();
}public void append(String fileName, String appendStr) throws IOException{if (!fileWriterMap.containsKey(fileName)){
File file = new File(fileName);
if(!file.exists()){
file.createNewFile();
}
FileWriter fw = new FileWriter(file);
fileWriterMap.put(fileName, fw);
}
fileWriterMap.get(fileName).write(appendStr);
fileWriterMap.get(fileName).write('
');
}public void closeAllWriters(){
for(Writer fw : fileWriterMap.values()){
try {
fw.close();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} finally{
try {
fw.close();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
}public List getAllFileNames(){
Set keys = fileWriterMap.keySet();
List klist = new ArrayList();
for (String key : keys){
klist.add(key);
}Collections.sort(klist);
return klist;
}@Test
public void testSplit() throws IOException{
new BigFileSpliter().split(new File("cellphone.txt"));
}
}

第二步，将文件按照文件名排序，依次读取文件中的电话号码

第三步，将电话号码放到位图中，如果对应的位是1，那么就不要放了（这样就去重了）

第四步，遍历位图，位的值为1的输出到文件中，如果算出的数不足8为10进制的数，前面补0, 比如838，前面补0，变成00000838

以下的Java程序是第二到第四步的实现

package art.programming.algorithm;import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;public class BigFileSort {private final static int RANGE = 32;
private int[] bitMap;private File outputFile;
private File inputFile;
private int bitMapLen = (99999999/RANGE) + RANGE;
FileWriter fw;public BigFileSort(String inputFileName, String outputFileName) throws IOException{
bitMap = new int[bitMapLen];
outputFile = new File(outputFileName);
if (outputFile.exists()){
outputFile.delete();
}
outputFile.createNewFile();
inputFile = new File(inputFileName);
fw = new FileWriter(outputFile);
}public void sortAndOutput() throws IOException{
BigFileSpliter bigFileSpliter = new BigFileSpliter();
bigFileSpliter.split(inputFile);
for (String fileName : bigFileSpliter.getAllFileNames()){
readAndSetBitMap(fileName);
output(fileName.substring(0, 3));
}
//Clean up
fw.close();
}private void readAndSetBitMap(String fileName) throws IOException{
InputStream is;
BufferedReader br;
String line;
is = new FileInputStream(fileName);
br = new BufferedReader(new InputStreamReader(is));
while((line = br.readLine()) != null){
long tmp = Long.parseLong(line.substring(3, 11));
int mod = (int) tmp / RANGE;
int offset = (int) tmp % RANGE;
int bit = bitMap[(int)mod];
if (getBit(bit, offset) != 1){
bit = setBit(bit, offset, 1);
bitMap[(int)mod] = bit;
}else{
System.out.println(fileName.subSequence(0, 3) + toStringRep(tmp) + " duplicates!");
}
}
br.close();
is.close();
}private void output(String prefix) throws IOException{for (int i=0; i< bitMapLen; i++){
for (int offset=0; offset){
if (getBit(bitMap[i], offset) == 1){
long tmp = i * RANGE + offset;
String cellphoneNum = toStringRep(tmp);
fw.write(prefix+cellphoneNum);
fw.write("
");
}
}
}for (int i=0; i< bitMapLen; i++){
bitMap[i] = 0;
}
}private String toStringRep(long tmp){
String cellphoneNum = String.valueOf(tmp);
if (cellphoneNum.length()<8){
StringBuilder sb = new StringBuilder();
for (int j=0; j< 8 - cellphoneNum.length(); j++){
sb.append('0');
}
sb.append(cellphoneNum);
cellphoneNum = sb.toString();
}
return cellphoneNum;
}private int getBit(int signinNum, int bitIndex) {
if( (signinNum & ( 1 << bitIndex)) != 0){
return 1;
}
return 0;
}private int setBit(int num, int bitIndex, int zeroOrOne){
if (zeroOrOne == 1){
num = num | (1 << bitIndex);
}else{
num = num - (1 << bitIndex);
}
return num;
}//整体测试以下
        @Test
public void testSort() throws IOException{
long begin = System.currentTimeMillis();
new BigFileSort("cellphone.txt", "sortedCellphone.txt").sortAndOutput();
System.out.println(System.currentTimeMillis() - begin);
}    }

整个过程，事件花费大约60秒左右

手机号码交集

将A、B文件分别剔重，可以得到电话号码排好序的两个文件。两个文件顺序对比就可以找出交集了。