|
锁定老帖子 主题：这不是面试题，这是真事
精华帖 (0) :: 良好帖 (1) :: 新手帖 (1) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2013-07-31
哎呀 这么复杂真心看不懂啊
不过好像就是一个外排序嘛 ，多路并归排序 然后扫相同的记录记ok了 实现就不用说了吧。 外排序 不过自己从头写的话费点事也不麻烦吧 找找有没有现在代码？ 分割的话 用shell 就ok 了嘛 |
| 返回顶楼 | |
|
发表时间：2013-07-31
iceman1952 写道 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-31
我有一个可靠办法，但效率不一定高。先按行拆分下文件，每份分多大呢?其实只要放得下n个15位的整数(long 8字节就放得下了)。以4G内存为例,4*1024*1024*1024/8=536870912.就是说4g内存基本上放得下0.5G左右的大小的数组，能放下数组就好办了，我可以排序了。我们一共就2G行数据，我将文件分4次就可以了。有人会说分文件内存要多少，我肯定的说很小，因为分文件是io读取你硬盘数据，只需要考虑缓存大小，缓存设置8k足够。按4次或者根据情况还可以更多次，分完文件后。然后对每一份重新排序后写入文件。剩下的事就是找出重复数据，我想在分组排序时每个组内的重复数据这个肯定是去掉了的。那就组间重复怎么办?其实也不麻烦了，第一组开始找拿数据，再其它组里面使用2分法直接去挑重复的就ok了。而且效率不会低的，因为是二分查找了。me没有玩过什么高深的算法，自己猜测了一把。如果有什么问题欢迎指出！
|
| 返回顶楼 | |
|
发表时间：2013-07-31
碉堡了，从lz的需求里，从什么地方看出需要排序？
|
| 返回顶楼 | |
|
发表时间：2013-07-31
我知道java 有个框架 mahout ， 你可以看看对你的问题有没有帮助。
|
| 返回顶楼 | |
|
发表时间：2013-07-31
其实这就是一个排序的问题，最优化的排序时间复杂度为n*log(n). 楼主的数据量为 2亿。
也就是需要进行 20亿次的比较。 比较的过程可以使用文件保存临时结果。20亿次比较的时间应该可以接受。 |
| 返回顶楼 | |
|
发表时间：2013-08-01
gosure 写道 其实这就是一个排序的问题，最优化的排序时间复杂度为n*log(n). 楼主的数据量为 2亿。
也就是需要进行 20亿次的比较。 比较的过程可以使用文件保存临时结果。20亿次比较的时间应该可以接受。 这样的玩笑一点也不好笑。 |
| 返回顶楼 | |
|
发表时间：2013-08-01
看不下去了，太扯了。
看看这个 http://www.cnblogs.com/bigrabbit/archive/2012/08/26/2657495.html 哪些想着多线程的，要好好学习下操作系统，什么时候多线程才会效率高。 |
| 返回顶楼 | |
|
发表时间：2013-08-01
whiletrue 写道 看不下去了，太扯了。
看看这个 http://www.cnblogs.com/bigrabbit/archive/2012/08/26/2657495.html 哪些想着多线程的，要好好学习下操作系统，什么时候多线程才会效率高。 15位的数，从0到999999999999999，但是只有两亿条数据，请问你这个bit的Set是两亿位呢？还是1000000000000000位呢？ |
| 返回顶楼 | |
|
发表时间：2013-08-01
iceman1952 写道 nicholasun 写道 iceman1952 写道 另外：不要建议分布式啥的，这个也用不起来，我这就是一个 standalone 的应用 什么逻辑？如果以后文件变成1000G 你也说我这只是一个standalone应用 你找其他人吧。。。 呃呃呃，需求就是“将一个大文件录入到 database”，就为了这个，我要搞个分布式，你觉得这个逻辑更讲得通？ PS：只有一个大文件，而且只有一张数据库表格。事实上，用oracle的external table应该也是挺好的，但是，由于需要对每个行进行 validate，所以，external table就被枪毙了 嗯，有些大文件的问题的确可以用些技巧（编程珠肌里有很多类似的题目）在单机上解决掉，但我觉得还是需要考虑水平扩展性的（如果文件越来越大并且越来越多，单机处理起来不效率） 楼主的场景可能不需要考虑吧 |
| 返回顶楼 | |
