前几天在论坛里看到一个帖子说百度的一道面试题，两个文件里各约有两亿行数据，每行只有一个数字，问如何求两个文件中数据的交集。
?
最近对大数据的处理比较感兴趣，所有思考了一下这个问题，对于JVM来说，两亿数据是非常多的，直接用数组来处理，是行不通的，另外，两亿的数据，效率也是一个重要的考量度。本来可以借助Hash的方法来解决这个问题，但因为每行只有一个数据，也就是只有数字0～9, 那么可以采用一个简便的方法，读取文件中的数字，假如是1, 那么给一个int数组的第1位加1,其他的数字如此类推，假如是2,给这个int数组的第2位加1, 直到所有的数据读取完毕。另外一个文件也采用相同的方法，最后，比较这两个int数组的相同位置上的元素，取当中小的作为交集的个数，比如a[9] = 100, b[9]=80, 那么说明在这两个文件中，有80个数字9是有交集的。最终的交集结果，用这样的统计形式表示，
{0 -- 1000}， 数字0在两个文件中有交集，并且是1000次
{1 -- 999}?
....
{8 -- 2000}
{9 -- 80}
?
基本的思路有了，问题是如何读取两亿个数字呢？即使数据采用分行方式保存，用readLine方法读取，两个文件，总共要读取4亿次，效率肯定是很低的，必须要用buffer，分析buffer，得出数字。从题目本身来说，一行只有一个数字是很好分析buffer的，考量到一定的扩展，本程序假定一行是一个数据，给出一个通用的解析方法。
?
首先定义一个基本的类，很简单，定义数据量，buffer的大小，和数据的最大值，比如10,表示文件里的数据是从0～9, 如果是100, 则是0～99。1000, 则表示0～999，这个最大值也决定了读取数据到目标数组的最大长度。
?
public class Data {
int counter = 200000000;
int bs = 0x80000;
int max = 10;
}
?
DataFinder类，从两个文件输入流中读取数据并且统计到数组，并求交集。因为考虑到每次读取到buffer中的bytes不一定是0x0a结尾，需要考虑这个0x0a在下一次读取的buffer中的情况，需要对上次结尾的一些bytes和本次读取的头几个bytes进行合并。取到一组正确的表示一个数据的bytes后，先转换成String，在转换成integer，根据这个integer来给数组中的一个特定位增加计数器。后来证明，这个思路中，需要花精力去处理的是IO及分析数据部分。
package data.comparison;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
public class DataFinder extends Data {
private int[] readData(InputStream is) throws IOException {
int[] ds = new int[max];
byte[] buff = new byte[bs];
int bc = 0;
byte[] delta = null;
while ((bc = (is.read(buff))) != -1) {
int p = 0;
int i = 0;
if (delta != null) {
while (buff[i++] != 0x0a) {
}
int len = i - p - 1;
byte[] bn = new byte[delta.length + len];
System.arraycopy(delta, 0, bn, 0, delta.length);
System.arraycopy(buff, 0, bn, delta.length, len);
p = i;
int n = Integer.parseInt(new String(bn));
ds[n]++;
delta = null;
}
while (i < bc & p < bc) {
if (buff[i] == 0x0a || i == bc - 1) {
int len = i == bc - 1 ? bc - 1 - p: i - p;
byte[] bn = new byte[len];
if (len==0){
System.out.println();
}
System.arraycopy(buff, p, bn, 0, len);
int n = Integer.parseInt(new String(bn));
ds[n]++;
p = i + 1;
}
i++;
}
if (i == bc && buff[i - 1] != 0x0a) {
delta = new byte[i - p];
System.arraycopy(buff, p, delta, 0, i - p);
}
}
return ds;
}
public void compare(InputStream in1, InputStream in2) throws IOException {
long t = System.currentTimeMillis();
StringBuilder result = new StringBuilder(32);
int[] ds1 = this.readData(in1);
int[] ds2 = this.readData(in2);
for (int i = 0; i < ds1.length & i < ds2.length; i++) {
result.append(String.format("{number: %d, occur: %d}%n", i,
ds1[i] < ds2[i] ? ds1[i] : ds2[i]));
}
System.out.println(result.toString());
System.out.println("--- done ---");
System.out.format("comparison costs %d ms%n", System.currentTimeMillis() - t);
}
public static void main(String args[]) throws IOException {
InputStream in1 = new FileInputStream("file1");
InputStream in2 = new FileInputStream("file2");
new DataFinder().compare(in1, in2);
}
}
?
最后，再写一个随即创造数据的类，
package data.comparison;
import java.io.FileOutputStream;
import java.io.IOException;
import java.util.Random;
public class DataCreator extends Data {
public void random(String file) throws IOException {
long t = System.currentTimeMillis();
FileOutputStream writer = new FileOutputStream(file);
int c = 0;
while (c < counter) {
Random random = new Random();
StringBuilder builder = new StringBuilder(200000);
for (int i = 0; i < bs & c < counter; i++, c++) {
builder.append(random.nextInt(max)).append("\n");
}
writer.write(builder.toString().getBytes());
}
writer.flush();
writer.close();
System.out.format("cost %d ms%n", System.currentTimeMillis() - t);
}
/**
* @param args
* @throws IOException
*/
public static void main(String[] args) throws IOException {
DataCreator dc = new DataCreator();
dc.random("file1");
dc.random("file2");
}
}
?
在I5 2.3G/4G/5400转的硬盘/Mac OS 10.7/JDK6.0.29的软硬件环境上，使用buffer方式后，性能还是比较可以的，随机写两个文件，只需要10秒不到的时间，可以接受。
cost 9313 ms cost 8884 ms
?求两个文件的交集，共花了63秒
{number: 0, occur: 20001948}
{number: 1, occur: 20000771}
{number: 2, occur: 19996245}
{number: 3, occur: 19996415}
{number: 4, occur: 19997276}
{number: 5, occur: 19992915}
{number: 6, occur: 19997709}
{number: 7, occur: 19997344}
{number: 8, occur: 19995041}
{number: 9, occur: 19998757}
--- done ---
comparison costs 63365 ms
?
这个方法把众多的数据转换成一个较小的数组，采用计数器的方法来求交集，算法上很简练，同时也避免了JVM heap开销过大，在读取数据时，另辟蹊径，采用buffer读文件，再从buffer中分析数据，从而避免了IO的问题。 那么，对于这个面试题，还有没有更好的思路呢？
?
［全文完］
相关文章
