|
锁定老帖子 主题：两个上亿行的大文件取交集
精华帖 (2) :: 良好帖 (0) :: 新手帖 (1) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2012-03-23
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，更好了！ |
| 返回顶楼 | |
|
发表时间：2012-03-23
feikiss 写道 iamxi 写道 前几天再看 编程珠玑第二版，书中第一章就是想楼主那样类似的问题。
像楼主那样，虽然理论上可以实现，但是实际中过亿的数据放入内存，而且用list，系统资源的开销不能不考虑。 恩，我是先把他分解为10个小文件，也就是每个小文件中有1千万行数据，对他们用快排进行排序，然后对这10个子文件进行合并，成为一个大文件即可。 抱歉，没自己看楼主的帖子，粗心了。分10个小文件解决了内存消耗，但是使用硬盘资源的话，IO的读取速度就会成为一个瓶颈，如果对时间的要求比较苛刻，2个文件就要读取2次硬盘，再分10个，那么大部分时间都浪费在反复读取文件上了。 b_l_east的方法是一个好方法。如果文件内都是非负数，你可以构建一个bit的数组，遍历文件，如果i数字则把bit[i]=1，这样两个数组就可以把两个文件内的所有值都放入其中，最后对两个数组进行比较，同一个下标都为1的数字就是交集中的一个元素了。这里不考虑重复的数字。一个byte=8个bit，1一亿个bit，也不过几十M吧。按b_l_east说的，就算是所有int，也不过百兆。 |
| 返回顶楼 | |
|
发表时间：2012-03-23
haoweishow 写道 用shell也不错。
赞同！！ |
| 返回顶楼 | |
|
发表时间：2012-03-23
一个文件排序或者hash 另一个文件直接比较不可以嘛？
|
| 返回顶楼 | |
|
发表时间：2012-03-23
排序，合并，使得相同的能够靠在一起，然后遍历双数的就是焦急了啊~~~
|
| 返回顶楼 | |
|
发表时间：2012-03-23
lixiao 写道 应该也行
sort filea> ta sort fileb> tb comm -12 ta tb 恩，这样的确可以出来结果，但是当文件过大时效率实在急人。。。 我做了下试验，结果如下： 编写的shell脚本： date sort Source1.txt > Source1_test.txt sort Source2.txt > Source2_test.txt comm -12 Source1_test.txt Source2_test.txt > result.txt date 运行结果： Fri Mar 23 12:11:04 CST 2012 Fri Mar 23 13:05:59 CST 2012 也就是说运行了一个多小时。。。。这有点儿急人啊。。。 |
| 返回顶楼 | |
|
发表时间：2012-03-23
iamxi 写道 feikiss 写道 iamxi 写道 前几天再看 编程珠玑第二版，书中第一章就是想楼主那样类似的问题。
像楼主那样，虽然理论上可以实现，但是实际中过亿的数据放入内存，而且用list，系统资源的开销不能不考虑。 恩，我是先把他分解为10个小文件，也就是每个小文件中有1千万行数据，对他们用快排进行排序，然后对这10个子文件进行合并，成为一个大文件即可。 抱歉，没自己看楼主的帖子，粗心了。分10个小文件解决了内存消耗，但是使用硬盘资源的话，IO的读取速度就会成为一个瓶颈，如果对时间的要求比较苛刻，2个文件就要读取2次硬盘，再分10个，那么大部分时间都浪费在反复读取文件上了。 b_l_east的方法是一个好方法。如果文件内都是非负数，你可以构建一个bit的数组，遍历文件，如果i数字则把bit[i]=1，这样两个数组就可以把两个文件内的所有值都放入其中，最后对两个数组进行比较，同一个下标都为1的数字就是交集中的一个元素了。这里不考虑重复的数字。一个byte=8个bit，1一亿个bit，也不过几十M吧。按b_l_east说的，就算是所有int，也不过百兆。 还是支持这个看法。楼主一堆 的代码，看得头痛。也知道又是个没尝过算法的人。不懂得从本质上分析 |
| 返回顶楼 | |
|
发表时间：2012-03-23
最后修改：2012-03-23
支持 b_l_east
|
| 返回顶楼 | |
|
发表时间：2012-03-23
最后修改：2012-03-23
因为，只有2个大文件，不妨反过来做。假定事先知道了数字范围，根据范围，划分成相等的份，然后，每份数字范围（例如其中一份为1至100万，相信很多内存都可以搞定），分别和两个文件中的每行数字进行命中匹配。最后把每份数字范围的匹配结果合并即可。当然，分多少份，要根据实际情况来看，因为会影响重复遍历两个大文件的次数，影响到实际运算时间。
|
| 返回顶楼 | |
|
发表时间：2012-03-23
我觉得这个题目的话，可以试着这样处理
用一个Stringbuilder将所有的行的数字添加在一个字符串里，每个数字用“，”隔开，这样就避免的内存过大的情况，一个Stringbuilder再大也大不到哪里去，接着就用str.contain（“”+”，“）判断另外一个文件中是否含有这个数字。 只是一个想法，欢迎指点！ |
| 返回顶楼 | |
