問題:假設一個文件中有9億條不重復的9位整數，現在要求對這個文件進行排序。?

一般解題思路:?
1、將數據導入到內存中?
2、將數據進行排序　（比如插入排序、快速排序）?
3、將排序好的數據存入文件?

難題:?
一個整數為4個字節?
即使使用數組也需要900,000,000 * 4byte = 3.4G內存?
對于32位系統，訪問2G以上的內存非常困難，而且一般設備也沒有這么多的物理內存?
將數據完全導入到內存中的做法不現實?

其他解決辦法:?
1、導入數據庫運算?
2、分段排序運算?
3、使用bit位運算?

解決方案一:數據庫排序?
將文本文件導入到數據庫，讓數據庫進行索引排序操作后提取數據到文件?

優點：操作簡單?
缺點：運算速度慢，而且需要數據庫設備。?

解決方案二:分段排序?
操作方式：?
規定一個內存大小，比如200M，200M可以記錄(200*1024*1024/4) = 52428800條記錄，我們可以每次提取5000萬條記錄到文件進行排序，要裝滿9位整數需要20次，所以一共要進行20次排序，需要對文件進行20次讀操作?

缺點：?
編碼復雜，速度也慢(至少20次搜索)?

關鍵步驟：?
先將整個9位整數進行分段，億條數據進行分成20段，每段5000萬條?
在文件中依次搜索0~5000萬，50000001~1億……?
將排序的結果存入文件?

解決方案三:bit位操作?
思考下面的問題:?
一個最大的9位整數為999999999?
這9億條數據是不重復的?
可不可以把這些數據組成一個隊列或數組，讓它有0~999999999(10億個)元素?
數組下標表示數值，節點中用0表示這個數沒有，1表示有這個數?
判斷0或1只用一個bit存儲就夠了?

聲明一個可以包含9位整數的bit數組(10億)，一共需要10億/8=120M內存?
把內存中的數據全部初始化為0, 讀取文件中的數據，并將數據放入內存。比如讀到一個數據為341245909這個數據，那就先在內存中找到341245909這個bit，并將bit值置為1遍歷整個bit數組，將bit為1的數組下標存入文件?

關鍵代碼?
檢查是某一個char里面(first)的第second位中存儲的數據是否為1?

bool CompareBit (unsigned char first, int second)?
{?
const static int mark_buf[] = {0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80};?
if (second > .8)?
return false;?

return (first & mark_buf[second]) == mark_buf[second];?
}?

將某一個char(Desc)中的第source位置為1?

bool WriteToBit (unsigned char *Desc, int source)?
{?
const static int mark_buf[] = {0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80};?

if (source >? .8)?
return false;?

Desc[0] |= mark_buf[source];?

return true;?
}?

案例?
在某個項目中，我們需要對2億條手機號碼刪除重復記錄(過濾號碼黑名單同樣有效)?

工作難點就在于如何處理這2億條電話號碼,直接用哈希表存放手機號碼不大現實,即使經過優化,用一個unsigned int存放一條記錄,那也得需要2億*4=8億byte,遠超過32位系統的尋址能力?

解決方案:?
將電話號碼由12位單個數字組成的字符串轉換為一個unsigned int型數據(這個完全可能,手機號碼由前三位數字和后面八位數字組成,后面八位需要占到1~1000萬的空間,而前面用0~100的數字存儲已經足夠)為簡單起見,默認為0~4G的數字都有可能分布號碼,為此我們分配4G/32=512M的內存將這2億個號碼整理成unsigned int類型后按上述辦法存放在這塊內存中(比如13512345678我們整理后為112345678,我們找到內存中112345678bit的下標,并將此bit值設為1)遍歷整個bit數組,記錄下所有的號碼,這些號碼即是不重復的手機號碼?

總結?
建立一個足夠大的bit數組當作hash表?
以bit數組的下標來表示一個整數?
以bit位中的0或1來表示這個整數是否在這個數組中存在?
適用于無重復原始數據的搜索?
原來每個整數需要4byte空間變為1bit，空間壓縮率為32倍?
擴展后可實現其他類型（包括重復數據）的搜索 < xmlnamespace prefix ="o" ns ="urn:schemas-microsoft-com:office:office" />

?

?

主題：3000w數據的表，取某項字段前50項數據，內存2G

偶然看到這個題，就想了一下怎么做，大體實現思路是這樣子的，3000w的數據劃分為1000段，也就是1-3w為一段，30001-6w項為第二段，依次類推，從每3w的數據中提取出前50條數據（這個根據sql排序就能取出來，2個g的內存夠了），最后1000個50就會產生5w個數據，最后提取出來的5w的數據放置到ArrayList中去，最后5w的數據統一排序，取出前50條。5w*5w的對比與交換是可以搞定的。具體實現，等最近的項目完了用多線程試試！

?

主題：【探討】給你1G內存，如何從3000萬個手機號碼中檢索出你要的號碼，要求每秒檢索>1000次

?

?

主題：3億數據快速檢索實現

上周有個需求，就是要做一個檢索庫：?
　　１　３億個手機號碼，并且每個號碼２０個左右的屬性例：地區，訂閱等信息。?
　　２　在最短的時候內select出來（５分鐘，１０分鐘）[最重要]?
　　３　允許更新。對這些號碼進行發送信息后，狀態改變。[可以讓他慢慢更新]?
　　和幾個同事討論了一下，具體要注意以下幾點：?
　　１　如果發送下去狀態改變，但是只發送一半，但狀態改變了如何辦？?
　　２　如果多個產品線一起下發，狀態會不會混亂。?
　　解決以上第二個問題，決定采用，隊列等待的方式。第一個問題沒想到好的解決辦法，回滾也想過了，但感覺不是很現實！?

　　解決方案：?
　　經過實驗500w條的數據在用plsql直接select，只需要０.２秒，所以總體采用分表的方式，每500w條分一個表，然后同時查詢！?
-----------------------------------------重新描述一下需求-------------------------------?
很多人說需求不是很的清楚，這里重新整理了一下！?
不過要注意的是數據庫里已經有3億個手機基數了！?
一．號碼入庫。?
不定期會有新的號碼需要入庫，入庫需要記錄號碼的常規屬性，如：手機號，省份，城市，入庫時間，手機卡類型，是否支持彩信，號碼來源情況等。?
二．入庫手機號源文件管理?
入庫手機號源文件要以文件形式保存在服務器上。?
三．按需要提取號碼（最關鍵部分）?
要按照需求提取所需的號碼。?

例如：?
提號要求：?
1.此號碼非黑名單用戶。?
2.此號碼為的訂購和退訂用戶。?
3.此號碼2個月內沒有活動。?
4.省份要求：遼寧，云南，廣東?
5.號段要求：137和138和139號段?
6.數量要求：每個省10w?
7.是否支持彩信：是（是，否，忽略三種情況）?
……?

最后，符合條件的號碼，按照固定格式（每個手機號占一行），形成文本文件，將此文件測試號碼，是否需要狀態報告等信息形成最終可發送文件并提供下載功能，同時記錄本次提取信息（發送時間，發送標識等）?
注：文件格式如下：?
139***85185#09#0?
139***71283?
139***33190?
第1列：手機號?
第2列：產品類型（#09）?
第3列：是否需要狀態報告（#0）?

四．統計功能?
一．號碼情況統計?
1.統計當前號碼總量。?
2.按照2個基本要求，統計現在庫中可以使用的號碼數量。?
注：統計需要顯示，全國總量，各省總量，各省省會總量，各省去除省會總量，各省7天未下發總量（省會與其他城市分開顯示），各省可以發送總量（省會與其他城市分開顯示，所以單獨列出來）。?

二．發送產品統計?
1.按時間段、業務線等統計發送產品的情況，如：發送時間，最終發送文件等?

五．黑名單及特殊號碼管理?
1.?添加黑名單?
2.?去除黑名單?
3.?過濾黑名單?
4.?查詢黑名單?

以上除黑名單外都是迫切需要的，黑名單功能可以以后完善。

?

?

?

現在有一萬（1-10000）的個數，從中拿掉一個數，還剩9999個數，現在用一個數組來存儲這9999個數，問怎么才能找出拿掉的數？

用10000個數的數組循環匹配9999個數，匹配成功，從9999數組中去除，不成功就是該數。?

大家還有什么好的思路沒有？

?

問題:假設一個文件中有9億條不重復的9位整數，現在要求對這個文件進行排序。

一般解題思路:?1、將數據導入到內存中 2、將數據進行排序　（比如插入排序、快速排序） 3、將排序好的數據存入文件

難題:?一個整數為4個字節即使使用數組也需要900,000,000 * 4byte = 3.4G內存對于32位系統，訪問2G以上的內存非常困難，而且一般設備也沒有這么多的物理內存將數據完全導入到內存中的做法不現實。

其他解決辦法:?1、導入數據庫運算 2、分段排序運算 3、使用bit位運算

解決方案一:數據庫排序?將文本文件導入到數據庫，讓數據庫進行索引排序操作后提取數據到文件

優點：操作簡單缺點：運算速度慢，而且需要數據庫設備。

解決方案二:分段排序?操作方式：規定一個內存大小，比如200M，200M可以記錄52428800條記錄，我們可以每次提取5000萬條記錄到文件進行排序，要裝滿9位整數需要20次，所以一共要進行20次排序，需要對文件進行20次讀操作

缺點：?編碼復雜，速度也慢(至少20次搜索)

關鍵步驟：先將整個9位整數進行分段，億條數據進行分成20段，每段5000萬條，在文件中依次搜索0~5000萬，50000001~1億…… 將排序的結果存入文件

解決方案三:bit位操作?思考下面的問題: 一個最大的9位整數為999999999 這9億條數據是不重復的，可不可以把這些數據組成一個隊列或數組，讓它有0~999999999(10億個)元素數組下標表示數值，節點中用0表示這個數沒有，1表示有這個數，判斷0或1只用一個bit存儲就夠了

聲明一個可以包含9位整數的bit數組(10億)，一共需要10億/8=120M內存，把內存中的數據全部初始化為0 ，讀取文件中的數據，并將數據放入內存。比如讀到一個數據為341245909這個數據，那就先在內存中找到341245909這個bit，并將bit值置為1 ，遍歷整個bit數組，將bit為1的數組下標存入文件

關鍵代碼?檢查是某一個char里面(first)的第second位中存儲的數據是否為1

bool CompareBit (unsigned char first, int second)

?{

const static int mark_buf[] = {0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80};

if (second > 8) return false;

return (first & mark_buf[second]) == mark_buf[second];

?}

將某一個char(Desc)中的第source位置為1

bool WriteToBit (unsigned char *Desc, int source)

{

const static int mark_buf[] = {0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80};

if (source > 8) return false;

Desc[0] |= mark_buf[source];

return true;

}

案例?在某個項目中，我們需要對2億條手機號碼刪除重復記錄(過濾號碼黑名單同樣有效)

工作難點就在于如何處理這2億條電話號碼,直接用哈希表存放手機號碼不大現實,即使經過優化,用一個unsigned int存放一條記錄,那也得需要2億*4=8億byte,遠超過32位系統的尋址能力

解決方案:?將電話號碼由12位單個數字組成的字符串轉換為一個unsigned int型數據(這個完全可能,手機號碼由前三位數字和后面八位數字組成，后面八位需要占到1~1000萬的空間,而前面用0~100的數字存儲已經足夠) ，為簡單起見，默認為0~4G的數字都有可能分布號碼，為此我們分配4G/32=512M的內存，將這2億個號碼整理成unsigned int類型后按上述辦法存放在這塊內存中(比如13512345678我們整理后為112345678,我們找到內存中112345678bit的下標,并將此bit值設為1) ，遍歷整個bit數組,記錄下所有的號碼,這些號碼即是不重復的手機號碼

總結?建立一個足夠大的bit數組當作hash表，以bit數組的下標來表示一個整數，以bit位中的0或1來表示這個整數是否在這個數組中存在，適用于無重復原始數據的搜索，原來每個整數需要4byte空間變為1bit，空間壓縮率為32倍，擴展后可實現其他類型（包括重復數據）的搜索

注意?由于操作系統和編程語言本身的限制，有可能內存足夠，但無法分配一塊連續大內存的情況，這樣的話可以申請多塊稍微小一點的內存，然后用鏈表或其他的方式連接起來使用

?

?

關于海量數據處理

常用的數據結構：

1.Bloom Filter

?? 大致思想是這樣，把一個數據通過N個哈希函數映射到一個長度為M的數組的一位上，將hash函數對應的值的位數組置1，查找時如果發現所有hash函數對應位都是1說明該數據的存在。但不能保證完全正確性，但是此方法無比高效。

【實例】給你A,B兩個文件，各存放50億條URL，每條URL占用64字節，內存限制是4G，讓你找出A,B文件共同的URL。如果是三個乃至n個文件呢？?

2.哈希法

?? 這個簡單，無非是通過一些哈希函數把元素搞到一個指定的位置，簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。這個很一般啊感覺。無非就是分類查找么，完全不如1猛。

3.最大或最小堆

?? ? 就是一個完全的最大或最小二叉樹，用途，比如:1)100w個數中找最大的前100個數。?用一個100個元素大小的最小堆即可。感覺還是不錯的。

4.Bit-map

所謂的Bit-map就是用一個bit位來標記某個元素對應的Value， 而Key即是該元素。由于采用了Bit為單位來存儲數據，因此在存儲空間方面，可以大大節省。

【問題實例】

1)已知某個文件內包含一些電話號碼，每個號碼為8位數字，統計不同號碼的個數。

8位最多99 999 999，大概需要99M個bit，大概10幾m字節的內存即可。 （可以理解為從0-99 999 999的數字，每個數字對應一個Bit位，所以只需要99M個Bit==1.2MBytes，這樣，就用了小小的1.2M左右的內存表示了所有的8位數的電話）

2)2.5億個整數中找出不重復的整數的個數，內存空間不足以容納這2.5億個整數。

將bit-map擴展一下，用2bit表示一個數即可，0表示未出現，1表示出現一次，2表示出現2次及以上，在遍歷這些數的時候，如果對應位置的值是0，則將其置為1；如果是1，將其置為2；如果是2，則保持不變。或者我們不用2bit來進行表示，我們用兩個bit-map即可模擬實現這個2bit-map，都是一樣的道理。

公司的一道考試題算法分析——大數據量整數排序

????題目大意：移動公司需要對已經發放的所有139段的號碼進行統計排序，已經發放的139號碼段的文件都存放在一個文本文件中（原題是放在兩個文件中），一個號碼一行，現在需要將文件里的所有號碼進行排序，并寫入到一個新的文件中；號碼可能會有很多，最多可能有一億個不同的號碼（所有的139段號碼），存入文本文件中大概要占1.2G的空間；jvm最大的內存在300以內，程序要考慮程序的可執行性及效率；只能使用Java標準庫，不得使用第三方工具。?
????這是個典型的大數據量的排序算法問題，首先要考慮空間問題，一下把1.2G的數據讀入內存是不太可能的，就算把1一億條數據，轉都轉換成int類型存儲也要占接近400M的空間。當時做個題目我并沒有想太多的執行效率問題，主要就考慮了空間，而且習慣性的想到合并排序，基本思想是原文件分割成若干個小文件并排序，再將排序好的小文件合并得到最后結果，算法大概如下：?

??? 1.順序讀取存放號碼文件的中所有號碼，并取139之后的八位轉換為int類型；每讀取號碼數滿一百萬個，（這個數據可配置）將已經讀取的號碼排序并存入新建的臨時文件。
??? 2.將所有生成的號碼有序的臨時文件合并存入結果文件。?

????這個算法雖然解決了空間問題，但是運行效率極低，由于IO讀寫操作太多，加上步驟1中的排序的算法（快速排序）本來效率就不高（對于電話排序這種特殊情況來說），導致1億條數據排序運行3個小時才有結果。?

????如果和能夠減少排序的時間呢？首當其沖的減少IO操作，另外如果能夠有更加好排序算法也行。前天無聊再看這個題目時突然想到大三時看《編程珠璣》時上面也有個問題的需求這個這個題目差不多，記得好像使用是位向量（實際上就是一個bit數組），用電話作為index，心中大喜，找到了解決此問題的最完美方案啦：用位向量存儲電話號碼，一個號碼占一個bit，一億個電話號碼也只需要大概12M的空間；算法大概如下：
????? 1.初始化bits[capacity]；
????? 2.順序所有讀入電話號碼，并轉換為int類型，修改位向量值：bits[phoneNum]=1；
????? 3.遍歷bits數組，如果bits[index]=1，轉換index為電話號碼輸出。?
??? Java中沒有bit類型，一個boolean值占空間為1byte（感興趣的可以自己寫程序驗證），我自己寫個用int模擬bit數組的類，代碼如下：?
???

Java代碼< xmlnamespace prefix ="v" ns ="urn:schemas-microsoft-com:vml" />

public?class?BitArray?{ ??

????private?int[]?bits?=?null; ??

????private?int?length; ??

????//用于設置或者提取int類型的數據的某一位(bit)的值時使用??

????private?final?static?int[]?bitValue?=?{ ??

????????0x80000000,//10000000?00000000?00000000?00000000?????? ??

????????0x40000000,//01000000?00000000?00000000?00000000?????? ??

????????0x20000000,//00100000?00000000?00000000?00000000?????? ??

????????0x10000000,//00010000?00000000?00000000?00000000?????? ??

????????0x08000000,//00001000?00000000?00000000?00000000?????? ??

????????0x04000000,//00000100?00000000?00000000?00000000?????? ??

????????0x02000000,//00000010?00000000?00000000?00000000?????? ??

????????0x01000000,//00000001?00000000?00000000?00000000?????? ??

????????0x00800000,//00000000?10000000?00000000?00000000?????? ??

????????0x00400000,//00000000?01000000?00000000?00000000?????? ??

????????0x00200000,//00000000?00100000?00000000?00000000?????? ??

????????0x00100000,//00000000?00010000?00000000?00000000?????? ??

????????0x00080000,//00000000?00001000?00000000?00000000?????? ??

????????0x00040000,//00000000?00000100?00000000?00000000?????? ??

????????0x00020000,//00000000?00000010?00000000?00000000?????? ??

????????0x00010000,//00000000?00000001?00000000?00000000?????????? ??

????????0x00008000,//00000000?00000000?10000000?00000000?????? ??

????????0x00004000,//00000000?00000000?01000000?00000000?????? ??

????????0x00002000,//00000000?00000000?00100000?00000000?????? ??

????????0x00001000,//00000000?00000000?00010000?00000000?????? ??

????????0x00000800,//00000000?00000000?00001000?00000000?????? ??

????????0x00000400,//00000000?00000000?00000100?00000000?????? ??

????????0x00000200,//00000000?00000000?00000010?00000000?????? ??

????????0x00000100,//00000000?00000000?00000001?00000000?????? ??

????????0x00000080,//00000000?00000000?00000000?10000000?????? ??

????????0x00000040,//00000000?00000000?00000000?01000000?????? ??

????????0x00000020,//00000000?00000000?00000000?00100000?????? ??

????????0x00000010,//00000000?00000000?00000000?00010000?????? ??

????????0x00000008,//00000000?00000000?00000000?00001000?????? ??

????????0x00000004,//00000000?00000000?00000000?00000100?????? ??

????????0x00000002,//00000000?00000000?00000000?00000010?????? ??

????????0x00000001?//00000000?00000000?00000000?00000001???????????? ??

????}; ??

????public?BitArray(int?length)?{ ??

????????if(length?<?0){ ??

????????????throw?new?IllegalArgumentException("length必須大于零！"); ??

????????} ??

????????bits?=?new?int[length?/?32?+?(length?%?32?>?0???1?:?0)]; ??

????????this.length?=?length; ??

????} ??

????//取index位的值??

????public?int?getBit(int?index){ ??

????????if(index?<0?||?index?>?length){ ??

????????????throw?new?IllegalArgumentException("length必須大于零小于"?+?length); ??

????????} ??

????????int?intData?=?bits[index/32]; ??

????????return?(intData?&?bitValue[index%32])?>>>?(32?-?index%32?-1); ??

????} ??

????//設置index位的值，只能為0或者1???

????public?void?setBit(int?index,int?value){ ??

????????if(index?<0?||?index?>?length){ ??

????????????throw?new?IllegalArgumentException("length必須大于零小于"?+?length); ??

????????}??????? ??

????????if(value!=1&&value!=0){ ??

????????????throw?new?IllegalArgumentException("value必須為0或者1"); ??

????????} ??

????????int?intData?=?bits[index/32]; ??

????????if(value?==?1){ ??

????????????bits[index/32]?=?intData?|?bitValue[index%32]; ??

????????}else{ ??

????????????bits[index/32]?=?intData?&?~bitValue[index%32]; ??

????????} ??

????} ??

????public?int?getLength(){ ??

????????return?length; ??

????}??? ??

}???? ??

??????

public class BitArray { ? private int[] bits = null; ? private int length; ? //用于設置或者提取int類型的數據的某一位(bit)的值時使用 ? private final static int[] bitValue = { ?? 0x80000000,//10000000 00000000 00000000 00000000????? ?? 0x40000000,//01000000 00000000 00000000 00000000????? ?? 0x20000000,//00100000 00000000 00000000 00000000????? ?? 0x10000000,//00010000 00000000 00000000 00000000????? ?? 0x08000000,//00001000 00000000 00000000 00000000????? ?? 0x04000000,//00000100 00000000 00000000 00000000????? ?? 0x02000000,//00000010 00000000 00000000 00000000????? ?? 0x01000000,//00000001 00000000 00000000 00000000????? ?? 0x00800000,//00000000 10000000 00000000 00000000????? ?? 0x00400000,//00000000 01000000 00000000 00000000????? ?? 0x00200000,//00000000 00100000 00000000 00000000????? ?? 0x00100000,//00000000 00010000 00000000 00000000????? ?? 0x00080000,//00000000 00001000 00000000 00000000????? ?? 0x00040000,//00000000 00000100 00000000 00000000????? ?? 0x00020000,//00000000 00000010 00000000 00000000????? ?? 0x00010000,//00000000 00000001 00000000 00000000?? ? ?? 0x00008000,//00000000 00000000 10000000 00000000????? ?? 0x00004000,//00000000 00000000 01000000 00000000????? ?? 0x00002000,//00000000 00000000 00100000 00000000????? ?? 0x00001000,//00000000 00000000 00010000 00000000????? ?? 0x00000800,//00000000 00000000 00001000 00000000????? ?? 0x00000400,//00000000 00000000 00000100 00000000????? ?? 0x00000200,//00000000 00000000 00000010 00000000????? ?? 0x00000100,//00000000 00000000 00000001 00000000????? ?? 0x00000080,//00000000 00000000 00000000 10000000????? ?? 0x00000040,//00000000 00000000 00000000 01000000????? ?? 0x00000020,//00000000 00000000 00000000 00100000????? ?? 0x00000010,//00000000 00000000 00000000 00010000????? ?? 0x00000008,//00000000 00000000 00000000 00001000????? ?? 0x00000004,//00000000 00000000 00000000 00000100????? ?? 0x00000002,//00000000 00000000 00000000 00000010????? ?? 0x00000001 //00000000 00000000 00000000? 00000001 ???? ? }; ? public BitArray(int length) { ?? if(length < 0){ ???? throw new IllegalArgumentException("length必須大于零！"); ?? } ?? bits = new int[length / 32 + (length % 32 > 0 ? 1 : 0)]; ?? this.length = length; ? } ? //取index位的值 ? public int getBit(int index){ ?? if(index <0 || index > length){ ???? throw new IllegalArgumentException("length必須大于零小于" + length); ?? } ?? int intData = bits[index/32]; ?? return (intData & bitValue[index%32]) >>> (32 - index%32 -1); ? } ? //設置index位的值，只能為0或者1 ? public void setBit(int index,int value){ ?? if(index <0 || index > length){ ???? throw new IllegalArgumentException("length必須大于零小于" + length); ?? }?? ?? if(value!=1&&value!=0){ ???? throw new IllegalArgumentException("value必須為0或者1"); ?? } ?? int intData = bits[index/32]; ?? if(value == 1){ ???? bits[index/32] = intData | bitValue[index%32]; ?? }else{ ???? bits[index/32] = intData & ~bitValue[index%32]; ?? } ? } ? public int getLength(){ ?? return length; ? }? }??? ????

????
??? bit數組有了，剩下就是算法代碼，核心代碼如下：?
???

Java代碼

bitArray?=?new?BitArray(100000000);? ??

//順序讀取所有的手機號碼??

while((phoneNum?=?bufferedReader.readLine())!=null){ ??

????phoneNum?=?phoneNum.trim().substring(3);//13573228432 ??

????//取139后8位轉換為int類型??

????phoneNumAsInt?=?Integer.valueOf(phoneNum); ??

????//設置對應bit值為1???

????bitArray.setBit(phoneNumAsInt,?1); ??

}??? ??

//遍歷bit數組輸出所有存在的號碼??

for(int?i?=?0;i<sortUnit;i++){ ??

????if(bitArray.getBit(i)==1){ ??

????????????writer.write("139"?+?leftPad(String.valueOf(i?+?sortUnit*times),?8)); ??

????????????writer.newLine();??????????????????????? ??

????}??????????????? ??

} ??

writer.flush(); ??

???

???? bitArray = new BitArray(100000000);? ???? //順序讀取所有的手機號碼 ???? while((phoneNum = bufferedReader.readLine())!=null){ ????? phoneNum = phoneNum.trim().substring(3);//13573228432 ????? //取139后8位轉換為int類型 ????? phoneNumAsInt = Integer.valueOf(phoneNum); ????? //設置對應bit值為1 ????? bitArray.setBit(phoneNumAsInt, 1); ???? }? ???? //遍歷bit數組輸出所有存在的號碼 ???? for(int i = 0;i<sortUnit;i++){ ?? ??? ? if(bitArray.getBit(i)==1){ ? ??? ???? writer.write("139" + leftPad(String.valueOf(i + sortUnit*times), 8)); ? ??? ?? ? writer.newLine();???? ??? ?? ?? ????? }????? ???? } ???? writer.flush();經測試，修改后的算法排序時只需要20多M的內存，一億條電話號碼排序只要10分鐘（時間主要花在IO上），看來效果還是很明顯的。 這個算法很快，不過也有他的局限性： 1.只能用于整數的排序，或者可以準確映射到正整數（對象不同對應的正整數也不相同）的數據的排序。 2.不能處理重復的數據，重復的數據排序后只有一條（如果有這種需求可以在這個算法的基礎上修改，給出現次數大于1的數據添加個計數器，然后存入Map中） 3.對于數據量極其大的數據處理可能還是比較占用空間，這種情況可配合多通道排序算法解決。

來源:http://blog.csdn.net/lixam/article/details/8845310

總結

以上是生活随笔為你收集整理的关于海量数据查找排序问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。