##40億個數中快速查找 ### 題目描述 給40億個不重復的unsigned int的整數，沒排過序的，然后再給一個數，如何快速判斷這個數是否在那40億個數當中？ ### 分析與解法 海量數據處理往往會很有趣，有趣在什么地方呢？ * 空間，available的內存不夠，需要反復交換內存 * 時間，速度太慢不行，畢竟那是海量數據 * 處理，數據是一次調用還是反復調用，因為針對時間和空間，通常來說，多次調用的話，勢必會增加預處理以減少每次調用的時候的時間代價。 #### 解法一 咱們回到眼前要解決的這個問題，1個unsigned int占用4字節，40億大約是4G個數，那么一共大約要用16G的內存空間，如果內存不夠大，反復和硬盤交換數據的話，后果不堪設想。 那么怎么儲存這么多的數據呢？還記得伴隨數組么？還是那種思想，利用內存地址代替下標。 先舉例，在內存中應該是1個byte=8bit，那么明顯有 0 = 0000 0000 255 = 1111 1111 69 = 0100 0101 那么69可以表示0.2.6三個數存在，其余的7以下的數不存在，0表示0-7都不存在，255表示0-7都存在，這就是位圖算法：通過全部置0，存在置1，這樣一種模式來通過連續的地址存貯數據，和檢驗數據的方法。 那么1個 unsigned int代表多少個數呢？1個unsigned int 是一個2^32以內的數，那么也就是這樣的1個數，可以表示32個數是否存在。同理申請一個unsigned int的數組a[n]則可以表示連續的 n*32的數。也就是a[0]表示0-31的數是否存在，a[1]表示32-63的數是否存在，依次類推。 這時候需要用多大的內存呢？ 16G/32=512M 512M和16G之間的區別，卻是是否一個32位尋址的CPU能否辦得到的事兒了，眾所周知，32位CPU最大尋址不超過4G，固然，你會說，現在都是64位的CPU之類的云云，但是，對于底層的設計者來說，尋址范圍越小越好操控的事實是不爭的。 問題到這里，其實基本上已經完事了，判斷本身，在位圖算法這里就是找到對應的內存位置是否為1就可以了。 #### 解法二 當然，下面就要開始說一說，當數據超出了可以接受的范圍之后的事情了。比如， 2^66范圍的數據檢索，也會是一個問題 4倍于64位CPU尋址范圍，如果加上CPU本身的偏移寄存器占用的資源，可能應該是6-8個64位CPU的尋址范圍，如果反復從內存到硬盤的讀寫，過程本身就是可怕的。 算法，更多的是用來解決瓶頸的，就想現在，根本不用考慮內存超出8M的問題，但是20年前，8086的年代，內存4M，或者內存8M，你怎么處理?固然做軟件的不需要完全考慮摩爾定律，但是摩爾定律絕對是影響軟件和算法編寫者得想法的。 再比如，烏克蘭俄羅斯的一批壓縮高手，比如國內有名的R大，為什么壓縮會出現？就是因為，要么存不下，要么傳輸時間過長。網絡再好，64G的高清怎么的也得下遍歷n個元素取出等概率載個一段時間吧。海量數據處理，永遠是考慮超過了當前硬件條件的時候，該怎么辦？！ 那么我們可以發現一個更加有趣的問題，如果存不下，但是還要存，怎么辦！ 壓縮！這里簡單的說一嘴，無損壓縮常見的為Huffman算法和LZW(Lenpel-Ziv &Welch)壓縮算法，前者研究不多，后者卻經常使用。 因為上面提到了位圖算法，我就用常見的位圖類的數據舉例： 以下引自我的摘抄出處忘記了，請作者見諒： 對原始數據ABCCAABCDDAACCDB進行LZW壓縮 原始數據中，只包括4個字符(Character),A,B,C,D,四個字符可以用一個2bit的數表示，0-A,1-B,2-C,3-D,從最直觀的角度看，原始字符串存在重復字符：ABCCAABCDDAACCDB，用4代表AB,5代表CC，上面的字符串可以替代表示為:45A4CDDAA5DB,這樣是不是就比原數據短了一些呢！ ### 問題擴展 為了區別代表串的值(Code)和原來的單個的數據值(String)，需要使它們的數值域不重合，上面用0-3來代表A-D,那么AB就必須用大于3的數值來代替，再舉另外一個例子，原來的數值范圍可以用8bit來表示，那么就認為原始的數的范圍是0～255，壓縮程序生成的標號的范圍就不能為0～255（如果是0-255，就重復了）。只能從256開始，但是這樣一來就超過了8位的表示范圍了，所以必須要擴展數據的位數，至少擴展一位，但是這樣不是增加了1個字符占用的空間了么？但是卻可以用一個字符代表幾個字符，比如原來255是8bit,但是現在用256來表示254，255兩個數，還是劃得來的。從這個原理可以看出LZW算法的適用范圍<u>是原始數據串最好是有大量的子串多次重復出現，重復的越多，壓縮效果越好。反之則越差，可能真的不減反增了</u>。 偽代碼如下 ``` STRING = get input character WHILE there are still input characters DO CHARACTER = get input character IF STRING+CHARACTER is in the string table then STRING = STRING+character ELSE output the code for STRING add STRING+CHARACTER to the string table STRING = CHARACTER END of IF END of WHILE output the code for STRING ``` 看過上面的適用范圍再聯想本題，數據有多少種，根據同余模的原理，可以驚人的發現，其實真的非常適合壓縮，但是壓縮之后，盡管存下了，在查找的時候，勢必又需要解碼，那么又回到了我們當初學習算法時的那句經典話，算法本身，就是為了解決時間和空間的均衡問題，要么時間換空間，要么空間換時間。 更多的，請讀者自行思考，因為，壓縮本身只是想引起讀者思考，已經是題外話了~本部分完--__上善若水.qinyu__。