两亿数据的交集

前几天在论坛里看到一个帖子说百度的一道面试题，两个文件里各约有两亿行数据，每行只有一个数字，问如何求两个文件中数据的交集。

 

最近对大数据的处理比较感兴趣，所有思考了一下这个问题，对于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的问题。 那么，对于这个面试题，还有没有更好的思路呢？

 

［全文完］