Java功底篇系列-02-如何了解實際開發中與“排序”相關的問題

場景一：找出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，如需轉載請自行聯系原作者