【什么是雙層桶】
事實上，與其說雙層桶劃分是一種數(shù)據(jù)結構，不如說它是一種算法設計思想。面對一堆大量的數(shù)據(jù)我們無法處理的時候，我們可以將其分成一個個小的單元，然后根據(jù)一定的策略來處理這些小單元，從而達到目的。
【適用范圍】
第k大，中位數(shù)，不重復或重復的數(shù)字
【基本原理及要點】
因為元素范圍很大，不能利用直接尋址表，所以通過多次劃分，逐步確定范圍，然后最后在一個可以接受的范圍內(nèi)進行。可以通過多次縮小，雙層只是一個例子，分治才是其根本（只是“只分不治”）。
【擴展】
當有時候需要用一個小范圍的數(shù)據(jù)來構造一個大數(shù)據(jù)，也是可以利用這種思想，相比之下不同的，只是其中的逆過程。
【問題實例】
1).2.5億個整數(shù)中找出不重復的整數(shù)的個數(shù)，內(nèi)存空間不足以容納這2.5億個整數(shù)。
有點像鴿巢原理，整數(shù)個數(shù)為2^32,也就是，我們可以將這2^32個數(shù)，劃分為2^8個區(qū)域(比如用單個文件代表一個區(qū)域)，然后將數(shù)據(jù)分離到不同的區(qū)域，然后不同的區(qū)域在利用bitmap就可以直接解決了。也就是說只要有足夠的磁盤空間，就可以很方便的解決。 當然這個題也可以用我們前面講過的BitMap方法解決，正所謂條條大道通羅馬~~~
2).5億個int找它們的中位數(shù)。
這個例子比上面那個更明顯。首先我們將int劃分為2^16個區(qū)域，然后讀取數(shù)據(jù)統(tǒng)計落到各個區(qū)域里的數(shù)的個數(shù)，之后我們根據(jù)統(tǒng)計結果就可以判斷中位數(shù)落到那個區(qū)域，同時知道這個區(qū)域中的第幾大數(shù)剛好是中位數(shù)。然后第二次掃描我們只統(tǒng)計落在這個區(qū)域中的那些數(shù)就可以了。
實際上，如果不是int是int64，我們可以經(jīng)過3次這樣的劃分即可降低到可以接受的程度。即可以先將int64分成2^24個區(qū)域，然后確定區(qū)域的第幾 大數(shù)，在將該區(qū)域分成2^20個子區(qū)域，然后確定是子區(qū)域的第幾大數(shù)，然后子區(qū)域里的數(shù)的個數(shù)只有2^20，就可以直接利用direct addr table進行統(tǒng)計了。
3).現(xiàn)在有一個0-30000的隨機數(shù)生成器。請根據(jù)這個隨機數(shù)生成器，設計一個抽獎范圍是0-350000彩票中獎號碼列表，其中要包含20000個中獎號碼。
這個題剛好和上面兩個思想相反，一個0到3萬的隨機數(shù)生成器要生成一個0到35萬的隨機數(shù)。那么我們完全可以將0-35萬的區(qū)間分成35/3=12個區(qū)間，然后每個區(qū)間的長度都小于等于3萬，這樣我們就可以用題目給的隨機數(shù)生成器來生成了，然后再加上該區(qū)間的基數(shù)。那么要每個區(qū)間生成多少個隨機數(shù)呢？計算公式就是：區(qū)間長度*隨機數(shù)密度，在本題目中就是30000*（20000/350000）。最后要注意一點，該題目是有隱含條件的：彩票，這意味著你生成的隨機數(shù)里面不能有重復，這也是我為什么用雙層桶劃分思想的另外一個原因。
做人好厚道，轉(zhuǎn)載請注明出處：http://diducoder.com/mass-data-topic-6-multi-dividing.html