Java功底篇系列-02-如何理解实际开发中与“排序”相关的问题

  1. 云栖社区>
  2. 博客>
  3. 正文

Java功底篇系列-02-如何理解实际开发中与“排序”相关的问题

科技小先锋 2017-11-14 23:13:00 浏览955
展开阅读全文

场景一:找出100W数据中TOP10


很自然的想法是排序,可是要知道对100W数据进行排序,不论采用什么样的排序算法吧,最坏情况下,应该是100W*100W的计算量,太大了。


可是,不排序又能怎么做呢?为什么要排序呢?我们仅仅需要的是TOP10。


思考下,找出100W数据中TOP1,你会排序吗?


找TOP1,相信大家和我一样,都不会去排序,应该是搞一个变量max认为它最大,然后遍历一边100W数据,在遍历过程中进行比较替换max就可以了找到TOP1。


依此规律,我们为什么不搞一组变量max1,max2,max3,max4...max10,然后去遍历一边100W数据,在遍历过程中对这一组变量进行替换呢?



场景二:有1000个整数数据,分布在[0-999]中,无序且重复,如何排序?


涉及到这些排序问题,特别是带有一定业务实际背景的,我感觉都不应该想什么“冒泡”,“快排”什么的。那为什么往往排序会第一时间想到它们呢?是因为我们懒,不想深入分析,只想用现成的,拿来就用!而实际上,这些都是带有一定的技巧性的!


创建一个数组array,大小1000,也就是array[0],array[1],...,array[999],如果数组元素的值,是索引出现的次数,那么不就完成排序了吗?


没想到一个数组,竟然完成了排序功能!简直不可思议!


要知道,数组的特性,她的index是正数,而且就是天然有序的啊!


然后,我们利用压缩节省空间的想法,用array[index]代表index出现的次数,问题就完美解决了。



场景三:有一个20W行文件,里面每一行存放着这样的信息:商品ID:商品分数,我们可以将其读入内存形成一个MAP1 ;在内存有这样一个MAP2 KEY代表用户,VALUE是这个用户需要过滤的商品信息  商品ID1,商品ID2,商品ID3,...。现在要求出每个用户,过滤后商品的TOP3。


一个很自然的想法是:

比如对MAP2进行遍历,然后在里面对MAP1进行遍历过滤,然后对过滤后的MAP1进行按照VALUE排序,这样就可以得到了。


可是问题是,如果我们的用户如果很多,要知道京东/淘宝的用户都是亿级别的。那么就是N亿*20W的遍历次数了,这还不算每次遍历还要排序取TOP3。


那么如何节省遍历次数呢?


利用公共缓存 + 减法思想!


可以对MAP1先进行一次排序,然后对MAP2进行遍历,在MAP2遍历过程中,我们只需要对MAP1的头部看一下,如果存在需要过滤的商品,我们就做下减法,而不需要真正的对MAP1进行遍历了。这说明,在实际中,如果我们预先做好公共的缓存,然后再去根据不同的要求做减法,将会提高效率!



场景四:有200W数据,他们相对均匀的分布在[1-200W],如何快速排序呢?


基于分布式处理:

分块  + 多线程处理的思想


既然数据相对均匀分布,那么就划分区间,如[1,1000],[1001,2000],...。


首先,我们对数据来一次遍历,目的是为了让他们各自找到自己的区间。


区间划分完毕后,由于区间与区间之间是有序的,所以我们只需要完成各个区间内部的排序即可。


最坏的情况下,每个区间全排序需要1000*1000,再加上上面的遍历一次200W,也就是需要1000*1000+200W=300W,这比200W*200W=4万亿  小多了!


而且,还可以进一步利用多线程进行处理,因为区间之间是完全隔离的,不存在相互影响,各自排序不需要加锁。因此我们完全可以利用多线程并发排序,节省时间!


原来这就是分布式计算的基本原理!



本文转自zfz_linux_boy 51CTO博客,原文链接:http://blog.51cto.com/zhangfengzhe/1684909,如需转载请自行联系原作者

网友评论

登录后评论
0/500
评论
科技小先锋
+ 关注