两亿数据的交集

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

?

最近对大数据的处理比较感兴趣，所有思考了一下这个问题，对于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，这个最大值也决定了读取数据到目标数组的最大长度。

?

{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的问题。 那么，对于这个面试题，还有没有更好的思路呢？

?

［全文完］