|
锁定老帖子 主题：这不是面试题，这是真事
精华帖 (0) :: 良好帖 (1) :: 新手帖 (1) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2013-07-29
用hadoop，这个问题在里面本身就是一个案例
|
| 返回顶楼 | |
|
发表时间：2013-07-29
仍数据库里吧，删掉只出现一次的
|
| 返回顶楼 | |
|
发表时间：2013-07-29
最后修改：2013-07-29
pittlu 写道 iceman1952 写道 aochant 写道 分文件这么分
将第二列的整数 算出hashcode然后取摸，将这个结果一致的分到同一个文件中 这样保证了 第二列值一样的一定分在同一个文件 然后就很简单了 比如要分为20个小文件 “123123123”.hashCode()&0x7FFFFFFF%20 都不用这么麻烦的，每个整数对 20 求余 就OK啦。但是，其实我没必要这么搞的，就像我红色标注的那样，只要得到“那个整数出现过2次以上”我就足以。无用功作的越少越好 这个思路就很好了，不过可以做以下改进（其实这个方案已经很简单了，毕竟是50G的文件，不知道还要多简单  ）：
1、直接内存映射文件读取整个大文件进行取模运算。 2、结果也不用重新写到新文件中，写文件是最耗时的，直接在内存里计算就可以了。 3、分多趟扫描文件取模，比如第一趟处理模数为1的整数，第二趟处理模数为2的整数。 内存映射后，多趟扫描文件？每次都要read啊，难道这样会快  。或者，我需要试试 ？
|
| 返回顶楼 | |
|
发表时间：2013-07-29
jahu 写道 ，，先说问题，，
第一，需求不是很明确。 我的建议; 1,合理使用多线程，组织好线程之间工作协调问题。 2,既然只需要获得重复，那么建议。使用最原始和直接，简单的技术。 你啥都没说？ |
| 返回顶楼 | |
|
发表时间：2013-07-29
使用位图法判断整形数组是否存在重复
判断集合中存在重复是常见编程任务之一，当集合中数据量比较大时我们通常希望少进行几次扫描，这时双重循环法就不可取了。 位图法比较适合于这种情况，它的做法是按照集合中最大元素max创建一个长度为max+1的新数组，然后再次扫描原数组，遇到几就给新数组的第几位置上1，如遇到5就给新数组的第六个元素置1，这样下次再遇到5想置位时发现新数组的第六个元素已经是1了，这说明这次的数据肯定和以前的数据存在着重复。这种给新数组初始化时置零其后置一的做法类似于位图的处理方法故称位图法。它的运算次数最坏的情况为2N。如果已知数组的最大值即能事先给新数组定长的话效率还能提高一倍。 15位太长，就二维数组吧 |
| 返回顶楼 | |
|
发表时间：2013-07-29
最后修改：2013-07-29
whiletrue 写道 shell没试过，hehuabing的方式肯定是可行的，这个是最方便的办法了，效率也非常高，相信可以超过shell。
看看编程珠玑吧 hehuabing 写道 试试用位图数据结构试试呢 好多建议用位图的兄弟，不过，这个要怎么用 要知道是15位的整数，最大是：999百万亿。（4G内存的bit是只有320亿，算算百万亿得多少内存了） |
| 返回顶楼 | |
|
发表时间：2013-07-29
最后修改：2013-07-29
liuzhiqiangruc 写道 先扫描一次文件，用一个hash表计数第二个字段，将计数>1的值输出。
然后将这些值存储在一个set中，然后再扫描一次文件，第二个字段在set中的输出行。。 原则： 文件很大，不能用排序。 2亿行的文件，我的经验用不了多长时间，半个小时顶天了。 如果你的文件在hadoop平台的话，写个sql，真的是分分钟的事情。 -Xmx1024M，写个简单的程序测试了下， ArrayList只能持有 2.57千万个Long（事实上，真正可以持有的肯定应该是这个2倍，因为每次空间不足时，System.arraycopy会占用几乎同样大小的空间，OutOfMemory时，肯定是在 System.arraycopy时），HashSet比这还少（测试过程老报错误）。Long占用的内存要远远多于 long（Integer/int，Short/short，Byte/byte都是同样的情况） 另外：同样情况下，如果开一个大大是数组，结果是这样的 long[] 89 million， int[] 178 million， byte[] 715 million |
| 返回顶楼 | |
|
发表时间：2013-07-29
最后修改：2013-07-29
tear11 写道 研究了一下大概描述下思路：
（1）位图：这个可能需要把用15位的数字作为下标，已经超过数组下标为整型的限制，就算没有这个限制（或找到其他实现方式），15整数的作为下标的数组，占用内存达到999999999999999l/(1024*1024*1024)=931322.5746154776(单位g)，这个太吓人了，前提还是java中有真正位图的实现，否则如果最小单位不是bit，是byte的话内存还要增加； Exactly，所以，说用位图其实是不现实的 tear11 写道 （2）long[] lArr = new long[120000000];测试了一下最大heap设置1g时能存储大概120000000个基本类型long，如果到2g的内存应该就能存储超过2亿个long，剩余内存用来计算；包装类型使用的内存要大于基本类型，这和楼主的测试（可以创建 1700W个Long对象）差不多，这种情况是不是采用基本类型合理一点，注：不知道楼主的环境能否跨越java虚拟机内存限制（一般是达不到2g的），哪位能否告诉一下怎么突破这个限制； JVM设置heap时是有限制的啊 ？我不设置heap大小，在我16G的开发机上，Runtime.getTotalMemory()，很多次就看到输出是 5G 啦，没看到啥限制啊
tear11 写道 （3）方法2不行就只能拆分文件了，是不是要找到算法让数据尽可能均匀分布到子文件中呢？（对这个比较感兴趣，希望有经验的兄弟分享下拆分的策略） 是的，平均分到文件中，这是个技术活。我的想法是直接对 希望的文件个数 取余数，这样能分开，但是，平均分布肯定没有任何保证 |
| 返回顶楼 | |
|
发表时间：2013-07-29
搞个15层的DFA状态机，然后把文件切割成小文件用线程扫描即可
|
| 返回顶楼 | |
|
发表时间：2013-07-29
evanzzy 写道 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的文件扔进内存，然后……你懂的
如果确实蛋疼没事儿干，还可以考虑多线程处理，速度肯定会更快的。 大大的long[]数组是可以的。考虑到很多数字前面部分可能一样（我在原帖中没提这点  ），我用int来存的。感觉这是最简单的方法了，效果也还不错：
搞个HashMap key：Integer，用数字的前面6位 value：int[]，每个元素是 数字的后面9位（不超过10亿，所以，int可以表达） 如果value的int[]数组比较长，基本上每个15位的数字，可以节省4个字节（不考虑HashMap的key所在的内存，int[]数组本身所占的内存） 
|
| 返回顶楼 | |
