|
锁定老帖子 主题：这不是面试题，这是真事
精华帖 (0) :: 良好帖 (1) :: 新手帖 (1) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2013-07-26
Trie树(字典树)，如果用Trie树来存你“第二行的整数”应该不要多少内存。
|
| 返回顶楼 | |
|
发表时间：2013-07-26
1.对文件每次读100,000行.对其中第二列的数据读出来进行根据10取模其实就是根据尾数分成10个文件存，存的时候可以开10个线程。读完两亿行数据。如果数据分布是比较平均的基本上每个文件会有大概两千行的数据。但是这个容量会比较小因为每条记录是15bytes * 2000 * 10000 = 300M
2.同时10线程分别对各个300M的数据进行读取处理。 |
| 返回顶楼 | |
|
发表时间：2013-07-26
两千万行 上面错了
|
| 返回顶楼 | |
|
发表时间：2013-07-26
先扫描一次文件，用一个hash表计数第二个字段，将计数>1的值输出。
然后将这些值存储在一个set中，然后再扫描一次文件，第二个字段在set中的输出行。。 原则： 文件很大，不能用排序。 2亿行的文件，我的经验用不了多长时间，半个小时顶天了。 如果你的文件在hadoop平台的话，写个sql，真的是分分钟的事情。 |
| 返回顶楼 | |
|
发表时间：2013-07-26
awk -F "\t" '{print $2| "sort -n | uniq -d" }' FILE
|
| 返回顶楼 | |
|
发表时间：2013-07-27
最后修改：2013-07-27
果断shell
awk '{++num[$2]} END{ for(n in num){ if(num[n]>=2) print n,num[n] } }' file 看错题目，找出行的话应该是下面的脚本 
awk '{++num[$2];if(num[$2]>=2){print $0}}' file |
| 返回顶楼 | |
|
发表时间：2013-07-27
bruce.yuan 写道 果断shell
awk '{++num[$2]} END{ for(n in num){ if(num[n]>=2) print n,num[n] } }' file 看错题目，找出行的话应该是下面的脚本
awk '{++num[$2];if(num[$2]>=2){print $0}}' file 嗯，这个是正确的做法。pass through 解决 |
| 返回顶楼 | |
|
发表时间：2013-07-28
iceman1952 写道 我有一个文件，一共100列，每个列以 tab 分开，第二列是一个 15位 的整数（此列是乱序的）
文件行数在2亿行之内，文件很大，大约 50G 左右。现在要求我找出 满足这种条件的行：第二列的整数，在此文件中，出现过2次或2次以上 有啥好办法嘛？ 我现在这么搞的：将文件尽量分成小文件（保证同样的数字分到同一个小文件中），使得此文件可以整个load到内存中。然后对内存中的数据使用set看是否曾经重复出现过 根据最后一位的值（0, 1, ..., 9），分成10个child文件。如果某个child文件还大于512M（我JVM内存比512大一点点，可以load整个文件），在根据第二位再分割此child文件，得到 grandchild文件；如果grandchild文件还是大于512M，则根据第三位分割...... 缺点：太耗时，以至于不现实，要1个多小时 PS：我将 JVM 最大heap设为 1024M，然后，测试将Long加入到set中，发现，可以创建 1700W个Long对象（Integer对象也是这么多）。到production环境中，我估计heap可以设置到8G，但是，即使这样，也只有1.6亿的Long（或者Integer），所以，肯定还是不能够读入所有的 整数，然后使用set判断哪个曾经出现过2次或2次以上 各位，有好办法嘛？我只要知道哪些整数曾经出现过2次或2次以上即可（分不分文件、出现的确切次数 我都不在乎） 另外：不要建议分布式啥的，这个也用不起来，我这就是一个 standalone 的应用 这事儿没那么麻烦吧。第二列是15位的整数，一共2亿个，使用long型数组（或HashSet），大概占用1.6G内存，不要用Long型对象。如果第二列的整数有重复，还会节约些内存。 然后全局遍历50G的这个大文件，在这个数组（或者HashSet）里面去找就可以了。其实50G的文件还不算太大。 生产环境如果能提供8G内存，这个做起来没问题的，你用512M内存是不是太小气了些？ 其实还有个最傻X的办法：花上几千块钱，买64G或128G内存，把这个50G的文件扔进内存，然后……你懂的 
如果确实蛋疼没事儿干，还可以考虑多线程处理，速度肯定会更快的。 |
| 返回顶楼 | |
|
发表时间：2013-07-28
最后修改：2013-07-28
awk -F'\t' '{if(a[$2]++ >=2){print $2}}' test.txt >newfile.txt
50G大小预计30分钟 |
| 返回顶楼 | |
|
发表时间：2013-07-29
研究了一下大概描述下思路：
（1）位图：这个可能需要把用15位的数字作为下标，已经超过数组下标为整型的限制，就算没有这个限制（或找到其他实现方式），15整数的作为下标的数组，占用内存达到999999999999999l/(1024*1024*1024)=931322.5746154776(单位g)，这个太吓人了，前提还是java中有真正位图的实现，否则如果最小单位不是bit，是byte的话内存还要增加； （2）long[] lArr = new long[120000000];测试了一下最大heap设置1g时能存储大概120000000个基本类型long，如果到2g的内存应该就能存储超过2亿个long，剩余内存用来计算；包装类型使用的内存要大于基本类型，这和楼主的测试（可以创建 1700W个Long对象）差不多，这种情况是不是采用基本类型合理一点，注：不知道楼主的环境能否跨越java虚拟机内存限制（一般是达不到2g的），哪位能否告诉一下怎么突破这个限制； （3）方法2不行就只能拆分文件了，是不是要找到算法让数据尽可能均匀分布到子文件中呢？（对这个比较感兴趣，希望有经验的兄弟分享下拆分的策略） |
| 返回顶楼 | |
