论坛首页 Java企业应用论坛

这不是面试题,这是真事

浏览 38746 次
精华帖 (0) :: 良好帖 (1) :: 新手帖 (1) :: 隐藏帖 (0)
作者 正文
   发表时间:2013-07-29  
jahu 写道
iceman1952 写道
jahu 写道
,,先说问题,,
第一,需求不是很明确。

   我的建议;
           1,合理使用多线程,组织好线程之间工作协调问题。
           2,既然只需要获得重复,那么建议。使用最原始和直接,简单的技术。

你啥都没说?

能说什么?这么庞大的一个功能,牵扯到的技术和细节太多了,需要做的测试也太多了,
比如,是不是真的需要2g内存,,?
比如你查分文件的策略是什么?这个文件在读的时候是不是继续写数据,
比如,数据分布是不是很均匀等等。
多线程,你定义好了,,需要那些技术吗?那些线程读数据,那些线程处理数据,那些线程验证数据等等?,有没有想过怎么在多线程的情况下组织线程的使用了?
按照你的需求,你可以重写一个map,,既然你只要只要得到两个以上的,那么你可以定义两个个set,第一个是2个以上,第二个1个,,就行了,
需要你那么麻烦啊,先问题复杂化,从复杂中看出简单,就开始做,


你有点菜,思路很不清晰
0 请登录后投票
   发表时间:2013-07-30  
pudgy 写道
shell命令很高效的,50G分分钟的事,估计10分钟最多了。
内存也不是问题,最多4G就够了。


看到sort,我笑了
0 请登录后投票
   发表时间:2013-07-30  
chinaagan 写道
用线程池+同步队列,算法就是拆分文件。。。队列就是保存待处理的文件及其状态大小。。。有两类线程,一类是拆分文件(就是根据数字来分,比如可以分100个文件,根据数字字符串前两位,如果文件还是挺大,可以继续分,提取数字字符串并保存到文件),一类是获取大小合适并已经拆分好的文件,然后统计出现次数大于等于二的并保存结果(可以保存到文件,并在在结果集中标明文件名,方便以后整合)。。。最后,任务都处理完的时候,就可以把结果集整合到一个文件中。。。线程池可以控制拆分和整合的线程数量。



迷信多线程的典型,写程序都写呆了吧。你确定磁盘IO操作为主的程序,多线程会更快?你以为你的磁盘有几个磁头?
0 请登录后投票
   发表时间: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时是有限制的啊 ?我不设置heap大小,在我16G的开发机上,Runtime.getTotalMemory(),很多次就看到输出是 5G 啦,没看到啥限制啊

tear11 写道

(3)方法2不行就只能拆分文件了,是不是要找到算法让数据尽可能均匀分布到子文件中呢?(对这个比较感兴趣,希望有经验的兄弟分享下拆分的策略)

是的,平均分到文件中,这是个技术活。我的想法是直接对 希望的文件个数 取余数,这样能分开,但是,平均分布肯定没有任何保证



如果是拆分文件,这种情况下,均匀分布未必就一定效率更高。
0 请登录后投票
   发表时间: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,你计算过需要需要多少时间么?这还没计算你遍历大文件的时间。
0 请登录后投票
   发表时间:2013-07-30  
jackra 写道
我感觉:
两个问题必须解决。
1.内存内处理,必然内存崩溃;
2.文件方式处理,必然速度慢;

个人建议:
1:拆分小文件,要看数据的情况,尽量给相似(比如开头两个或三个数字相同的)数值分派到不同文件;
2:对小文件进行排序排重处理;
3:存储小文件时记录行号,这样就可以直接确定结果行;
4:拆分小文件时尽量减少读写次数,可以采用内存缓冲方式,比如存储1w条即写文件。



第4点,操作系统自己有io缓冲的
0 请登录后投票
   发表时间:2013-07-30  
anson2003 写道
请使用布隆算法


不可靠,运营商统计这个也许是用来计费的
0 请登录后投票
   发表时间: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时效率会更高一点
0 请登录后投票
   发表时间:2013-07-30  
hardPass 写道
jackra 写道
我感觉:
两个问题必须解决。
1.内存内处理,必然内存崩溃;
2.文件方式处理,必然速度慢;

个人建议:
1:拆分小文件,要看数据的情况,尽量给相似(比如开头两个或三个数字相同的)数值分派到不同文件;
2:对小文件进行排序排重处理;
3:存储小文件时记录行号,这样就可以直接确定结果行;
4:拆分小文件时尽量减少读写次数,可以采用内存缓冲方式,比如存储1w条即写文件。



第4点,操作系统自己有io缓冲的

个人感觉哈,似乎得用手工控制吧?
0 请登录后投票
   发表时间: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”,你自己信么?请给出具体的测试代码

0 请登录后投票
论坛首页 Java企业应用版

跳转论坛:
Global site tag (gtag.js) - Google Analytics