|
锁定老帖子 主题：两个上亿行的大文件取交集
精华帖 (2) :: 良好帖 (0) :: 新手帖 (1) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2012-03-23
bitmap 或者bloom filter搞定
|
| 返回顶楼 | |
|
发表时间：2012-03-23
思路没有问题，我那时遇到一个面试也是这样搞的
|
| 返回顶楼 | |
|
发表时间：2012-03-23
b_l_east 写道 b_l_east 写道 如果仅仅只是要取两个文件中都存在的数字，而不用管这个数字在两个文件中出现的次数的话，用BitSet就行了。
这个昨天有人讨论过，说给40亿个整数排序。 用数组显然是不行的，太大了，一个整形使用4Byte，1亿个int就会花400M左右的内存，10亿就是4G内存。 因为int的最大数是2^32 - 1 == 约43亿，用一个二进制的下标来表示一个int值，大概需要43亿个bit位，即约43亿/8 = 5.4亿Byte，即约540M的内存。这可以解决问题了。 这里一次只能解决全正数，或全负数，所以要分两次。 不好意思，计算错误，应该是2^31，最高位用来表示符号的，所以内存使用要减半，约270M，更好了！ 我想知道的是，Java中有这个集合吗？BItSet？难道我的API不是最新的？以前从没有用过！ |
| 返回顶楼 | |
|
发表时间：2012-03-23
beijishiqidu 写道 b_l_east 写道 b_l_east 写道 如果仅仅只是要取两个文件中都存在的数字，而不用管这个数字在两个文件中出现的次数的话，用BitSet就行了。
这个昨天有人讨论过，说给40亿个整数排序。 用数组显然是不行的，太大了，一个整形使用4Byte，1亿个int就会花400M左右的内存，10亿就是4G内存。 因为int的最大数是2^32 - 1 == 约43亿，用一个二进制的下标来表示一个int值，大概需要43亿个bit位，即约43亿/8 = 5.4亿Byte，即约540M的内存。这可以解决问题了。 这里一次只能解决全正数，或全负数，所以要分两次。 不好意思，计算错误，应该是2^31，最高位用来表示符号的，所以内存使用要减半，约270M，更好了！ 我想知道的是，Java中有这个集合吗？BItSet？难道我的API不是最新的？以前从没有用过！ 哎，太纠结了。原来自己真的这么水，还需要搜索才可以显示出来，这次真的受教了！ |
| 返回顶楼 | |
|
发表时间：2012-03-24
用sqlload将文件装载到数据库，通过数据库跑批，想怎么样就怎么样
|
| 返回顶楼 | |
|
发表时间：2012-03-24
我没有看你的代码，但是感觉你的算法思路有点怪异，我有个疑问，那要是你把第一个文件分成的十个小文件之后再和第二个文件分成的小文件便利比较的话，会不会出现这个情况；1：暂时吧两个大文件定位A和B，分成的小文件是a1，a2...a10 和b1，b2...b10；要是a1中的数据不在b1中呢？在b5中呢？你怎么比较？这样的结果还是交集吗？2：你不是说大文件里面放不下，你分成小的排序。然后再组合，直接添加模式的写？但是你怎么保证你原来的数据就是有序的，也许你分出来的小文件a1（1,4,7）；a2（2,5，9）他也是排好序的，你怎么添加呢？请LZ解答！我没有看你的代码，但是我觉得你开始描述的思路就有问题。所以请LZ接单我的疑惑！
|
| 返回顶楼 | |
|
发表时间：2012-03-24
这个借助bloom filter的原理来搞，
大体思路如下，把两个文件里的数据都读取到一个bitset里，具体的方法如下， 假如文件的第一个数字是100,把bitset的100设置为1, 另外一个文件也是如此，共用到2个长度为2亿的Bitset，如果非常在意内存耗用，直接用2亿／8的byte[]数组，当然位数要自己算了，而且还需要进行位运算。 所有的数据读完后，直接比较这两个数组里的数据，如果a[i] = b[i],说明数字i同时在两个文件里出现。 这个方案需要考虑正负数，假如文件里有小数点，用bloom filter的原理是不可行的。 从IO上来说，java顺序读文件的性能还能接受。有时间来测试一下这个方案实际表现。 |
| 返回顶楼 | |
|
发表时间：2012-03-24
beijishiqidu 写道 我没有看你的代码，但是感觉你的算法思路有点怪异，我有个疑问，那要是你把第一个文件分成的十个小文件之后再和第二个文件分成的小文件便利比较的话，会不会出现这个情况；1：暂时吧两个大文件定位A和B，分成的小文件是a1，a2...a10 和b1，b2...b10；要是a1中的数据不在b1中呢？在b5中呢？你怎么比较？这样的结果还是交集吗？2：你不是说大文件里面放不下，你分成小的排序。然后再组合，直接添加模式的写？但是你怎么保证你原来的数据就是有序的，也许你分出来的小文件a1（1,4,7）；a2（2,5，9）他也是排好序的，你怎么添加呢？请LZ解答！我没有看你的代码，但是我觉得你开始描述的思路就有问题。所以请LZ接单我的疑惑！
我想说的是，你所有的这些疑问，就是你不单没有看代码，而且没有看我的思路分析。。。建议你再仔细看一下我的思路分析，我不想把他们再粘贴到这里。。。 |
| 返回顶楼 | |
