637
《Java特種兵》1.2 一些簡單算法，你會如何理解
1.2 一些簡單算法你會如何理解
終於迎來第二次聚會的機會本節內容會輕鬆許多也許一盞茶的工夫就可以聽完這個小故事。
注其實本節並不是討論算法例子也會很簡單如果你對算法很熟悉請跳過此節。
想要從一堆數據中找出一個max、min。
想要從100萬個數字中找出最大的10個數字。
你的想法是什麼你會如何找先排序再找或者摸不到頭腦。
胖哥的一些方法也許會幫到你“想想學校裏麵排隊、找人是怎麼做的”。
假如一個學校有幾千人你要找一個人胖哥給你提供幾種方法你選哪一種
◎ 方法1幾千個人我逐個去問你是不是我要找的人如果回答是那麼就是我要找的如果不是則繼續問下一個。
◎ 方法2我知道學生的年級然後在年級中每個班級按照方法1繼續做同樣的事情。
◎ 方法3我知道具體的班級然後在班級裏麵像“方法1”一樣逐個問。
◎ 方法4我知道姓名通過姓名得到有幾個班級同名的人這幾個人我逐個問。
◎ 方法5我知道班級和姓名也許就1個或2個學生同名然後逐個問。
◎ 方法6我知道“學號”直接找到人。
上麵6種方法屬於思維上的方法學在不同的場景下使用不同的手段但你會毫不猶豫地說第1種方法肯定是最傻的方法。沒錯但是我們的程序往往就是這樣寫的一個長長的for循環加匹配就是逐個問的道理對於人數不多的情況它其實也是實用的但人數多了自然會有問題。後麵幾種方法都是知道某些前提內容後然後通過不同的索引手段找到了人。好了下麵我們回到正題探討幾種計算方法的場景。
1.2.1 從一堆數據中找max和min
在一堆數據中找到一個最大的數據如果它是無序的就不存在“班級、年級”的維度概念也就是說沒有數據分組的概念在這種場景下不得不去做一次數組遍曆和學校的學生不按照班級站隊的道理一樣。但是需要做一次排序嗎當然不需要因為我們隻要找出最大值和最小值就可以了排序的代價太大了。如果要求最大值則可以先給一個臨時變量賦值為Integer.MIN_VALUE或數組中的第1個元素值然後循環數組的每個下標隻要比當前的這個值大就給它賦予最新的值。這個時間複雜度是循環一次就可以搞定的自然就不需要排序那麼大的時間複雜度了。而排序會是什麼樣的呢
在學校排隊的時候學生有自己的主見每人都有大腦CPU當“校長”號令者下達命令後每個學生自己知道去找位置可以將自己的大致位置找好細節的可以再由班主任來排序但計算機中的CPU是有限的不能這樣幹這種方式的時間複雜度減少不了因此排序的代價是巨大的除非有一天計算機的內存不通過CPU或很少通過CPU就可以自己排序。
寓意“所有的算法來自生活而且沒有生活那麼複雜。”
進一步來看這個問題100個人進行羽毛球比賽最終需要挑選出水平最高的那一個人最少會比賽99場。用這種方式就像擂台比武一樣倒下的人下台勝利者繼續在台上在實際生活中水平高的可能會累死但在計算機中不會。
比賽的次數99次是最少的有沒有其他的方法呢或許可以讓兩兩之間進行較量高手再兩兩之間繼續較量最後決出勝負但是比賽的次數我們發現還是N-1次例如8個人首先4場勝出4人然後2場勝出2人最後1場加起來就是7場。這種方式有一個重要的特征——在兩兩比賽的時候隻要有足夠多的場地就可以一起比賽那麼總體時間就節約下來了在計算機中就是“多線程”技術。前者的設計方法由於簡單無法實現這種並行但是它足夠簡單隻要for循環裏麵需要處理的內容足夠簡單效率依然是很高的。
寓意即使是多線程技術在生活中也能找到活生生的例子。
將這個問題再做一點“發散性”擴展在一堆雜亂無章的數據中需要求出某個數據從大到小的“排名”情況你會將所有的數據全部重排序一次嗎當然不會因為完全重排序通常是n2的時間複雜度。
不過聰明的同學會給自己找一個理由完全重排序後的數據是可以反複使用的如果排序導致時間開銷過多則可以定時做完全排序外部的請求直接從排序結果中獲取即可。這樣我們需要忍受數據上的一點小延遲因為這個排名可能隨時在變化由於是定時排序所以變化後的數據並不會立即更新到排序後的結果中或許在沒有麵臨大數據的時候換個思路會更快捷——在很多時候隻要數據量不是特別大隻需要找出比這個數據大的數據個數就自然知道排名了。這種思維其實是相通的將上麵的思路放在這裏使用就是一種“變通”。
1.2.2 從100萬個數字中找最大的10個數字
通過1.2.1節的介紹胖哥認為你應該可以領悟到一些什麼——既然在尋找最大數字的時候是保留一個最大值那麼在尋找10個最大數字的時候就可以記錄10個數字的最小值或者將這10個數字排序也是很輕鬆的。
循環大數組的每個元素如果當前數字大於這10個數字的最小值就剔除最小值將當前數字寫進去。如果10個數字是有序的那麼可以快速定位數字要寫入的位置如果是無序的則隻需要重新找出最小值即可。如果數字比較隨機那麼隨著不斷的疊加這個最小值也會越變越大這10個數字需要再次插入的概率就會變小很多即使是在最壞的情況下每個數字都要插入到10個數字中剔除最小的也最多是10´100萬的運算量而不會是100萬´100萬的運算量。
1.2.3 關於排序實際場景很重要
胖哥算法學得不太好在胖哥思維中的很多排序算法沒有什麼排序算法是特別好的或者在最壞的情況下它們都半斤八兩。在前麵的例子中一個學校要排隊每個學生都有自己的大腦CPU計算機要整體排序應如何排呢
實際的場景很重要這裏假如有“雜亂無章”的數據200萬個數據兩層for循環得到一個n2的複雜度200萬´200萬=4萬億。胖哥不想用我們開始分析業務場景。如果我們發現這些數據中有95%以上是相對均勻地分布在1200萬之間的而且重複數據極少那麼在這種場景下會如何排序還會用兩層for循環去排序嗎
胖哥的第一感覺就是它是有技巧的胖哥希望先分堆再排序。由於數據較為均勻所以將它們分成2002份甚至於更多其中2000份為1200萬之間每個堆都是一個連續的區間例如[1-1000]、[1001-2000]、[2001-3000]…自然每個區間的數據範圍是一個小堆而且小堆之間的數據是有序的“<1”的數據和“>200萬”的數據各自再分一個小堆2002個堆之間的數據是完全有序的因此隻要它們各自內部有序就是全局有序。這個過程需要掃描200萬數據一次然後在2002個堆中找到自己的位置由於它本身有序所以采用二分查找算法是可以快速找到位置的每次匹配範圍會縮小1倍在2002個範圍中尋找每個數字最壞匹配11次因為2的11次方是2048總體上11´100萬=1100萬。
此時平均每個堆大概是1000條數據200萬數據放在2002個堆中那麼每個堆自己排序的最壞時間複雜度將是1000´1000=100萬有2002個堆因此是100萬´2002=20.02億加上分堆的開銷是20.135億計算次數依然很高但是可以看到已經比1萬億這個數字降低了500倍。這就是根據業務場景來做邏輯優化的魅力讀者可以在這個基礎上繼續深度挖掘業務細節。
回顧是否覺得這也是生活中的一些場景——先排好班級每個班級之間就不用排序了而不是全校上千人一起來排隊它采用的是我們熟悉的分塊排序隻是唯一的區別是分塊排序完成後就不需要再進行板塊之間的排序了。這再次說明我們實踐中運用的還是“基礎的算法”在實際場景中需要變化“變化後的招數才是最有攻擊力的招數”。
內容擴展當拆分成多個塊以後板塊內部的排序是隔離的因此各個板塊是可以並行排序的而且無須加鎖如果麵對的是超大數據還可以利用多線程來降低處理時間。將這個問題細化就是分布式計算的基本原理了。
場景擴展其實排序還有很多實際場景遠遠不止這些而且有些的確是很複雜的算法不過無論多麼複雜總能在實際的生活中找到邏輯背景。在這種前提下隻要深度挖掘業務背景就可以在基礎算法之上進行靈活擴展。例如有很多個已經排序後的分塊塊內都是有序的從第1個塊到最後一個塊的特征是後一個塊的最小值大於前一個塊的最小值你會如何排序呢
由於算法不是本書的重點這裏胖哥就簡單說明一下。題目說明了每個塊內部是有序的且後一個塊的最小值大於前一個塊的最小值第一想法自然是用後一個塊的最小值找出前一個塊小於等於當前值的列表。由於本身是有序的所以這樣排序下來肯定是有序的且剩下的數據肯定比當前取出的數據要大。
但是有個問題剩下的數據就無法保證後一個塊的最小值大於前一個塊的最小值了但是我們覺得這樣“很爽”還想要這樣的情況繼續發生。
在取出第1個塊的數據後不論取出幾條數據記錄下現在的最小值並認為是所有的最小值。進一步下一個塊取完後得到最小值如果它仍然大於前一個塊的最小值就用鏈表方式寫在前一個塊的後麵若小於前一個塊的最小值就放在前一個塊的前麵。我們也可以用一個單獨的數組來存放每個塊當前的最小值這個長度與塊個數一致因此不會占用太多的空間數組本身是有序的相繼遞推的時候還可以用“二分查找算法快速定位”板塊的位置。這樣取完一次數據後就得到了一個新的鏈表或者在分配的數組中記錄了新的板塊順序。總之現在是一個嶄新的順序那麼在進一步取數的過程中我們又可以輕鬆完成了這也是一種分塊排序的特殊場景。
說了這麼多胖哥還是在講這句話實際場景千變萬化切不可死記硬背。
1.2.4 數據庫是怎麼找數據的
按照1.2.3節中的例子將一些數據劃分為板塊但是由於數據太多就會造成板塊太多或板塊內部的數據太多此時就會有管理板塊的板塊。數據庫通常承載的數據量都上億單表大小甚至十億以上它是怎麼做的呢
其實數據庫也離不開這些原理大多數數據庫的索引都會用換湯不換藥的“B+樹”當然也有使用Hash來做索引的此思想源自對平衡二叉樹的一種擴展而同時也來自基本算法——二分查找算法隻是在場景中也會有些變化數據庫中的分塊、索引、排序等概念在這些理論中體現得非常明顯。
例如SQL操作表與表之間的join的時候如果是已經排序好的兩個列表join就無須完全的兩層for循環來操作那是N´N的時間複雜度此時有點類似於1.2.3節中的擴展例子介紹如下。
假如A表與B表join到B表中查找A表的一個數據100它從B表最小的數據開始找找到了許多小於100的數據不過都排除在外不論是否找到100這個數據當去B表查找A表的下一個數據101的時候就不會再從最小值開始找了而是從100開始因為數據庫知道雙方是有序的。隨著這個規律的推移掃描的數據範圍會越來越小而不是像兩層for循環那樣每一個外部的for循環都需要在內存中從第1個下標開始掃描。
通常如果SQL沒有問題join表的個數往往不會太多我們可以進一步做簡單化優化。
1.2.5 Hash算法的形象概念
其實Hash有很多種有簡單Hash還有一致性Hash等這裏我們就談談簡單Hash算法。關於Hash算法經常會在教材中看到Hash桶快速定位先計算再定位並且號稱複雜度為O(1)。
胖哥有自己的看法這樣的概念容易讓人迷惑Hash到底是“神馬”東西而容易認為O(1)就是沒有時間開銷的Hash就是絕對定位的Hash算法就是無限快等思維都會出現。但實際場景也許並不是這樣的。
胖哥不想搞得那麼複雜胖哥認為Hash算法有點像圖1-5所示的那樣這裏給大家一個簡單的感性認識在後文相關的專業內容介紹中胖哥會再次講到Hash。
簡單地看就是如果知道隊名就能知道在哪個範圍然後在範圍內查找名稱。在前麵的一些介紹中已經有所體現在找班級的時候就是這樣找的隻是各自有自己的排序方法——這裏按照“隊伍”來分布而前麵的例子是按照“班級”來分布的。
在Java語言裏Hash算法通常是按照hashCode來分布的前麵提到過在不同的場景下這個hashCode會計算出不同的值——可用對象頭部的一個標識符可用某些對象的屬性通過一定計算得到同一個hashCode肯定在同一個分組上這個分組也就是專業說法上的“桶”“桶”內部的數據通常是無序的通常內部用一個鏈表存放有的小夥伴會問鏈表不是有序的嗎其實這裏所謂的無序是指鏈表上存放的數據並沒有要求外部寫入的數據以先進先出或後進先出的順序存放外部程序也不能依賴於遍曆的順序。
在查找數據時首先根據hashCode找到桶然後在這個桶內部需要逐個使用equals()方法來對比內部的值而在極度衝突的情況下許多數據將被放在同一個桶中通常叫作“熱點”導致一個桶的數據鏈表會非常長這樣一來分布在該桶上的查找、遍曆等操作都會變得很慢。因此千萬不要因為Hash算法的複雜度是O(1)就認為它天下無敵了其實這隻是一個相對量級別的說法實際場景中的開銷我們要用數字來說話。
圖1-5 狗狗要找隊伍和位置
反過來說如果要使用Hash來做大量數據的查找那麼需要設計合適多的Hash桶。另外在設計hashCode、hashCode與桶的下標轉換的時候要有足夠的離散能力否則會做“賠了夫人又折兵”的事情。
有人曾經用一種固定Hash的方式來存儲網絡上的URL喜歡鑽空子的小夥伴利用了這種方式形成一種網絡攻擊手段。他們在知道算法的基礎上通過模擬同樣hashCode的不同URL使得某些“桶”內部的數據變得特別多每一個分布到這個“桶”的請求都會在這個“桶”內部查找最壞的情況就是一個也沒有找到那麼就需要遍曆整個鏈表這樣就可能使得係統性能極度下降。
看到這裏你若有所領悟胖哥就心滿意足了。雖然本節知識會相對枯燥些但仍然在闡述一些和我們工作密切相關的基礎思想。接下來我們再來看看基礎知識“運算符”。
最後更新：2017-05-23 14:32:55