锁定老帖子 主题:这不是面试题,这是真事
精华帖 (0) :: 良好帖 (1) :: 新手帖 (1) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2013-07-29
jahu 写道 iceman1952 写道 jahu 写道 ,,先说问题,,
第一,需求不是很明确。 我的建议; 1,合理使用多线程,组织好线程之间工作协调问题。 2,既然只需要获得重复,那么建议。使用最原始和直接,简单的技术。 你啥都没说? 能说什么?这么庞大的一个功能,牵扯到的技术和细节太多了,需要做的测试也太多了, 比如,是不是真的需要2g内存,,? 比如你查分文件的策略是什么?这个文件在读的时候是不是继续写数据, 比如,数据分布是不是很均匀等等。 多线程,你定义好了,,需要那些技术吗?那些线程读数据,那些线程处理数据,那些线程验证数据等等?,有没有想过怎么在多线程的情况下组织线程的使用了? 按照你的需求,你可以重写一个map,,既然你只要只要得到两个以上的,那么你可以定义两个个set,第一个是2个以上,第二个1个,,就行了, 需要你那么麻烦啊,先问题复杂化,从复杂中看出简单,就开始做, 你有点菜,思路很不清晰 |
|
返回顶楼 | |
发表时间:2013-07-30
pudgy 写道 shell命令很高效的,50G分分钟的事,估计10分钟最多了。
内存也不是问题,最多4G就够了。 看到sort,我笑了 |
|
返回顶楼 | |
发表时间:2013-07-30
chinaagan 写道 用线程池+同步队列,算法就是拆分文件。。。队列就是保存待处理的文件及其状态大小。。。有两类线程,一类是拆分文件(就是根据数字来分,比如可以分100个文件,根据数字字符串前两位,如果文件还是挺大,可以继续分,提取数字字符串并保存到文件),一类是获取大小合适并已经拆分好的文件,然后统计出现次数大于等于二的并保存结果(可以保存到文件,并在在结果集中标明文件名,方便以后整合)。。。最后,任务都处理完的时候,就可以把结果集整合到一个文件中。。。线程池可以控制拆分和整合的线程数量。
迷信多线程的典型,写程序都写呆了吧。你确定磁盘IO操作为主的程序,多线程会更快?你以为你的磁盘有几个磁头? |
|
返回顶楼 | |
发表时间:2013-07-30
iceman1952 写道 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时是有限制的啊 ![]() tear11 写道 (3)方法2不行就只能拆分文件了,是不是要找到算法让数据尽可能均匀分布到子文件中呢?(对这个比较感兴趣,希望有经验的兄弟分享下拆分的策略) 是的,平均分到文件中,这是个技术活。我的想法是直接对 希望的文件个数 取余数,这样能分开,但是,平均分布肯定没有任何保证 如果是拆分文件,这种情况下,均匀分布未必就一定效率更高。 |
|
返回顶楼 | |
发表时间:2013-07-30
yanyilin224 写道 既然第二列存的是个整数,也不会出现极端情况(比如同一个数字出现Interger.Max_Value次),那么不用分文件,不依赖第三档库,用java.io就能搞定,对内存要求很低,只需要一个2.2G左右的临时文件。
大致算法: 1.创建临时文件 2.读取要解析的文件,每次读一行数据,读到第二列的整数n 3.利用RandomAccessFile读取临时文件的第n个byte(file.seek(n);file.read(byte[1]);) 4.如果读不到数据,或读到的是0,那么向这个位上写入一个1 5.如果读到的是大于0的数字,那么把该数字+1之后再回文件这个byte上(按楼主的要求,如果大于2的话不再写入也正确,因为用于计数的只有一个byte,记录不了太多重复) 6.读取完成后,遍历一次临时文件,如果读到第x位的值大于2,说明整数x出现过超过两次或以上 能不纸上谈兵不? 不知道你这个2.2G是怎么计算出来的? seek?磁盘寻道时间大概是10ms,2亿行 * 10ms,你计算过需要需要多少时间么?这还没计算你遍历大文件的时间。 |
|
返回顶楼 | |
发表时间:2013-07-30
jackra 写道 我感觉:
两个问题必须解决。 1.内存内处理,必然内存崩溃; 2.文件方式处理,必然速度慢; 个人建议: 1:拆分小文件,要看数据的情况,尽量给相似(比如开头两个或三个数字相同的)数值分派到不同文件; 2:对小文件进行排序排重处理; 3:存储小文件时记录行号,这样就可以直接确定结果行; 4:拆分小文件时尽量减少读写次数,可以采用内存缓冲方式,比如存储1w条即写文件。 第4点,操作系统自己有io缓冲的 |
|
返回顶楼 | |
发表时间:2013-07-30
anson2003 写道 请使用布隆算法
不可靠,运营商统计这个也许是用来计费的 |
|
返回顶楼 | |
发表时间:2013-07-30
最后修改:2013-07-30
hardPass 写道 yanyilin224 写道 既然第二列存的是个整数,也不会出现极端情况(比如同一个数字出现Interger.Max_Value次),那么不用分文件,不依赖第三档库,用java.io就能搞定,对内存要求很低,只需要一个2.2G左右的临时文件。
大致算法: 1.创建临时文件 2.读取要解析的文件,每次读一行数据,读到第二列的整数n 3.利用RandomAccessFile读取临时文件的第n个byte(file.seek(n);file.read(byte[1]);) 4.如果读不到数据,或读到的是0,那么向这个位上写入一个1 5.如果读到的是大于0的数字,那么把该数字+1之后再回文件这个byte上(按楼主的要求,如果大于2的话不再写入也正确,因为用于计数的只有一个byte,记录不了太多重复) 6.读取完成后,遍历一次临时文件,如果读到第x位的值大于2,说明整数x出现过超过两次或以上 能不纸上谈兵不? 不知道你这个2.2G是怎么计算出来的? seek?磁盘寻道时间大概是10ms,2亿行 * 10ms,你计算过需要需要多少时间么?这还没计算你遍历大文件的时间。 不知道你有没有看懂,如果看懂了的话2.2G是很自然就能计算出来的,临时文件最多Intger.MAX_VALUE个byte,当然是接近2.2G左右,具体数字没有细算。 至于你说seek寻道时间,刚测试了一下,10万次随机seek+写byte平均耗时3ms,确实有点慢;在这里可以做一些优化,在内存中先缓存一部分结果,再将结果按位置排序后再写入文件中,这样seek时效率会更高一点 |
|
返回顶楼 | |
发表时间:2013-07-30
hardPass 写道 jackra 写道 我感觉:
两个问题必须解决。 1.内存内处理,必然内存崩溃; 2.文件方式处理,必然速度慢; 个人建议: 1:拆分小文件,要看数据的情况,尽量给相似(比如开头两个或三个数字相同的)数值分派到不同文件; 2:对小文件进行排序排重处理; 3:存储小文件时记录行号,这样就可以直接确定结果行; 4:拆分小文件时尽量减少读写次数,可以采用内存缓冲方式,比如存储1w条即写文件。 第4点,操作系统自己有io缓冲的 个人感觉哈,似乎得用手工控制吧? |
|
返回顶楼 | |
发表时间:2013-07-30
yanyilin224 写道 hardPass 写道 yanyilin224 写道 既然第二列存的是个整数,也不会出现极端情况(比如同一个数字出现Interger.Max_Value次),那么不用分文件,不依赖第三档库,用java.io就能搞定,对内存要求很低,只需要一个2.2G左右的临时文件。
大致算法: 1.创建临时文件 2.读取要解析的文件,每次读一行数据,读到第二列的整数n 3.利用RandomAccessFile读取临时文件的第n个byte(file.seek(n);file.read(byte[1]);) 4.如果读不到数据,或读到的是0,那么向这个位上写入一个1 5.如果读到的是大于0的数字,那么把该数字+1之后再回文件这个byte上(按楼主的要求,如果大于2的话不再写入也正确,因为用于计数的只有一个byte,记录不了太多重复) 6.读取完成后,遍历一次临时文件,如果读到第x位的值大于2,说明整数x出现过超过两次或以上 能不纸上谈兵不? 不知道你这个2.2G是怎么计算出来的? seek?磁盘寻道时间大概是10ms,2亿行 * 10ms,你计算过需要需要多少时间么?这还没计算你遍历大文件的时间。 不知道你有没有看懂,如果看懂了的话2.2G是很自然就能计算出来的,临时文件最多Intger.MAX_VALUE个byte,当然是接近2.2G左右,具体数字没有细算。 至于你说seek寻道时间,刚测试了一下,100万次随机位置的seek,平均耗时314.3ns,平均3000次seek才1ms,也不算太慢吧? 你所谓的“2.2G是很自然就能计算出来的”,我看不懂,请给出公式。 还有你所谓的“平均耗时314.3ns”,你自己信么?请给出具体的测试代码 |
|
返回顶楼 | |