第一篇：火龍果軟件-海量數據處理小結

火龍果?整理 uml.org.cn

海量的數據處理問題，對其進行處理是一項艱巨而復雜的任務。原因有以下幾個方面：

一、數據量過大，數據中什么情況都可能存在。如果說有10條數據，那么大不了每條去逐一檢查，人為處理，如果有上百條數據，也可以考慮，如果數據上到千萬級別，甚至過億，那不是手工能解決的了，必須通過工具或者程序進行處理，尤其海量的數據中，什么情況都可能存在，例如，數據中某處格式出了問題，尤其在程序處理時，前面還能正常處理，突然到了某個地方問題出現了，程序終止了。

二、軟硬件要求高，系統資源占用率高。對海量的數據進行處理，除了好的方法，最重要的就是合理使用工具，合理分配系統資源。一般情況，如果處理的數據過TB級，小型機是要考慮的，普通的機子如果有好的方法可以考慮，不過也必須加大CPU和內存，就象面對著千軍萬馬，光有勇氣沒有一兵一卒是很難取勝的。

三、要求很高的處理方法和技巧。這也是本文的寫作目的所在，好的處理方法是一位工程師長期工作經驗的積累，也是個人的經驗的總結。沒有通用的處理方法，但有通用的原理和規則。那么處理海量數據有哪些經驗和技巧呢，我把我所知道的羅列一下，以供大家參考：

一、選用優秀的數據庫工具現在的數據庫工具廠家比較多，對海量數據的處理對所使用的數據庫工具要求比較高，一般使用Oracle或者DB2，微軟公司最近發布的SQL Server 2005性能也不錯。另外在BI領域：數據庫，數據倉庫，多維數據庫，數據挖掘等相關工具也要進行選擇，象好的ETL工具和好的OLAP工具都十分必要，例如Informatic，Eassbase等。筆者在實際數據分析項目中，對每天6000萬條的日志數據進行處理，使用SQL Server 2000需要花費6小時，而使用SQL Server 2005則只需要花費3小時。

二、編寫優良的程序代碼處理數據離不開優秀的程序代碼，尤其在進行復雜數據處理時，必須使用程序。好的程序代碼對數據的處理至關重要，這不僅僅是數據處理準確度的問題，更是數據處理效率的問題。良好的程序代碼應該包含好的算法，包含好的處理流程，包含好的效率，包含好的異常處理機制等。

三、對海量數據進行分區操作對海量數據進行分區操作十分必要，例如針對按年份存取的數據，我們可以按年進行分區，不同的數據庫有不同的分區方式，不過處理機制大體相同。例如SQL Server的數據庫分區是將不同的數據存于不同的文件組下，而不同的文件組存于不同的磁盤分區下，這樣將數據分散開，減小磁盤I/O，減小了系統負荷，而且還可以將日志，索引等放于不同的分區下。

四、建立廣泛的索引對海量的數據處理，對大表建立索引是必行的，建立索引要考慮到具體情況，例如針對大表的分組、排序等字段，都要建立相應索引，一般還可以建立復合索引，對經常插入的表則建立索引時要小心，筆者在處理數據時，曾經在一個ETL流程中，當插入表時，首先刪除索引，然后插入完畢，建立索引，并實施聚合操作，聚合完成后，再次插入前還是刪除索引，所以索引要用到好的時機，索引的填充因子和聚集、非聚集索引都要考慮。

五、建立緩存機制當數據量增加時，一般的處理工具都要考慮到緩存問題。緩存大小設置的好差也關系到數據處理的成敗，例如，筆者在處理2億條數據聚合操作時，緩存設置為100000條/Buffer，這對于這個級別的數據量是可行的。

六、加大虛擬內存如果系統資源有限，內存提示不足，則可以靠增加虛擬內存來解決。筆者在實際項目中曾經遇到針對18億條的數據進行處理，內存為1GB，1個P4 2.4G的CPU，對這么大的數據量進行聚合操作是有問題的，提示內存不足，那么采用了加大虛擬內存的方法來解決，在6塊磁盤分區上分別建立了6個4096M的磁盤分區，用于虛擬內存，這樣虛擬的內存則增加為 4096*6 + 1024 = 25600 M，解決了數據處理中的內存不足問題。

七、分批處理 海量數據處理難因為數據量大，那么解決海量數據處理難的問題其中一個技巧是減少數據量。可以對海量數據分批處理，然后處理后的數據再進行合并操作，這樣逐個擊破，有利于小數據量的處理，不至于面對大數據量帶來的問題，不過這種方法也要因時因勢進行，如果不允許拆分數據，還需要另想辦法。不過一般的數據按天、按月、按年等存儲的，都可以采用先分后合的方法，對數據進行分開處理。

八、使用臨時表和中間表數據量增加時，處理中要考慮提前匯總。這樣做的目的是化整為零，大表變小表，分塊處理完成后，再利用一定的規則進行合并，處理過程中的臨時表的使用和中間結果的保存都非常重要，如果對于超海量的數據，大表處理不了，只能拆分為多個小表。如果處理過程中需要多步匯總操作，可按

火龍果?整理 uml.org.cn

匯總步驟一步步來，不要一條語句完成，一口氣吃掉一個胖子。

九、優化查詢SQL語句在對海量數據進行查詢處理過程中，查詢的SQL語句的性能對查詢效率的影響是非常大的，編寫高效優良的SQL腳本和存儲過程是數據庫工作人員的職責，也是檢驗數據庫工作人員水平的一個標準，在對SQL語句的編寫過程中，例如減少關聯，少用或不用游標，設計好高效的數據庫表結構等都十分必要。筆者在工作中試著對1億行的數據使用游標，運行3個小時沒有出結果，這是一定要改用程序處理了。

十、使用文本格式進行處理對一般的數據處理可以使用數據庫，如果對復雜的數據處理，必須借助程序，那么在程序操作數據庫和程序操作文本之間選擇，是一定要選擇程序操作文本的，原因為：程序操作文本速度快；對文本進行處理不容易出錯；文本的存儲不受限制等。例如一般的海量的網絡日志都是文本格式或者csv格式（文本格式），對它進行處理牽扯到數據清洗，是要利用程序進行處理的，而不建議導入數據庫再做清洗。

十一、定制強大的清洗規則和出錯處理機制海量數據中存在著不一致性，極有可能出現某處的瑕疵。例如，同樣的數據中的時間字段，有的可能為非標準的時間，出現的原因可能為應用程序的錯誤，系統的錯誤等，這是在進行數據處理時，必須制定強大的數據清洗規則和出錯處理機制。

十二、建立視圖或者物化視圖視圖中的數據來源于基表，對海量數據的處理，可以將數據按一定的規則分散到各個基表中，查詢或處理過程中可以基于視圖進行，這樣分散了磁盤I/O，正如10根繩子吊著一根柱子和一根吊著一根柱子的區別。

十三、避免使用32位機子（極端情況）目前的計算機很多都是32位的，那么編寫的程序對內存的需要便受限制，而很多的海量數據處理是必須大量消耗內存的，這便要求更好性能的機子，其中對位數的限制也十分重要。

十四、考慮操作系統問題海量數據處理過程中，除了對數據庫，處理程序等要求比較高以外，對操作系統的要求也放到了重要的位置，一般是必須使用服務器的，而且對系統的安全性和穩定性等要求也比較高。尤其對操作系統自身的緩存機制，臨時空間的處理等問題都需要綜合考慮。

十五、使用數據倉庫和多維數據庫存儲數據量加大是一定要考慮OLAP的，傳統的報表可能5、6個小時出來結果，而基于Cube的查詢可能只需要幾分鐘，因此處理海量數據的利器是OLAP多維分析，即建立數據倉庫，建立多維數據集，基于多維數據集進行報表展現和數據挖掘等。

十六、使用采樣數據，進行數據挖掘基于海量數據的數據挖掘正在逐步興起，面對著超海量的數據，一般的挖掘軟件或算法往往采用數據抽樣的方式進行處理，這樣的誤差不會很高，大大提高了處理效率和處理的成功率。一般采樣時要注意數據的完整性和，防止過大的偏差。筆者曾經對1億2千萬行的表數據進行采樣，抽取出400萬行，經測試軟件測試處理的誤差為千分之五，客戶可以接受。還有一些方法，需要在不同的情況和場合下運用，例如使用代理鍵等操作，這樣的好處是加快了聚合時間，因為對數值型的聚合比對字符型的聚合快得多。類似的情況需要針對不同的需求進行處理。海量數據是發展趨勢，對數據分析和挖掘也越來越重要，從海量數據中提取有用信息重要而緊迫，這便要求處理要準確，精度要高，而且處理時間要短，得到有價值信息要快，所以，對海量數據的研究很有前途，也很值得進行廣泛深入的研究。

一般來說第7種方案是最常用的，有的主要就是使用第7種方案，選擇的余地也非常的大，不只是俺月，日，年，也可以按周等等劃分，靈活性較高

而面對大量數據的處理一般都是分批次處理，之前我做一個文本分類器，面對1g多的索引（索引1g多，但是分類時需要的數據就大得多了），40-50分鐘就可以跑完所有分類：

一是分批操作。

二是給jvm回收內存的時間，比如每次20w的數據進行分類，完成之后睡眠一段時間，每睡眠一端時間就手動gc一次。

火龍果?整理 uml.org.cn

通過這些方式取得了很明顯得見效。

海量數據處理專題

（一）大數據量的問題是很多面試筆試中經常出現的問題，比如baidu google 騰訊 這樣的一些涉及到海量數據的公司經常會問到。

下面的方法是我對海量數據的處理方法進行了一個一般性的總結，當然這些方法可能并不能完全覆蓋所有的問題，但是這樣的一些方法也基本可以處理絕大多數遇到的問題。下面的一些問題基本直接來源于公司的面試筆試題目，方法不一定最優，如果你有更好的處理方法，歡迎與我討論。

本貼從解決這類問題的方法入手，開辟一系列專題來解決海量數據問題。擬包含 以下幾個方面。

1.Bloom Filter 2.Hash 3.Bit-Map 4.堆(Heap)5.雙層桶劃分 6.數據庫索引

7.倒排索引（Inverted Index）8.外排序 9.Trie樹 10.MapReduce

在這些解決方案之上，再借助一定的例子來剖析海量數據處理問題的解決方案。歡迎大家關注。

海量數據處理專題

（二）【什么是Bloom Filter】

Bloom Filter是一種空間效率很高的隨機數據結構，它利用位數組很簡潔地表示一個集合，并能判斷一個元素是否屬于這個集合。Bloom Filter的這種高效是有一定代價的：在判斷一個元素是否屬于某個集合時，有可能會把不屬于這個集合的元素誤認為屬于這個集合（false positive）。因此，Bloom Filter不適合那些“零錯誤”的應用場合。而在能容忍低錯誤率的應用場合下，Bloom Filter通過極少的錯誤換取了存儲空間的極大節省。這里有一篇關于Bloom Filter的詳細介紹，不太懂的博友可以看看。

【適用范圍】

可以用來實現數據字典，進行數據的判重，或者集合求交集

【基本原理及要點】

火龍果?整理 uml.org.cn

對于原理來說很簡單，位數組+k個獨立hash函數。將hash函數對應的值的位數組置1，查找時如果發現所有hash函數對應位都是1說明存在，很明顯這 個過程并不保證查找的結果是100%正確的。同時也不支持刪除一個已經插入的關鍵字，因為該關鍵字對應的位會牽動到其他的關鍵字。所以一個簡單的改進就是 counting Bloom filter，用一個counter數組代替位數組，就可以支持刪除了。

還有一個比較重要的問題，如 何根據輸入元素個數n，確定位數組m的大小及hash函數個數。當hash函數個數k=(ln2)*(m/n)時錯誤率最小。在錯誤率不大于E的情況 下，m至少要等于n*lg(1/E)才能表示任意n個元素的集合。但m還應該更大些，因為還要保證bit數組里至少一半為0，則m應 該>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2為底的對數)。

舉個例子我們假設錯誤率為0.01，則此時m應大概是n的13倍。這樣k大概是8個。

注意這里m與n的單位不同，m是bit為單位，而n則是以元素個數為單位(準確的說是不同元素的個數)。通常單個元素的長度都是有很多bit的。所以使用bloom filter內存上通常都是節省的。

【擴展】

Bloom filter將集合中的元素映射到位數組中，用k（k為哈希函數個數）個映射位是否全1表示元素在不在這個集合中。Counting bloom filter（CBF）將位數組中的每一位擴展為一個counter，從而支持了元素的刪除操作。Spectral Bloom Filter（SBF）將其與集合元素的出現次數關聯。SBF采用counter中的最小值來近似表示元素的出現頻率。

【問題實例】

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

根據這個問題我們來計算下內存的占用，4G=2^32大概是40億*8大概是340億，n=50億，如果按出錯率0.01算需要的大概是650億個 bit?，F在可用的是340億，相差并不多，這樣可能會使出錯率上升些。另外如果這些urlip是一一對應的，就可以轉換成ip，則大大簡單了。

海量數據處理專題

（三）什么是Hash

Hash，一般翻譯做“散列”，也有直接音譯為“哈?！钡?，就是把任意長度的輸入（又叫做預映射，pre-image），通過散列算法，變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小于輸入的空間，不同的輸入可能會散列成相同的輸出，而不可能從散列值來唯一的確定輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。

火龍果?整理 uml.org.cn

HASH主要用于信息安全領域中加密算法，它把一些不同長度的信息轉化成雜亂的128位的編碼,這些編碼值叫做HASH值.也可以說，hash就是找到一種數據內容和數據存放地址之間的映射關系。數組的特點是：尋址容易，插入和刪除困難；而鏈表的特點是：尋址困難，插入和刪除容易。那么我們能不能綜合兩者的特性，做出一種尋址容易，插入刪除也容易的數據結構？答案是肯定的，這就是我們要提起的哈希表，哈希表有多種不同的實現方法，我接下來解釋的是最常用的一種方法——拉鏈法，我們可以理解為“鏈表的數組”，如圖：

左邊很明顯是個數組，數組的每個成員包括一個指針，指向一個鏈表的頭，當然這個鏈表可能為空，也可能元素很多。我們根據元素的一些特征把元素分配到不同的鏈表中去，也是根據這些特征，找到正確的鏈表，再從鏈表中找出這個元素。

元素特征轉變為數組下標的方法就是散列法。散列法當然不止一種，下面列出三種比較常用的。1，除法散列法

最直觀的一種，上圖使用的就是這種散列法，公式：

index = value % 16

學過匯編的都知道，求模數其實是通過一個除法運算得到的，所以叫“除法散列法”。

2，平方散列法

求index是非常頻繁的操作，而乘法的運算要比除法來得省時（對現在的CPU來說，估計我們感覺不出

火龍果?整理 uml.org.cn

來），所以我們考慮把除法換成乘法和一個位移操作。公式：

index =(value * value)>> 28

如果數值分配比較均勻的話這種方法能得到不錯的結果，但我上面畫的那個圖的各個元素的值算出來的index都是0——非常失敗。也許你還有個問題，value如果很大，value * value不會溢出嗎？答案是會的，但我們這個乘法不關心溢出，因為我們根本不是為了獲取相乘結果，而是為了獲取index。

3，斐波那契（Fibonacci）散列法

平方散列法的缺點是顯而易見的，所以我們能不能找出一個理想的乘數，而不是拿value本身當作乘數呢？答案是肯定的。

1，對于16位整數而言，這個乘數是40503 2，對于32位整數而言，這個乘數是2654435769

3，對于64位整數而言，這個乘數是***98485

這幾個“理想乘數”是如何得出來的呢？這跟一個法則有關，叫黃金分割法則，而描述黃金分割法則的最經典表達式無疑就是著名的斐波那契數列，如果你還有興趣，就到網上查找一下“斐波那契數列”等關鍵字，我數學水平有限，不知道怎么描述清楚為什么，另外斐波那契數列的值居然和太陽系八大行星的軌道半徑的比例出奇吻合，很神奇，對么？

對我們常見的32位整數而言，公式：

i ndex =(value * 2654435769)>> 28

如果用這種斐波那契散列法的話，那我上面的圖就變成這樣了：

很明顯，用斐波那契散列法調整之后要比原來的取摸散列法好很多。

火龍果?整理 uml.org.cn

【適用范圍】

快速查找，刪除的基本數據結構，通常需要總數據量可以放入內存?！净驹砑耙c】

hash函數選擇，針對字符串，整數，排列，具體相應的hash方法。

碰撞處理，一種是open hashing，也稱為拉鏈法；另一種就是closed hashing，也稱開地址法，opened addressing。

【擴展】

d-left hashing中的d是多個的意思，我們先簡化這個問題，看一看2-left hashing。2-left hashing指的是將一個哈希表分成長度相等的兩半，分別叫做T1和T2，給T1和T2分別配備一個哈希函數，h1和h2。在存儲一個新的key時，同 時用兩個哈希函數進行計算，得出兩個地址h1[key]和h2[key]。這時需要檢查T1中的h1[key]位置和T2中的h2[key]位置，哪一個 位置已經存儲的（有碰撞的）key比較多，然后將新key存儲在負載少的位置。如果兩邊一樣多，比如兩個位置都為空或者都存儲了一個key，就把新key 存儲在左邊的T1子表中，2-left也由此而來。在查找一個key時，必須進行兩次hash，同時查找兩個位置。

【問題實例】

1).海量日志數據，提取出某日訪問百度次數最多的那個IP。

IP的數目還是有限的，最多2^32個，所以可以考慮使用hash將ip直接存入內存，然后進行統計。

海量數據處理專題

（四）【什么是Bit-map】

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

如果說了這么多還沒明白什么是Bit-map，那么我們來看一個具體的例子，假設我們要對0-7內的5個元素(4,7,2,5,3)排序（這里假設這些元素沒有重復）。那么我們就可以采用Bit-map的方法來達到排序的目的。要表示8個數，我們就只需要8個Bit（1Bytes），首先我們開辟1Byte 的空間，將這些空間的所有Bit位都置為0(如下圖：)

火龍果?整理 uml.org.cn

然后遍歷這5個元素，首先第一個元素是4，那么就把4對應的位置為1（可以這樣操作 p+(i/8)|(0x01<<(i%8))當然了這里的操作涉及到Big-ending和Little-ending的情況，這里默認為Big-ending）,因為是從零開始的，所以要把第五位置為一（如下圖）：

然后再處理第二個元素7，將第八位置為1,，接著再處理第三個元素，一直到最后處理完所有的元素，將相應的位置為1，這時候的內存的Bit位的狀態如下：

然后我們現在遍歷一遍Bit區域，將該位是一的位的編號輸出（2，3，4，5，7），這樣就達到了排序的目的。下面的代碼給出了一個BitMap的用法：排序。//定義每個Byte中有8個Bit位 #include ＜memory.h＞ #define BYTESIZE 8 void SetBit(char *p, int posi){

}

void BitMapSortDemo(){

//BufferLen這個值是根據待排序的數據中最大值確定的 //待排序中的最大值是14，因此只需要2個Bytes(16個Bit)//為了簡單起見，我們不考慮負數 int num[] = {3,5,2,10,6,12,8,14,9};*p = *p|(0x01＜＜(posi%BYTESIZE));//將該Bit位賦值1 return;for(int i=0;i ＜(posi/BYTESIZE);i++){ } p++;

火龍果?整理 uml.org.cn

} //就可以了。

const int BufferLen = 2;char *pBuffer = new char[BufferLen];//要將所有的Bit位置為0，否則結果不可預知。memset(pBuffer,0,BufferLen);for(int i=0;i＜9;i++){

} //首先將相應Bit位上置為1 SetBit(pBuffer,num[i]);//輸出排序結果

for(int i=0;i＜BufferLen;i++)//每次處理一個字節(Byte){

} for(int j=0;j＜BYTESIZE;j++)//處理該字節中的每個Bit位 {

} pBuffer++;

//判斷該位上是否是1，進行輸出，這里的判斷比較笨。//首先得到該第j位的掩碼（0x01＜＜j），將內存區中的 //位和此掩碼作與操作。最后判斷掩碼是否和處理后的 //結果相同

if((*pBuffer&(0x01＜＜j))==(0x01＜＜j)){ }

printf(“%d ”,i*BYTESIZE + j);int _tmain(int argc, _TCHAR* argv[]){

} 【適用范圍】 BitMapSortDemo();return 0;

火龍果?整理 uml.org.cn

可進行數據的快速查找，判重，刪除，一般來說數據范圍是int的10倍以下 【基本原理及要點】

使用bit數組來表示某些元素是否存在，比如8位電話號碼 【擴展】

Bloom filter可以看做是對bit-map的擴展 【問題實例】

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，都是一樣的道理。

海量數據處理專題

（五）【什么是堆】

概念：堆是一種特殊的二叉樹，具備以下兩種性質

1）每個節點的值都大于（或者都小于，稱為最小堆）其子節點的值

2）樹是完全平衡的，并且最后一層的樹葉都在最左邊

這樣就定義了一個最大堆。如下圖用一個數組來表示堆：

火龍果?整理 uml.org.cn

那么下面介紹二叉堆：二叉堆是一種完全二叉樹，其任意子樹的左右節點（如果有的話）的鍵值一定比根節點大，上圖其實就是一個二叉堆。

你一定發覺了，最小的一個元素就是數組第一個元素，那么二叉堆這種有序隊列如何入隊呢？看圖：

火龍果?整理 uml.org.cn

假設要在這個二叉堆里入隊一個單元，鍵值為2，那只需在數組末尾加入這個元素，然后盡可能把這個元素往上挪，直到挪不動，經過了這種復雜度為Ο(logn)的操作，二叉堆還是二叉堆。

那如何出隊呢？也不難，看圖：

火龍果?整理 uml.org.cn

出隊一定是出數組的第一個元素，這么來第一個元素以前的位置就成了空位，我們需要把這個空位挪至葉子節點，然后把數組最后一個元素插入這個空位，把這個“空位”盡量往上挪。這種操作的復雜度也是Ο(logn)。

【適用范圍】

海量數據前n大，并且n比較小，堆可以放入內存

【基本原理及要點】

最大堆求前n小，最小堆求前n大。方法，比如求前n小，我們比較當前元素與最大堆里的最大元素，如果它小于最大元素，則應該替換那個最大元 素。這樣最后得到的n個元素就是最小的n個。適合大數據量，求前n小，n的大小比較小的情況，這樣可以掃描一遍即可得到所有的前n元素，效率很高。

【擴展】

雙堆，一個最大堆與一個最小堆結合，可以用來維護中位數。

【問題實例】

1)100w個數中找最大的前100個數。

用一個100個元素大小的最小堆即可。

海量數據處理專題

（六）火龍果?整理 uml.org.cn

【什么是雙層桶】

事實上，與其說雙層桶劃分是一種數據結構，不如說它是一種算法設計思想。面對一堆大量的數據我們無法處理的時候，我們可以將其分成一個個小的單元，然后根據一定的策略來處理這些小單元，從而達到目的。

【適用范圍】

第k大，中位數，不重復或重復的數字

【基本原理及要點】

因為元素范圍很大，不能利用直接尋址表，所以通過多次劃分，逐步確定范圍，然后最后在一個可以接受的范圍內進行?？梢酝ㄟ^多次縮小，雙層只是一個例子，分治才是其根本（只是“只分不治”）。

【擴展】

當有時候需要用一個小范圍的數據來構造一個大數據，也是可以利用這種思想，相比之下不同的，只是其中的逆過程。

【問題實例】

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

有點像鴿巢原理，整數個數為2^32,也就是，我們可以將這2^32個數，劃分為2^8個區域(比如用單個文件代表一個區域)，然后將數據分離到不同的區域，然后不同的區域在利用bitmap就可以直接解決了。也就是說只要有足夠的磁盤空間，就可以很方便的解決。當然這個題也可以用我們前面講過的BitMap方法解決，正所謂條條大道通羅馬~~~ 2).5億個int找它們的中位數。

這個例子比上面那個更明顯。首先我們將int劃分為2^16個區域，然后讀取數據統計落到各個區域里的數的個數，之后我們根據統計結果就可以判斷中位數落到那個區域，同時知道這個區域中的第幾大數剛好是中位數。然后第二次掃描我們只統計落在這個區域中的那些數就可以了。

實際上，如果不是int是int64，我們可以經過3次這樣的劃分即可降低到可以接受的程度。即可以先將int64分成2^24個區域，然后確定區域的第幾 大數，在將該區域分成2^20個子區域，然后確定是子區域的第幾大數，然后子區域里的數的個數只有2^20，就可以直接利用direct addr table進行統計了。

3).現在有一個0-30000的隨機數生成器。請根據這個隨機數生成器，設計一個抽獎范圍是0-350000彩票中獎號碼列表，其中要包含20000個中獎號碼。

這個題剛好和上面兩個思想相反，一個0到3萬的隨機數生成器要生成一個0到35萬的隨機數。那么我們完全可以將0-35萬的區間分成35/3=12個區間，然后每個區間的長度都小于等于3萬，這樣我們就可以用題目給的隨機數生成器來生成了，然后再加上該區間的基數。那么要每個區間生成多少個隨機數呢？計算公式就是：區間長度*隨機數密度，在本題目中就是30000*（20000/350000）。最后要注意一點，該題目是有隱含條件的：彩票，這意味著你生成的隨機數里面不能有重復，這也是我為什么用雙層桶劃分思想的另外一個原因。

第二篇：常用大數據量、海量數據處理方法 (算法)總結

? 大數據量的問題是很多面試筆試中經常出現的問題，比如baidu google 騰訊 這樣的一些涉及到海量數據的公司經常會問到。

下面的方法是我對海量數據的處理方法進行了一個一般性的總結，當然這些方法可能并不能完全覆蓋所有的問題，但是這樣的一些方法也基本可以處理絕大多數遇到的問題。下面的一些問題基本直接來源于公司的面試筆試題目，方法不一定最優，如果你有更好的處理方法，歡迎與我討論。

1.Bloom filter

適用范圍：可以用來實現數據字典，進行數據的判重，或者集合求交集

基本原理及要點：

對于原理來說很簡單，位數組+k個獨立hash函數。將hash函數對應的值的位數組置1，查找時如果發現所有hash函數對應位都是1說明存在，很明顯這個過程并不保證查找的結果是100%正確的。同時也不支持刪除一個已經插入的關鍵字，因為該關鍵字對應的位會牽動到其他的關鍵字。所以一個簡單的改進就是 counting Bloom filter，用一個counter數組代替位數組，就可以支持刪除了。

還有一個比較重要的問題，如何根據輸入元素個數n，確定位數組m的大小及hash函數個數。當hash函數個數k=(ln2)*(m/n)時錯誤率最小。在錯誤率不大于E的情況下，m至少要等于n*lg(1/E)才能表示任意n個元素的集合。但m還應該更大些，因為還要保證bit數組里至少一半為0，則m應該>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2為底的對數)。

舉個例子我們假設錯誤率為0.01，則此時m應大概是n的13倍。這樣k大概是8個。

注意這里m與n的單位不同，m是bit為單位，而n則是以元素個數為單位(準確的說是不同元素的個數)。通常單個元素的長度都是有很多bit的。所以使用bloom filter內存上通常都是節省的。

擴展：

Bloom filter將集合中的元素映射到位數組中，用k（k為哈希函數個數）個映射位是否全1表示元素在不在這個集合中。Counting bloom filter（CBF）將位數組中的每一位擴展為一個counter，從而支持了元素的刪除操作。Spectral Bloom Filter（SBF）將其與集合元素的出現次數關聯。SBF采用counter中的最小值來近似表示元素的出現頻率。

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

根據這個問題我們來計算下內存的占用，4G=2^32大概是40億*8大概是340億，n=50億，如果按出錯率0.01算需要的大概是650億個bit。現在可用的是340億，相差并不多，這樣可能會使出錯率上升些。另外如果這些urlip是一一對應的，就可以轉換成ip，則大大簡單了。

2.Hashing

適用范圍：快速查找，刪除的基本數據結構，通常需要總數據量可以放入內存

基本原理及要點：

hash函數選擇，針對字符串，整數，排列，具體相應的hash方法。

碰撞處理，一種是open hashing，也稱為拉鏈法；另一種就是closed hashing，也稱開地址法，opened addressing。

擴展：

d-left hashing中的d是多個的意思，我們先簡化這個問題，看一看2-left hashing。2-left hashing指的是將一個哈希表分成長度相等的兩半，分別叫做T1和T2，給T1和T2分別配備一個哈希函數，h1和h2。在存儲一個新的key時，同時用兩個哈希函數進行計算，得出兩個地址h1[key]和h2[key]。這時需要檢查T1中的h1[key]位置和T2中的h2[key]位置，哪一個位置已經存儲的（有碰撞的）key比較多，然后將新key存儲在負載少的位置。如果兩邊一樣多，比如兩個位置都為空或者都存儲了一個key，就把新key 存儲在左邊的T1子表中，2-left也由此而來。在查找一個key時，必須進行兩次hash，同時查找兩個位置。

問題實例：

1).海量日志數據，提取出某日訪問百度次數最多的那個IP。

IP的數目還是有限的，最多2^32個，所以可以考慮使用hash將ip直接存入內存，然后進行統計。

3.bit-map

適用范圍：可進行數據的快速查找，判重，刪除，一般來說數據范圍是int的10倍以下

基本原理及要點：使用bit數組來表示某些元素是否存在，比如8位電話號碼

擴展：bloom filter可以看做是對bit-map的擴展

問題實例：

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

8位最多99 999 999，大概需要99m個bit，大概10幾m字節的內存即可。

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

將bit-map擴展一下，用2bit表示一個數即可，0表示未出現，1表示出現一次，2表示出現2次及以上。或者我們不用2bit來進行表示，我們用兩個bit-map即可模擬實現這個2bit-map。

4.堆

適用范圍：海量數據前n大，并且n比較小，堆可以放入內存

基本原理及要點：最大堆求前n小，最小堆求前n大。方法，比如求前n小，我們比較當前元素與最大堆里的最大元素，如果它小于最大元素，則應該替換那個最大元素。這樣最后得到的n個元素就是最小的n個。適合大數據量，求前n小，n的大小比較小的情況，這樣可以掃描一遍即可得到所有的前n元素，效率很高。

擴展：雙堆，一個最大堆與一個最小堆結合，可以用來維護中位數。

問題實例：

1)100w個數中找最大的前100個數。

用一個100個元素大小的最小堆即可。

5.雙層桶劃分

適用范圍：第k大，中位數，不重復或重復的數字

基本原理及要點：因為元素范圍很大，不能利用直接尋址表，所以通過多次劃分，逐步確定范圍，然后最后在一個可以接受的范圍內進行?？梢酝ㄟ^多次縮小，雙層只是一個例子。

擴展：

問題實例：

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

有點像鴿巢原理，整數個數為2^32,也就是，我們可以將這2^32個數，劃分為2^8個區域(比如用單個文件代表一個區域)，然后將數據分離到不同的區域，然后不同的區域在利用bitmap就可以直接解決了。也就是說只要有足夠的磁盤空間，就可以很方便的解決。

2).5億個int找它們的中位數。

這個例子比上面那個更明顯。首先我們將int劃分為2^16個區域，然后讀取數據統計落到各個區域里的數的個數，之后我們根據統計結果就可以判斷中位數落到那個區域，同時知道這個區域中的第幾大數剛好是中位數。然后第二次掃描我們只統計落在這個區域中的那些數就可以了。

實際上，如果不是int是int64，我們可以經過3次這樣的劃分即可降低到可以接受的程度。即可以先將int64分成2^24個區域，然后確定區域的第幾大數，在將該區域分成2^20個子區域，然后確定是子區域的第幾大數，然后子區域里的數的個數只有2^20，就可以直接利用direct addr table進行統計了。

6.數據庫索引

適用范圍：大數據量的增刪改查

基本原理及要點：利用數據的設計實現方法，對海量數據的增刪改查進行處理。

擴展：

問題實例：

7.倒排索引(Inverted index)

適用范圍：搜索引擎，關鍵字查詢

基本原理及要點：為何叫倒排索引？一種索引方法，被用來存儲在全文搜索下某個單詞在一個文檔或者一組文檔中的存儲位置的映射。

以英文為例，下面是要被索引的文本：

T0 = “it is what it is” T1 = “what is it”

T2 = “it is a banana”

我們就能得到下面的反向文件索引：

“a”: {2} “banana”: {2} “is”: {0, 1, 2} “it”: {0, 1, 2} “what”: {0, 1}

檢索的條件“what”, “is” 和 “it” 將對應集合的交集。

正向索引開發出來用來存儲每個文檔的單詞的列表。正向索引的查詢往往滿足每個文檔有序頻繁的全文查詢和每個單詞在校驗文檔中的驗證這樣的查詢。在正向索引中，文檔占據了中心的位置，每個文檔指向了一個它所包含的索引項的序列。也就是說文檔指向了它包含的那些單詞，而反向索引則是單詞指向了包含它的文檔，很容易看到這個反向的關系。

擴展：

問題實例：文檔檢索系統，查詢那些文件包含了某單詞，比如常見的學術論文的關鍵字搜索。

8.外排序

適用范圍：大數據的排序，去重

基本原理及要點：外排序的歸并方法，置換選擇 敗者樹原理，最優歸并樹

擴展：

問題實例：

1).有一個1G大小的一個文件，里面每一行是一個詞，詞的大小不超過16個字節，內存限制大小是1M。返回頻數最高的100個詞。

這個數據具有很明顯的特點，詞的大小為16個字節，但是內存只有1m做hash有些不夠，所以可以用來排序。內存可以當輸入緩沖區使用。

9.trie樹

適用范圍：數據量大，重復多，但是數據種類小可以放入內存

基本原理及要點：實現方式，節點孩子的表示方式

擴展：壓縮實現。

問題實例：

1).有10個文件，每個文件1G，每個文件的每一行都存放的是用戶的query，每個文件的query都可能重復。要你按照query的頻度排序。

2).1000萬字符串，其中有些是相同的(重復),需要把重復的全部去掉，保留沒有重復的字符串。請問怎么設計和實現？

3).尋找熱門查詢：查詢串的重復度比較高，雖然總數是1千萬，但如果除去重復后，不超過3百萬個，每個不超過255字節。

10.分布式處理 mapreduce

適用范圍：數據量大，但是數據種類小可以放入內存

基本原理及要點：將數據交給不同的機器去處理，數據劃分，結果歸約。

擴展：

問題實例：

1).The canonical example application of MapReduce is a process to count the appearances of

each different word in a set of documents: void map(String name, String document):

// name: document name

// document: document contents

for each word w in document:

EmitIntermediate(w, 1);

void reduce(String word, Iterator partialCounts):

// key: a word

// values: a list of aggregated partial counts

int result = 0;

for each v in partialCounts:

result += ParseInt(v);

Emit(result);

Here, each document is split in words, and each word is counted initially with a “1” value by

the Map function, using the word as the result key.The framework puts together all the pairs

with the same key and feeds them to the same call to Reduce, thus this function just needs to

sum all of its input values to find the total appearances of that word.2).海量數據分布在100臺電腦中，想個辦法高效統計出這批數據的TOP10。

3).一共有N個機器，每個機器上有N個數。每個機器最多存O(N)個數并對它們操作。如何找到N^2個數的中數(median)？

經典問題分析

上千萬or億數據（有重復），統計其中出現次數最多的前N個數據,分兩種情況：可一次讀入內存，不可一次讀入。

可用思路：trie樹+堆，數據庫索引，劃分子集分別統計，hash，分布式計算，近似統計，外排序

所謂的是否能一次讀入內存，實際上應該指去除重復后的數據量。如果去重后數據可以放入內存，我們可以為數據建立字典，比如通過 map，hashmap，trie，然后直接進行統計即可。當然在更新每條數據的出現次數的時候，我們可以利用一個堆來維護出現次數最多的前N個數據，當然這樣導致維護次數增加，不如完全統計后在求前N大效率高。

如果數據無法放入內存。一方面我們可以考慮上面的字典方法能否被改進以適應這種情形，可以做的改變就是將字典存放到硬盤上，而不是內存，這可以參考數據庫的存儲方法。

當然還有更好的方法，就是可以采用分布式計算，基本上就是map-reduce過程，首先可以根據數據值或者把數據hash(md5)后的值，將數據按照范圍劃分到不同的機子，最好可以讓數據劃分后可以一次讀入內存，這樣不同的機子負責處理各種的數值范圍，實際上就是map。得到結果后，各個機子只需拿出各自的出現次數最多的前N個數據，然后匯總，選出所有的數據中出現次數最多的前N個數據，這實際上就是reduce過程。

實際上可能想直接將數據均分到不同的機子上進行處理，這樣是無法得到正確的解的。因為一個數據可能被均分到不同的機子上，而另一個則可能完全聚集到一個機子上，同時還可能存在具有相同數目的數據。比如我們要找出現次數最多的前100個，我們將1000萬的數據分布到10臺機器上，找到每臺出現次數最多的前 100個，歸并之后這樣不能保證找到真正的第100個，因為比如出現次數最多的第100個可能有1萬個，但是它被分到了10臺機子，這樣在每臺上只有1千個，假設這些機子排名在1000個之前的那些都是單獨分布在一臺機子上的，比如有1001個，這樣本來具有1萬個的這個就會被淘汰，即使我們讓每臺機子選出出現次數最多的1000個再歸并，仍然會出錯，因為可能存在大量個數為1001個的發生聚集。因此不能將數據隨便均分到不同機子上，而是要根據hash 后的值將它們映射到不同的機子上處理，讓不同的機器處理一個數值范圍。

而外排序的方法會消耗大量的IO，效率不會很高。而上面的分布式方法，也可以用于單機版本，也就是將總的數據根據值的范圍，劃分成多個不同的子文件，然后逐個處理。處理完畢之后再對這些單詞的及其出現頻率進行一個歸并。實際上就可以利用一個外排序的歸并過程。

另外還可以考慮近似計算，也就是我們可以通過結合自然語言屬性，只將那些真正實際中出現最多的那些詞作為一個字典，使得這個規模可以放入內存。

第三篇：數據處理和電子表格軟件教案

“數據處理和電子表格軟件”教學設計

【適用年級】 初二年級第二學期 【適用單元】 電子表格軟件第1節 【教學目標】 ●知識目標

（1）熟悉EXCEL窗口。

（2）理解工作簿、工作表、單元格概念。（3）掌握建立、保存、關閉工作簿的操作。（4）掌握工作表、單元格的基本操作。●技能目標

通過學生探究學習過程中，掌握EXCEL窗口中幾個的基本操作?！袂楦心繕?/p>

（1）通過動手實踐，培養學生在學習過程中自主探究、對比、舉一反三的學習能力；

（2）利用知識的遷移，培養學生的綜合信息素養能力?！菊n時安排】2課時（兩節連上）【教學重點與難點】

（1）重點：工作簿、工作表、單元格概念。（2）難點：掌握工作表、單元格的基本操作?！窘虒W方法】對比法、任務驅動法 【課前準備】軟件EXCEL 【教學設計】

教學過程 教師活動 學生活動 教學意圖

引入新課

大家打開書本的目錄看本書要學習什么內容？目錄中大家看到的黑體字是——用計算機處理數據，計算機能處理什么樣的數據呢？ 觀察本書目錄

讓學生了解這本書我們將要學習哪些內容？（培養學生每學習一本書前先了解所學內容大概的習慣）

閱讀思考

大家打開課本P2—P3了解以下問題：

1、什么是信息？什么是數據？兩者有聯系嗎？

2、什么是數據處理？數據處理使用到哪些軟件？

3、說說EXCEL軟件的功能？ 閱讀教材

說說自己的理解

培養學生利用閱讀獲取知識的習慣

區別與拓展

大家看第2頁后，看這（教師指黑板）它告訴你什么樣的信息？

黑板是色彩和形狀這些信息表現出來的，生活中每樣東西都有自己的信息如我們每一位都自己的信息：姓名、身高、衣著等，因此信息是廣義的，表現信息叫數據，如色彩、長寬都是數據，同理數據也是一個廣義的概念，包括數值、文字、圖像等一些。如何處理這些數據是我們所關心的，課本中提到什么樣軟件？ 引導學生說說閱讀P3后對EXCEL知道了多少？

黑色的、有長和寬的黑板 EXCEL 學生積極發言 設疑激趣 拓展知識面

讓學生表達自己的看法，展示自己的空間

任務驅動

大家說了這么多了，看看EXCEL是什么樣的？閱讀課本P4—P6，認識EXCEL窗口，并在計算機中實踐，同時比較與WORD窗口不同處 學生實踐

培養學生自主探究和對比學習的能力

學生演示 請發現不同處的學生在教師機上展示 觀察

知識鞏固

設置障礙

教師不小心關閉文件窗口，只剩下軟件平臺，問怎么辦？

學生說，教師操作

知識遷移到工作簿的新建、保存操作上。

引入新問題

在了解窗口時提到了Sheet工作表，這兒怎么又是工作簿，還有單元格，這三者都有些混了，怎么區分它呢？ 教師操作并講解??

看課本P9回答：一個工作表中能有多少個單元格呢？ 單元格、當前單元格、單元格區域怎樣區分呢？ 教師操作并講解??

觀察區別概念

答（行：256列65536表格）觀察區別概念

讓學生正確區別工作簿、工作表、單元格概念

正確區別單元格、當前單元格、單元格區域概念

任務驅動

了解單元格后，結合課本P10—P12完成P15練習4、5、6題

學生實踐

以單元格的練習促進學生自主學習單元格的操作

教師小結并處理練習問題

一、單元格的選定操作及地址表示：

1、單個（一個）單元格

2、連續單元格區域

3、整行或整列

4、不連續單元格區域

觀察

總結知識點

任務驅動

P16的練習7，它主要是對工作表進行的操作，可結合課本P13—P14完成練習學生實踐

以工作表的練習促進學生自主學習工作表操作

輔導并檢查作業

重點檢查工作表的復制操作 如何同時復制多個工作表？

知識舉一反三

學生總結本課知識 這節課你學到了什么？

教學后記

這節課教師引導，學生自主學習充分體現出來，我上本節課的成功之處有以下幾點。

1．以練習促學：布置練習完成單元格及工作表的學習，在學習的過程中所有的學生都在積極看書或互相交流，沒有看到學生“等著吃”的現象，這種積極的心態也感染了我，同時在處理練習時學生有自己的表現方式，如練習4中的地址，他地址輸入到相應的單元格中，既直觀又好理解；在練習7中的操作使用多種不同方法是我沒有料想到的。這是我嘗試調動學生自主學習的方法的一種，我認為比較成功，今后也可以推廣的方法。

2．設置問題障礙：使學生積極主動解決問題，情趣高、效果比較好，知識遷移比較巧妙。

3．區別與拓展：對“信息”與“數據”知識的拓展比較滿意，擴大學生對抽象概念的理解。

4．通過找不同學習EXCEL窗口時，隨機說了幾道題如234+548＝256*652＝的計算題讓學生找不同并用它解決這個計算問題，學生通過自己發現很容易記住“編輯公式＝”的用法，這對今后數據處理有很大的用處。5．內容銜接比較緊湊。不足之處有以下幾點。

1．“信息與數據”知識的拓展時間掌握不好會影響下面知識的進展速度。2．“了解EXCEL窗口，并區別與WORD窗口不同處”學生實踐區別完成后，學生講解與展示時間太長也影響進度，在另一個班我進行對比區別，讓學生和我的進行比較，注意自己沒有發現的，這樣效果比較好。

第四篇：火龍果軟件-UMLATM設計文檔

火龍果?整理 uml.org.cn

UML實驗報告

2.用例建模

掌握客戶需求分析的方法和步驟 了解以用例驅動的軟件開發方法 掌握用例圖的畫法

掌握用Rose或PowerDesigner進行用例建模的具體方法和步驟

1.ATM系統用例圖:

存款現金管理取款客戶修改密碼銀行管理員維護ATM設備轉賬余額查詢

2.這個ATM系統主要顯示了對客戶提供存取款，轉賬，余額查詢和密碼修改的功能，以及銀行管理員對客戶修改密碼，現金和ATM設備維護的操作。3.描述用例 “取款”用例 用例編號：0671 用例名：轉賬 執行者：.人執行者：客戶

.系統執行者：取款子系統 目的：執行取款任務 類型：端點 主要的 基本的 級別：一級 過程描述： 1.插卡

2.輸入密碼

3.輸入取款金額確定

4.取款打印憑條

5.退出系統 “查詢”用例 用例編號：0670

火龍果?整理 uml.org.cn

用例名：查詢賬戶 執行者：.人執行者：客戶

.系統執行者：查詢子系統 目的：執行查詢任務 類型：端點 主要的 基本的 級別：一級 過程描述： 1.插卡

2.輸入密碼

3.查詢賬號

4.人名幣查詢

5.查詢打印憑條

6.退出系統

“修改密碼”用例 用例編號：0669 用例名：修改密碼 執行者：

.人執行者：客戶、銀行工作人員.系統執行者：修改密碼子系統 目的：執行修改密碼任務 類型：端點 主要的 基本的 級別：一級 過程描述：1.插卡

2.輸入密碼

3.修改密碼

4.輸入新密碼

5.再次輸入新密碼

6.修改成功退出系統

“轉賬”用例 用例編號：0668 用例名：轉賬 執行者：.人執行者：客戶

.系統執行者：轉賬子系統 目的：執行轉賬任務 類型：端點 主要的 基本的 級別：一級 過程描述：1.插卡。

2.輸入密碼。

3.進入轉賬界面。

4.輸入轉入卡號或賬號（只能同行轉賬）。

5.再次輸入卡號或賬號。

火龍果?整理 uml.org.cn

6.輸入轉入金額確定。

7.退出系統 “現金管理”用例 用例編號：0667 用例名：現金管理 執行者：

.人執行者：銀行管理員.系統執行者：現金管理子系統 目的：執行現金管理任務 類型：端點 主要的 基本的 級別：一級

過程描述： 1.進入銀行系統

2.進行添加現金操作

3.退出系統 “維護ATM設備”用例 用例編號：0667 用例名：維護ATM設備 執行者：

.人執行者：銀行管理員

.系統執行者：維護ATM設備子系統 目的：執行現金管理任務 類型：端點 主要的 基本的 級別：一級

過程描述： 1.進入銀行系統

2.對ATM設備進行檢查

3.對ATM設備進行相應維護

4.退出系統

3.活動圖建模

了解活動圖建模的概念

掌握描述一個操作執行過程中所完成工作（動作）的方法 掌握描述對象內部工作的具體步驟

ATM取款子系統活動圖：

火龍果?整理 uml.org.cn 客戶需求分析規格說明書/系統分析規格說明書

了解用包模型來描述系統體系結構（用例模型）的方法 掌握用Rose或PowerDesigner進行包圖建模的具體方法和步驟

火龍果?整理 uml.org.cn

掌握書寫客戶需求規格說明書的基本格式

5.類建模

? 對象類建模

理解面向對象系統分析和對象類建模的概念 了解和掌握面向對象系統分析的方法和步驟 了解和掌握尋找待開發系統中類的方法和技巧 掌握使用Rose或PowerDesigner建立類模型的方法

? 類的繼承建模

理解類之間的繼承關系

了解和掌握分析類之間繼承關系的方法

掌握使用Rose或PowerDesigner建立類之間繼承關系模型的過程

? 對象類關聯關系建模

理解面向對象類之間關聯關系的概念 了解和掌握分析類之間的關聯關系的方法

了解和掌握待開發系統中類之間關聯關系的分析方法

掌握使用Rose或PowerDesigner如何對關聯關系進行建模的過程

許多單個的帳戶組成了帳戶庫。帳戶具有帳戶類型、帳戶號、余額三個屬性，均為private，其類型分別為char，int，double。六個操作分別為setType、getType、getAccountNumbe、setAccountNumbe、caculateBalance、getBalance，除caculateBalance為protected其余均為public。

setType設置帳戶類型，返回類型為void，參數類型為char，輸入帳戶類型。

getType獲取帳戶類型，返回類型為char，無參數。

setAccountNumbe設置帳戶號，返回類型為void，參數類型為int，輸入帳戶號。

getAccountNumbe獲取帳戶號，返回類型為int，無參數。

caculateBalance計算余額，返回類型為void，參數為double，第一個參數為輸入存取款數額，第二個參數為存款余額，既為輸入也為輸出。

getBalance獲取帳戶余額，返回類型為double，無參數。

許多銀行儲戶組成了儲戶庫。ATM系統包含了許多ATM機。銀行儲戶及ATM機兩個類包含哪些屬性，哪些操作，它們的可見性及操作的返回類型、參數個數、參數類型從類圖上都一目了然。更多的屬性及操作都可以一一加上，使這個類圖更詳細更完整，從而使參與項目的每個成員都能無歧義的明了整個設計的類的結構。同樣對于一個真正的銀行系統，這個類圖過于簡單。比如帳戶類型我們可以先定義一個abstract class，它包含一個帳戶最基本的屬性及操作。而有些操作先定義為abstract，如余額的計算。然后再繼承這個abstract class，我們可以有saving account 和checking account等等。不同的帳戶有不同的余額計算方法，我們可以加上具體的算法。對于不同的帳戶可能還有一些它特有的操作，我們也可以加上，比如saving account在存款達到多少時可以享受機票打折的優惠。

對象類關聯關系圖：

火龍果?整理 uml.org.cn

銀行0..10..10..*0..10..1賬號庫0..*銀行儲戶庫ATM系統0..10..10..10..*賬戶---++++++賬戶類型: char賬戶號·: int余額: DoublesetType()getType()setAccountNumbe()getAccountNumbe()caculateBalance()getBalance()0..*1..*銀行儲戶: char: char: void: int: Double: Double---+++用戶姓名: int用戶ID: int用戶密碼: int存錢(): int取錢(): int其他操作(): intATM機0..*0..*-+++ATM機ID: int收款(): int吐款(): int其他服務(): int1..*0..1 順序圖建模

理解順序圖的基本概念

了解和掌握軟件工程中用例邏輯時序的分析方法 了解和掌握待開發系統中順序圖的設計和實現 掌握使用Rose或PowerDesigner創建順序圖的方法

下圖描述了顧客在ATM機上取款時信息的流動情況。以時間為順序。因為僅是示例，所以整個過程是沒有出現任何故障時的流程，并且只畫到了取款結束。通過這個圖，我們可以看出消息是如何在系統中不同對象之間進行交互。

通過流程圖我們可以很清楚地看到系統是如何工作的，系統各部分之間的信息及控制是如何發送的，整個流程是否合理。流程圖對我們的設計起到了很好的幫助作用。注意在本圖沒有一個生命線終端有一個“X”，這是因為這個流程中還未遇到有對象生命結束。當有對象生命結束時需在對應的生命線終端畫“X”，表明這個對象在這時被銷毀。

首先銀行儲戶將ATM卡插入讀卡機，讀卡機將信息傳給客戶管理，客戶管理提出查詢密碼，顯示部分將輸入密碼請求顯示出來…..ATM取款順序圖 ：

火龍果?整理 uml.org.cn

順序客戶讀卡器顯示設備輸入設備ATM數據庫點鈔機銀行數據庫插入ATM卡接受ATM卡顯示輸入密碼請求查詢密碼輸入密碼密碼傳遞請求確認密碼合法性詢問服務類別顯示輸入服務類別請求輸入取款請求取款請求確認密碼合法性詢問取款數額顯示輸入數額請求輸入取款數額傳遞取款數額顯示確認數額請求詢問取款數額確認確認輸入傳遞確認信息數額合法性確認請求確認數額合法性出鈔請求出鈔取鈔詢問是否打印憑條顯示詢問是否打印憑條確定請求退出取出ATM卡 火龍果?整理 uml.org.cn 合作圖建模

了解合作圖的概念及其在系統設計中的作用 掌握兩種交互圖（順序圖和合作圖）的差別 熟悉和掌握合作圖案例的分析方法

掌握使用Rose或PowerDesigner依據用例繪制合作圖

合作圖和順序圖是可以無信息損失的相互轉換，只是它們的側重點是不一樣的。順序圖著重于對象間消息傳遞的時間順序，合作圖著重于表達對象之間的靜態連接關系。下圖將順序圖轉換為合作圖。

ATM系統協作圖 ：

1．插入ATM卡

2．接受ATM卡

3．查詢密碼

4．顯示輸入密碼請求

5．輸入密碼

6．密碼傳遞

7．請求確認密碼合法性

8．確認密碼合法性

9．詢問服務類別

10．顯示輸入服務服務類別請求

11．輸入取款請求

12．取款請求

13．詢問取款數額

14．顯示輸入數額請求

15．輸入取款數額

16．傳遞取款數額

17．詢問取款數額確認

火龍果?整理 uml.org.cn

18．顯示確認數額請求

19．輸入確認

20．傳遞確認信息

21．數額合法性確認請求

22．確認數額和法性

23．出鈔請求

24．計算帳戶余額

25．出鈔

26．取鈔

27．傳遞余額并詢問是否還需要其他服務

28．顯示帳戶余額并提示選擇下面的服務 狀態圖建模

了解狀態圖的概念及其在系統設計中的作用

掌握使用Rose或PowerDesigner依據用例繪制對象的狀態圖

下圖描述了顧客在ATM機上進行操作會經歷的幾種狀態，及各種狀態之間轉換的條件。因為是簡化了的例子，所以除了等待顧客插入磁卡的起始狀態和結束服務的終止狀態，顧客會處于輸入密碼、選擇服務類型、存款及取款四種狀態。

ATM狀態圖：

插入磁卡后進入輸密碼狀態，當密碼輸入正確時進入選擇服務類型狀態，當輸入密碼不正確時，停留在原狀態，但如果三次不正確，服務結束。進入選擇服務類型后根據選擇的不同，顧客可進入存款和取款狀態。存、取款結束后，顧客既可以選擇結束服務到最終狀態，也可以選擇繼續服務回到選擇服務類型狀態。

通過狀態圖我們可以無歧義的了解各個活動角色是如何在不同狀況下轉換的，轉換的條件是什么，是否會出現死鎖現象，是否有條件沒考慮周全，是否有狀態無法達到。狀態圖可以幫助我們發現問題，并及時改正。構件圖建模

了解系統物理體系結構模型和表示方法 了解構件圖建模的概念及其在系統設計中的作用 掌握使用Rose或PowerDesigner繪制構件圖

火龍果?整理 uml.org.cn 部署圖建模

了解系統物理體系結構模型和表示方法 了解部署圖的概念及其在系統設計中的作用 掌握使用Rose或PowerDesigner繪制部署圖的方法

第五篇：海量閱讀課題實施小結

一學期教七本書不是神話

一學期教七本書不是神話

?？h第二實驗小學

張連鋒

教書育人是教師的天職，教書是手段，育人是目的。學校教育就是要為社會培養合格公民和優秀人才?？墒沁@些年來，我們大多情況下熟練地運用教書的手段，明爭暗賽的培養著機械考試的高手，造成了嚴重的兩極分化，普遍的厭學現象和道德滑坡。我們迷失在應試考試之中，忘記了育人的目的。怎樣回歸育人之道？《義務教育語文課程標準》要求：“要重視培養學生廣泛的閱讀興趣，擴大閱讀面，增加閱讀量，提高閱讀品位，提倡少做題，多讀書，好讀書，讀好書，讀整本的書。”著名教育家蘇霍姆林斯基說過：“應該讓孩子生活在書籍的世界里”。作家格林說過：“讀書是世界上門檻最低的高貴行為”、“只有童年讀的書，才會對人生產生深刻的影響”。我國著名學者、書香校園的首倡者朱永新先生在微博中則說：“沒有閱讀，就沒有學生的精神成長”。而北大陳平原教授則認為：一輩子的道路決定于語文。真正的語文教育必須擴大閱讀面，增加閱讀量，去引導學生“讀整本的書”。我們無論在課內還是課外都應該擴大孩子們的閱讀量。

在本學期，我們課題組研究“課內外海量閱讀”實驗，我利用一切課堂時間，總共學習了七本書，具體做法如下：

一、化零為整，每天循序漸進

我們學校每天八點到八點二十有二十分鐘的早讀課，一般都是讓學生熟悉課文的。而這個時間被我“公款私用”了，每天分享一首詩，有時候是現代詩，有時候是外國的優秀詩篇，有時候是與節氣或者節日，或者單元主題有關的古詩，每天領著孩子們讀詩，賞詩，背詩，也是“別有一番滋味在心頭”。后來，發現了徐冬梅，薛瑞萍老師主編的《日有所誦》，如獲至寶，從此，它成了我們早讀課的主角。每天二十分鐘，孩子們收獲的不止一點點課外知識。

二、固定時間，養成習慣

陽光體育的時候，我們學校每個班的體育變成了三節。后來由于教師不夠，每個班的一節體育課由班主任來上。由于基本的體育技能管體育的老師基本上都交過了，所以這一節課，我跟孩子們商量后又挪作他用了?！端渍Z兒歌100首》是一首簡單易懂，道理簡單的書，這節課每次抄五首，孩子們邊抄邊問，不認識的字查字典，不理解的就商量，商量完就背，背過了就說，說一句話或者一段話，用上今天所學習的俗語，這樣學、背、用，一堂課基本上可以完成。有些當堂沒有辦法完成的，就當做課下作業，并聯絡家長一起督促。這樣在孩子的生活中，遇到合適的情境，孩子們總是能說出一些有關的俗語，給別人出口成章的感覺，得到了別人的認可，孩子們學的盡頭更大了。

三、整合資源，為我所用

國學經典走進課堂，給孩子們種植文化底蘊。《弟子規》《百家姓》《論語》《孟子》等紛紛走進各年級的課堂。《中華經典誦讀》這套教材編的非常好，原文下面有注釋，注釋下面有譯文，譯文下面有故事鏈接。孩子們完全可以通過自己的用心閱讀來理解，內化，吸收。我們這學期學的是《孟子》，孩子們已經不單單滿足于每周五的閱讀課來閱讀這本書，放學后，吃飯余，他們都廢寢忘食的讀著。后來，他們紛紛找我說希望閱讀更多的經典，于是我把課題組里其他班級的《增廣賢文》借過來發到班里，孩子們如饑似渴的讀起來。這樣，我們用了同樣的時間讀了兩本經典誦讀，孩子們都滿足而驕傲的說：“我們無法決定時間的長度，但我們拓寬了它的寬度?！?/p>

四、課本主角，力求詳解

很多人勸我說：“課本是最基本的，一定要讓孩子牢固掌握了課本，保證了考試成績，才去干‘雜事’。”為了堵住悠悠之口，也為了向別人證明我做的是對的。我跟孩子們商量該怎么辦。孩子們紛紛出謀劃策，結合我們原來的學習方法，我們又制定了新的學習模式——“五讀掌”。每天學習課文之前，自己在家里預習，解決生字等最基本的學習目標，在書本的空白處批上自己的理解，給不太懂的地方坐上標記。課堂上通過小組合作討論，分享自己的理解所得，并解決昨天自己預習時所遇到的問題。下一步展示，小組推薦自己的批注里比較重要的地方，分享給全班同學。理解了課文后，演繹課文，選自己喜歡的地方或者感受最深的地方，通過朗讀表演出來。孩子們基本上每堂課都在忙，忙于展示，忙于討論，忙于分享，忙于表演......而且是樂在其中的忙。他們還說：“在別人展示的時候，認真聽，一方面表示對別人的尊重，二是把別人的理解據為己有，我們就站在了巨人的肩膀上，自己就會變得更聰明?！?/p>

五、快速閱讀，事半功倍

課堂變得高效，課文就學的特別快。在大半個學期的時候，我們就學完了課文，孩子們沒有意思，就要求把我們的輔助讀物《快樂作文》和《語文閱讀》，也拿到課堂上用“五毒掌”來學習。由于，這兩本書的單元主題是一樣的，所以我們就合并學習，一次學習一個單元。通過預習，批注，提問，展示，演繹的方式，我們愉快的度過了一堂又一堂的語文課。我們知道了南京大屠殺使中國人前所未有的團結起來，我們知道了一個孩子一雙小眼睛里有無數的情感，我們知道了......看著孩子們因學到了知識而閃光的笑臉，我心里特別欣慰。

“課內外海量閱讀”研究實施以來，我帶著孩子們一個學期學完了《語文課本》、《日有所誦》、《中華經典誦讀之孟子》、《中華經典誦讀之增廣賢文》、《快樂作文》、《語文閱讀》、《俗語兒歌100首》七本書，孩子們在課外也在一本本書里認識了楊紅櫻、沈石溪、鄭淵潔、曹文軒等作家，嘗到了讀書的甜頭，享受了讀書的快樂。就這樣讀著，想著，實驗著，摸索著，快樂著，一路走下去，我愿意。