|
锁定老帖子 主题：这不是面试题，这是真事
精华帖 (0) :: 良好帖 (1) :: 新手帖 (1) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2013-07-30
hardPass 写道 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”，你自己信么？请给出具体的测试代码 314ns已经改了，是测试代码的问题，每次seek+write接近3ms。 2.2G是直接把Interger.MAX_VALUE(byte)换算成G就OK |
| 返回顶楼 | |
|
发表时间：2013-07-30
yanyilin224 写道 hardPass 写道 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”，你自己信么？请给出具体的测试代码 314ns已经改了，是测试代码的问题，每次seek+write接近3ms。 2.2G是直接把Interger.MAX_VALUE(byte)换算成G就OK 3ms也值得怀疑，除非你做了raid，或者你的硬盘配置确实好，不过数量级上差不多了。 你这个Interger.MAX_VALUE有很大的问题啊。 你要是以2亿（行数）计算实际大小，或者用1e16-1(15位数字所表示的最大数字)计算稀疏文件的表面大小，都可以说是成立的，但是Interger.MAX_VALU么，逻辑不清。 |
| 返回顶楼 | |
|
发表时间：2013-07-30
最后修改：2013-07-30
hardPass 写道 yanyilin224 写道 hardPass 写道 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”，你自己信么？请给出具体的测试代码 314ns已经改了，是测试代码的问题，每次seek+write接近3ms。 2.2G是直接把Interger.MAX_VALUE(byte)换算成G就OK 3ms也值得怀疑，除非你做了raid，或者你的硬盘配置确实好，不过数量级上差不多了。 你这个Interger.MAX_VALUE有很大的问题啊。 你要是以2亿（行数）计算实际大小，或者用1e16-1(15位数字所表示的最大数字)计算稀疏文件的表面大小，都可以说是成立的，但是Interger.MAX_VALU么，逻辑不清。 
看懂算法就知道，逻辑简单得很，看图吧 |
| 返回顶楼 | |
|
发表时间：2013-07-30
iceman1952 写道 另外：不要建议分布式啥的，这个也用不起来，我这就是一个 standalone 的应用 什么逻辑？如果以后文件变成1000G 你也说我这只是一个standalone应用 你找其他人吧。。。 |
| 返回顶楼 | |
|
发表时间：2013-07-30
http://www.dbafree.net/?p=36
布隆过滤器，提供一个别人写的例子。 |
| 返回顶楼 | |
|
发表时间：2013-07-30
hardPass 写道 chinaagan 写道 用线程池+同步队列，算法就是拆分文件。。。队列就是保存待处理的文件及其状态大小。。。有两类线程，一类是拆分文件（就是根据数字来分，比如可以分100个文件，根据数字字符串前两位，如果文件还是挺大，可以继续分，提取数字字符串并保存到文件），一类是获取大小合适并已经拆分好的文件，然后统计出现次数大于等于二的并保存结果（可以保存到文件，并在在结果集中标明文件名，方便以后整合）。。。最后，任务都处理完的时候，就可以把结果集整合到一个文件中。。。线程池可以控制拆分和整合的线程数量。
迷信多线程的典型，写程序都写呆了吧。你确定磁盘IO操作为主的程序，多线程会更快？你以为你的磁盘有几个磁头？ 现在磁盘IO慢吗？楼主这情形限制的是内存大小。。。这里明显可以用到多线程。。。当拆分好文件大小之后（比如每个文件50M左右），可以统计每个文件的重复数据（通过hashmap），各不相干，这里不用多线程用什么？ |
| 返回顶楼 | |
|
发表时间：2013-07-30
chinaagan 写道 hardPass 写道 chinaagan 写道 用线程池+同步队列，算法就是拆分文件。。。队列就是保存待处理的文件及其状态大小。。。有两类线程，一类是拆分文件（就是根据数字来分，比如可以分100个文件，根据数字字符串前两位，如果文件还是挺大，可以继续分，提取数字字符串并保存到文件），一类是获取大小合适并已经拆分好的文件，然后统计出现次数大于等于二的并保存结果（可以保存到文件，并在在结果集中标明文件名，方便以后整合）。。。最后，任务都处理完的时候，就可以把结果集整合到一个文件中。。。线程池可以控制拆分和整合的线程数量。
迷信多线程的典型，写程序都写呆了吧。你确定磁盘IO操作为主的程序，多线程会更快？你以为你的磁盘有几个磁头？ 现在磁盘IO慢吗？楼主这情形限制的是内存大小。。。这里明显可以用到多线程。。。当拆分好文件大小之后（比如每个文件50M左右），可以统计每个文件的重复数据（通过hashmap），各不相干，这里不用多线程用什么？ 晕了，啥时候磁盘IO不慢了？ |
| 返回顶楼 | |
|
发表时间：2013-07-30
shell直接弄就可以 如果要编程 参考shell的思想 只将第二列的数据放入缓存中或者一个临时文件当中 然后排序 然后再排查。
|
| 返回顶楼 | |
|
发表时间：2013-07-30
teasp 写道 iceman1952 写道 teasp 写道 楼主，一个Integer占多少字节？何苦为了省long的4个字节而用hashmap呢，我觉得long数组是合理的。
Integer远比你想象的多（16字节）http://www.ibm.com/developerworks/cn/java/j-codetoheap/ 所以我才提醒你没必要用Hashmap呀。 很多数字的前面 6 位是一样的，对于每一个这种数字，让它们共用一个 Integer的key，然后，每个数字的后面9位就可以用int（而不是long）来存储了 很明显这是在节省内存，有啥不对嘛？ |
| 返回顶楼 | |
|
发表时间：2013-07-30
nicholasun 写道 iceman1952 写道 另外：不要建议分布式啥的，这个也用不起来，我这就是一个 standalone 的应用 什么逻辑？如果以后文件变成1000G 你也说我这只是一个standalone应用 你找其他人吧。。。 呃呃呃，需求就是“将一个大文件录入到 database”，就为了这个，我要搞个分布式，你觉得这个逻辑更讲得通？ PS：只有一个大文件，而且只有一张数据库表格。事实上，用oracle的external table应该也是挺好的，但是，由于需要对每个行进行 validate，所以，external table就被枪毙了 |
| 返回顶楼 | |
