第一篇：火龍果軟件-海量數(shù)據(jù)處理小結(jié)

火龍果?整理 uml.org.cn

海量的數(shù)據(jù)處理問題，對其進(jìn)行處理是一項艱巨而復(fù)雜的任務(wù)。原因有以下幾個方面：

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

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

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

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

二、編寫優(yōu)良的程序代碼處理數(shù)據(jù)離不開優(yōu)秀的程序代碼，尤其在進(jìn)行復(fù)雜數(shù)據(jù)處理時，必須使用程序。好的程序代碼對數(shù)據(jù)的處理至關(guān)重要，這不僅僅是數(shù)據(jù)處理準(zhǔn)確度的問題，更是數(shù)據(jù)處理效率的問題。良好的程序代碼應(yīng)該包含好的算法，包含好的處理流程，包含好的效率，包含好的異常處理機(jī)制等。

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

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

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

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

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

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

火龍果?整理 uml.org.cn

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

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

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

十一、定制強(qiáng)大的清洗規(guī)則和出錯處理機(jī)制海量數(shù)據(jù)中存在著不一致性，極有可能出現(xiàn)某處的瑕疵。例如，同樣的數(shù)據(jù)中的時間字段，有的可能為非標(biāo)準(zhǔn)的時間，出現(xiàn)的原因可能為應(yīng)用程序的錯誤，系統(tǒng)的錯誤等，這是在進(jìn)行數(shù)據(jù)處理時，必須制定強(qiáng)大的數(shù)據(jù)清洗規(guī)則和出錯處理機(jī)制。

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

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

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

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

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

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

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

一是分批操作。

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

火龍果?整理 uml.org.cn

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

海量數(shù)據(jù)處理專題

（一）大數(shù)據(jù)量的問題是很多面試筆試中經(jīng)常出現(xiàn)的問題，比如baidu google 騰訊 這樣的一些涉及到海量數(shù)據(jù)的公司經(jīng)常會問到。

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

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

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

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

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

海量數(shù)據(jù)處理專題

（二）【什么是Bloom Filter】

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

【適用范圍】

可以用來實現(xiàn)數(shù)據(jù)字典，進(jìn)行數(shù)據(jù)的判重，或者集合求交集

【基本原理及要點】

火龍果?整理 uml.org.cn

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

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

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

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

【擴(kuò)展】

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

【問題實例】

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

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

海量數(shù)據(jù)處理專題

（三）什么是Hash

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

火龍果?整理 uml.org.cn

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

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

元素特征轉(zhuǎn)變?yōu)閿?shù)組下標(biāo)的方法就是散列法。散列法當(dāng)然不止一種，下面列出三種比較常用的。1，除法散列法

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

index = value % 16

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

2，平方散列法

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

火龍果?整理 uml.org.cn

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

index =(value * value)>> 28

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

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

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

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

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

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

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

i ndex =(value * 2654435769)>> 28

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

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

火龍果?整理 uml.org.cn

【適用范圍】

快速查找，刪除的基本數(shù)據(jù)結(jié)構(gòu)，通常需要總數(shù)據(jù)量可以放入內(nèi)存?！净驹砑耙c】

hash函數(shù)選擇，針對字符串，整數(shù)，排列，具體相應(yīng)的hash方法。

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

【擴(kuò)展】

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

【問題實例】

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

IP的數(shù)目還是有限的，最多2^32個，所以可以考慮使用hash將ip直接存入內(nèi)存，然后進(jìn)行統(tǒng)計。

海量數(shù)據(jù)處理專題

（四）【什么是Bit-map】

所謂的Bit-map就是用一個bit位來標(biāo)記某個元素對應(yīng)的Value，而Key即是該元素。由于采用了Bit為單位來存儲數(shù)據(jù)，因此在存儲空間方面，可以大大節(jié)省。

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

火龍果?整理 uml.org.cn

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

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

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

}

void BitMapSortDemo(){

//BufferLen這個值是根據(jù)待排序的數(shù)據(jù)中最大值確定的 //待排序中的最大值是14，因此只需要2個Bytes(16個Bit)//為了簡單起見，我們不考慮負(fù)數(shù) 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，否則結(jié)果不可預(yù)知。memset(pBuffer,0,BufferLen);for(int i=0;i＜9;i++){

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

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

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

} pBuffer++;

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

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

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

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

火龍果?整理 uml.org.cn

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

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

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

1)已知某個文件內(nèi)包含一些電話號碼，每個號碼為8位數(shù)字，統(tǒng)計不同號碼的個數(shù)。

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

2)2.5億個整數(shù)中找出不重復(fù)的整數(shù)的個數(shù)，內(nèi)存空間不足以容納這2.5億個整數(shù)。

將bit-map擴(kuò)展一下，用2bit表示一個數(shù)即可，0表示未出現(xiàn)，1表示出現(xiàn)一次，2表示出現(xiàn)2次及以上，在遍歷這些數(shù)的時候，如果對應(yīng)位置的值是0，則將其置為1；如果是1，將其置為2；如果是2，則保持不變?；蛘呶覀儾挥?bit來進(jìn)行表示，我們用兩個bit-map即可模擬實現(xiàn)這個 2bit-map，都是一樣的道理。

海量數(shù)據(jù)處理專題

（五）【什么是堆】

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

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

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

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

火龍果?整理 uml.org.cn

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

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

火龍果?整理 uml.org.cn

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

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

火龍果?整理 uml.org.cn

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

【適用范圍】

海量數(shù)據(jù)前n大，并且n比較小，堆可以放入內(nèi)存

【基本原理及要點】

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

【擴(kuò)展】

雙堆，一個最大堆與一個最小堆結(jié)合，可以用來維護(hù)中位數(shù)。

【問題實例】

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

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

海量數(shù)據(jù)處理專題

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

【什么是雙層桶】

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

【適用范圍】

第k大，中位數(shù)，不重復(fù)或重復(fù)的數(shù)字

【基本原理及要點】

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

【擴(kuò)展】

當(dāng)有時候需要用一個小范圍的數(shù)據(jù)來構(gòu)造一個大數(shù)據(jù)，也是可以利用這種思想，相比之下不同的，只是其中的逆過程。

【問題實例】

1).2.5億個整數(shù)中找出不重復(fù)的整數(shù)的個數(shù)，內(nèi)存空間不足以容納這2.5億個整數(shù)。

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

這個例子比上面那個更明顯。首先我們將int劃分為2^16個區(qū)域，然后讀取數(shù)據(jù)統(tǒng)計落到各個區(qū)域里的數(shù)的個數(shù)，之后我們根據(jù)統(tǒng)計結(jié)果就可以判斷中位數(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進(jìn)行統(tǒng)計了。

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

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

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

? 大數(shù)據(jù)量的問題是很多面試筆試中經(jīng)常出現(xiàn)的問題，比如baidu google 騰訊 這樣的一些涉及到海量數(shù)據(jù)的公司經(jīng)常會問到。

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

1.Bloom filter

適用范圍：可以用來實現(xiàn)數(shù)據(jù)字典，進(jìn)行數(shù)據(jù)的判重，或者集合求交集

基本原理及要點：

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

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

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

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

擴(kuò)展：

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

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

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

2.Hashing

適用范圍：快速查找，刪除的基本數(shù)據(jù)結(jié)構(gòu)，通常需要總數(shù)據(jù)量可以放入內(nèi)存

基本原理及要點：

hash函數(shù)選擇，針對字符串，整數(shù)，排列，具體相應(yīng)的hash方法。

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

擴(kuò)展：

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

問題實例：

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

IP的數(shù)目還是有限的，最多2^32個，所以可以考慮使用hash將ip直接存入內(nèi)存，然后進(jìn)行統(tǒng)計。

3.bit-map

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

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

擴(kuò)展：bloom filter可以看做是對bit-map的擴(kuò)展

問題實例：

1)已知某個文件內(nèi)包含一些電話號碼，每個號碼為8位數(shù)字，統(tǒng)計不同號碼的個數(shù)。

8位最多99 999 999，大概需要99m個bit，大概10幾m字節(jié)的內(nèi)存即可。

2)2.5億個整數(shù)中找出不重復(fù)的整數(shù)的個數(shù)，內(nèi)存空間不足以容納這2.5億個整數(shù)。

將bit-map擴(kuò)展一下，用2bit表示一個數(shù)即可，0表示未出現(xiàn)，1表示出現(xiàn)一次，2表示出現(xiàn)2次及以上?；蛘呶覀儾挥?bit來進(jìn)行表示，我們用兩個bit-map即可模擬實現(xiàn)這個2bit-map。

4.堆

適用范圍：海量數(shù)據(jù)前n大，并且n比較小，堆可以放入內(nèi)存

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

擴(kuò)展：雙堆，一個最大堆與一個最小堆結(jié)合，可以用來維護(hù)中位數(shù)。

問題實例：

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

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

5.雙層桶劃分

適用范圍：第k大，中位數(shù)，不重復(fù)或重復(fù)的數(shù)字

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

擴(kuò)展：

問題實例：

1).2.5億個整數(shù)中找出不重復(fù)的整數(shù)的個數(shù)，內(nèi)存空間不足以容納這2.5億個整數(shù)。

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

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

這個例子比上面那個更明顯。首先我們將int劃分為2^16個區(qū)域，然后讀取數(shù)據(jù)統(tǒng)計落到各個區(qū)域里的數(shù)的個數(shù)，之后我們根據(jù)統(tǒng)計結(jié)果就可以判斷中位數(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進(jìn)行統(tǒng)計了。

6.數(shù)據(jù)庫索引

適用范圍：大數(shù)據(jù)量的增刪改查

基本原理及要點：利用數(shù)據(jù)的設(shè)計實現(xiàn)方法，對海量數(shù)據(jù)的增刪改查進(jìn)行處理。

擴(kuò)展：

問題實例：

7.倒排索引(Inverted index)

適用范圍：搜索引擎，關(guān)鍵字查詢

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

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

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” 將對應(yīng)集合的交集。

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

擴(kuò)展：

問題實例：文檔檢索系統(tǒng)，查詢那些文件包含了某單詞，比如常見的學(xué)術(shù)論文的關(guān)鍵字搜索。

8.外排序

適用范圍：大數(shù)據(jù)的排序，去重

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

擴(kuò)展：

問題實例：

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

這個數(shù)據(jù)具有很明顯的特點，詞的大小為16個字節(jié)，但是內(nèi)存只有1m做hash有些不夠，所以可以用來排序。內(nèi)存可以當(dāng)輸入緩沖區(qū)使用。

9.trie樹

適用范圍：數(shù)據(jù)量大，重復(fù)多，但是數(shù)據(jù)種類小可以放入內(nèi)存

基本原理及要點：實現(xiàn)方式，節(jié)點孩子的表示方式

擴(kuò)展：壓縮實現(xiàn)。

問題實例：

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

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

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

10.分布式處理 mapreduce

適用范圍：數(shù)據(jù)量大，但是數(shù)據(jù)種類小可以放入內(nèi)存

基本原理及要點：將數(shù)據(jù)交給不同的機(jī)器去處理，數(shù)據(jù)劃分，結(jié)果歸約。

擴(kuò)展：

問題實例：

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).海量數(shù)據(jù)分布在100臺電腦中，想個辦法高效統(tǒng)計出這批數(shù)據(jù)的TOP10。

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

經(jīng)典問題分析

上千萬or億數(shù)據(jù)（有重復(fù)），統(tǒng)計其中出現(xiàn)次數(shù)最多的前N個數(shù)據(jù),分兩種情況：可一次讀入內(nèi)存，不可一次讀入。

可用思路：trie樹+堆，數(shù)據(jù)庫索引，劃分子集分別統(tǒng)計，hash，分布式計算，近似統(tǒng)計，外排序

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

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

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

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

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

另外還可以考慮近似計算，也就是我們可以通過結(jié)合自然語言屬性，只將那些真正實際中出現(xiàn)最多的那些詞作為一個字典，使得這個規(guī)?？梢苑湃雰?nèi)存。

第三篇：數(shù)據(jù)處理和電子表格軟件教案

“數(shù)據(jù)處理和電子表格軟件”教學(xué)設(shè)計

【適用年級】 初二年級第二學(xué)期 【適用單元】 電子表格軟件第1節(jié) 【教學(xué)目標(biāo)】 ●知識目標(biāo)

（1）熟悉EXCEL窗口。

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

通過學(xué)生探究學(xué)習(xí)過程中，掌握EXCEL窗口中幾個的基本操作?！袂楦心繕?biāo)

（1）通過動手實踐，培養(yǎng)學(xué)生在學(xué)習(xí)過程中自主探究、對比、舉一反三的學(xué)習(xí)能力；

（2）利用知識的遷移，培養(yǎng)學(xué)生的綜合信息素養(yǎng)能力。【課時安排】2課時（兩節(jié)連上）【教學(xué)重點與難點】

（1）重點：工作簿、工作表、單元格概念。（2）難點：掌握工作表、單元格的基本操作。【教學(xué)方法】對比法、任務(wù)驅(qū)動法 【課前準(zhǔn)備】軟件EXCEL 【教學(xué)設(shè)計】

教學(xué)過程 教師活動 學(xué)生活動 教學(xué)意圖

引入新課

大家打開書本的目錄看本書要學(xué)習(xí)什么內(nèi)容？目錄中大家看到的黑體字是——用計算機(jī)處理數(shù)據(jù)，計算機(jī)能處理什么樣的數(shù)據(jù)呢？ 觀察本書目錄

讓學(xué)生了解這本書我們將要學(xué)習(xí)哪些內(nèi)容？（培養(yǎng)學(xué)生每學(xué)習(xí)一本書前先了解所學(xué)內(nèi)容大概的習(xí)慣）

閱讀思考

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

1、什么是信息？什么是數(shù)據(jù)？兩者有聯(lián)系嗎？

2、什么是數(shù)據(jù)處理？數(shù)據(jù)處理使用到哪些軟件？

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

說說自己的理解

培養(yǎng)學(xué)生利用閱讀獲取知識的習(xí)慣

區(qū)別與拓展

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

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

黑色的、有長和寬的黑板 EXCEL 學(xué)生積極發(fā)言 設(shè)疑激趣 拓展知識面

讓學(xué)生表達(dá)自己的看法，展示自己的空間

任務(wù)驅(qū)動

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

培養(yǎng)學(xué)生自主探究和對比學(xué)習(xí)的能力

學(xué)生演示 請發(fā)現(xiàn)不同處的學(xué)生在教師機(jī)上展示 觀察

知識鞏固

設(shè)置障礙

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

學(xué)生說，教師操作

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

引入新問題

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

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

觀察區(qū)別概念

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

讓學(xué)生正確區(qū)別工作簿、工作表、單元格概念

正確區(qū)別單元格、當(dāng)前單元格、單元格區(qū)域概念

任務(wù)驅(qū)動

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

學(xué)生實踐

以單元格的練習(xí)促進(jìn)學(xué)生自主學(xué)習(xí)單元格的操作

教師小結(jié)并處理練習(xí)問題

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

1、單個（一個）單元格

2、連續(xù)單元格區(qū)域

3、整行或整列

4、不連續(xù)單元格區(qū)域

觀察

總結(jié)知識點

任務(wù)驅(qū)動

P16的練習(xí)7，它主要是對工作表進(jìn)行的操作，可結(jié)合課本P13—P14完成練習(xí)學(xué)生實踐

以工作表的練習(xí)促進(jìn)學(xué)生自主學(xué)習(xí)工作表操作

輔導(dǎo)并檢查作業(yè)

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

知識舉一反三

學(xué)生總結(jié)本課知識 這節(jié)課你學(xué)到了什么？

教學(xué)后記

這節(jié)課教師引導(dǎo)，學(xué)生自主學(xué)習(xí)充分體現(xiàn)出來，我上本節(jié)課的成功之處有以下幾點。

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

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

3．區(qū)別與拓展：對“信息”與“數(shù)據(jù)”知識的拓展比較滿意，擴(kuò)大學(xué)生對抽象概念的理解。

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

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

第四篇：火龍果軟件-UMLATM設(shè)計文檔

火龍果?整理 uml.org.cn

UML實驗報告

2.用例建模

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

掌握用Rose或PowerDesigner進(jìn)行用例建模的具體方法和步驟

1.ATM系統(tǒng)用例圖:

存款現(xiàn)金管理取款客戶修改密碼銀行管理員維護(hù)ATM設(shè)備轉(zhuǎn)賬余額查詢

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

.系統(tǒng)執(zhí)行者：取款子系統(tǒng) 目的：執(zhí)行取款任務(wù) 類型：端點 主要的 基本的 級別：一級 過程描述： 1.插卡

2.輸入密碼

3.輸入取款金額確定

4.取款打印憑條

5.退出系統(tǒng) “查詢”用例 用例編號：0670

火龍果?整理 uml.org.cn

用例名：查詢賬戶 執(zhí)行者：.人執(zhí)行者：客戶

.系統(tǒng)執(zhí)行者：查詢子系統(tǒng) 目的：執(zhí)行查詢?nèi)蝿?wù) 類型：端點 主要的 基本的 級別：一級 過程描述： 1.插卡

2.輸入密碼

3.查詢賬號

4.人名幣查詢

5.查詢打印憑條

6.退出系統(tǒng)

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

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

2.輸入密碼

3.修改密碼

4.輸入新密碼

5.再次輸入新密碼

6.修改成功退出系統(tǒng)

“轉(zhuǎn)賬”用例 用例編號：0668 用例名：轉(zhuǎn)賬 執(zhí)行者：.人執(zhí)行者：客戶

.系統(tǒng)執(zhí)行者：轉(zhuǎn)賬子系統(tǒng) 目的：執(zhí)行轉(zhuǎn)賬任務(wù) 類型：端點 主要的 基本的 級別：一級 過程描述：1.插卡。

2.輸入密碼。

3.進(jìn)入轉(zhuǎn)賬界面。

4.輸入轉(zhuǎn)入卡號或賬號（只能同行轉(zhuǎn)賬）。

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

火龍果?整理 uml.org.cn

6.輸入轉(zhuǎn)入金額確定。

7.退出系統(tǒng) “現(xiàn)金管理”用例 用例編號：0667 用例名：現(xiàn)金管理 執(zhí)行者：

.人執(zhí)行者：銀行管理員.系統(tǒng)執(zhí)行者：現(xiàn)金管理子系統(tǒng) 目的：執(zhí)行現(xiàn)金管理任務(wù) 類型：端點 主要的 基本的 級別：一級

過程描述： 1.進(jìn)入銀行系統(tǒng)

2.進(jìn)行添加現(xiàn)金操作

3.退出系統(tǒng) “維護(hù)ATM設(shè)備”用例 用例編號：0667 用例名：維護(hù)ATM設(shè)備 執(zhí)行者：

.人執(zhí)行者：銀行管理員

.系統(tǒng)執(zhí)行者：維護(hù)ATM設(shè)備子系統(tǒng) 目的：執(zhí)行現(xiàn)金管理任務(wù) 類型：端點 主要的 基本的 級別：一級

過程描述： 1.進(jìn)入銀行系統(tǒng)

2.對ATM設(shè)備進(jìn)行檢查

3.對ATM設(shè)備進(jìn)行相應(yīng)維護(hù)

4.退出系統(tǒng)

3.活動圖建模

了解活動圖建模的概念

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

ATM取款子系統(tǒng)活動圖：

火龍果?整理 uml.org.cn 客戶需求分析規(guī)格說明書/系統(tǒng)分析規(guī)格說明書

了解用包模型來描述系統(tǒng)體系結(jié)構(gòu)（用例模型）的方法 掌握用Rose或PowerDesigner進(jìn)行包圖建模的具體方法和步驟

火龍果?整理 uml.org.cn

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

5.類建模

? 對象類建模

理解面向?qū)ο笙到y(tǒng)分析和對象類建模的概念 了解和掌握面向?qū)ο笙到y(tǒng)分析的方法和步驟 了解和掌握尋找待開發(fā)系統(tǒng)中類的方法和技巧 掌握使用Rose或PowerDesigner建立類模型的方法

? 類的繼承建模

理解類之間的繼承關(guān)系

了解和掌握分析類之間繼承關(guān)系的方法

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

? 對象類關(guān)聯(lián)關(guān)系建模

理解面向?qū)ο箢愔g關(guān)聯(lián)關(guān)系的概念 了解和掌握分析類之間的關(guān)聯(lián)關(guān)系的方法

了解和掌握待開發(fā)系統(tǒng)中類之間關(guān)聯(lián)關(guān)系的分析方法

掌握使用Rose或PowerDesigner如何對關(guān)聯(lián)關(guān)系進(jìn)行建模的過程

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

setType設(shè)置帳戶類型，返回類型為void，參數(shù)類型為char，輸入帳戶類型。

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

setAccountNumbe設(shè)置帳戶號，返回類型為void，參數(shù)類型為int，輸入帳戶號。

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

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

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

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

對象類關(guān)聯(lián)關(guān)系圖：

火龍果?整理 uml.org.cn

銀行0..10..10..*0..10..1賬號庫0..*銀行儲戶庫ATM系統(tǒng)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機(jī)0..*0..*-+++ATM機(jī)ID: int收款(): int吐款(): int其他服務(wù)(): int1..*0..1 順序圖建模

理解順序圖的基本概念

了解和掌握軟件工程中用例邏輯時序的分析方法 了解和掌握待開發(fā)系統(tǒng)中順序圖的設(shè)計和實現(xiàn) 掌握使用Rose或PowerDesigner創(chuàng)建順序圖的方法

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

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

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

火龍果?整理 uml.org.cn

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

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

掌握使用Rose或PowerDesigner依據(jù)用例繪制合作圖

合作圖和順序圖是可以無信息損失的相互轉(zhuǎn)換，只是它們的側(cè)重點是不一樣的。順序圖著重于對象間消息傳遞的時間順序，合作圖著重于表達(dá)對象之間的靜態(tài)連接關(guān)系。下圖將順序圖轉(zhuǎn)換為合作圖。

ATM系統(tǒng)協(xié)作圖 ：

1．插入ATM卡

2．接受ATM卡

3．查詢密碼

4．顯示輸入密碼請求

5．輸入密碼

6．密碼傳遞

7．請求確認(rèn)密碼合法性

8．確認(rèn)密碼合法性

9．詢問服務(wù)類別

10．顯示輸入服務(wù)服務(wù)類別請求

11．輸入取款請求

12．取款請求

13．詢問取款數(shù)額

14．顯示輸入數(shù)額請求

15．輸入取款數(shù)額

16．傳遞取款數(shù)額

17．詢問取款數(shù)額確認(rèn)

火龍果?整理 uml.org.cn

18．顯示確認(rèn)數(shù)額請求

19．輸入確認(rèn)

20．傳遞確認(rèn)信息

21．?dāng)?shù)額合法性確認(rèn)請求

22．確認(rèn)數(shù)額和法性

23．出鈔請求

24．計算帳戶余額

25．出鈔

26．取鈔

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

28．顯示帳戶余額并提示選擇下面的服務(wù) 狀態(tài)圖建模

了解狀態(tài)圖的概念及其在系統(tǒng)設(shè)計中的作用

掌握使用Rose或PowerDesigner依據(jù)用例繪制對象的狀態(tài)圖

下圖描述了顧客在ATM機(jī)上進(jìn)行操作會經(jīng)歷的幾種狀態(tài)，及各種狀態(tài)之間轉(zhuǎn)換的條件。因為是簡化了的例子，所以除了等待顧客插入磁卡的起始狀態(tài)和結(jié)束服務(wù)的終止?fàn)顟B(tài)，顧客會處于輸入密碼、選擇服務(wù)類型、存款及取款四種狀態(tài)。

ATM狀態(tài)圖：

插入磁卡后進(jìn)入輸密碼狀態(tài)，當(dāng)密碼輸入正確時進(jìn)入選擇服務(wù)類型狀態(tài)，當(dāng)輸入密碼不正確時，停留在原狀態(tài)，但如果三次不正確，服務(wù)結(jié)束。進(jìn)入選擇服務(wù)類型后根據(jù)選擇的不同，顧客可進(jìn)入存款和取款狀態(tài)。存、取款結(jié)束后，顧客既可以選擇結(jié)束服務(wù)到最終狀態(tài)，也可以選擇繼續(xù)服務(wù)回到選擇服務(wù)類型狀態(tài)。

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

了解系統(tǒng)物理體系結(jié)構(gòu)模型和表示方法 了解構(gòu)件圖建模的概念及其在系統(tǒng)設(shè)計中的作用 掌握使用Rose或PowerDesigner繪制構(gòu)件圖

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

了解系統(tǒng)物理體系結(jié)構(gòu)模型和表示方法 了解部署圖的概念及其在系統(tǒng)設(shè)計中的作用 掌握使用Rose或PowerDesigner繪制部署圖的方法

第五篇：海量閱讀課題實施小結(jié)

一學(xué)期教七本書不是神話

一學(xué)期教七本書不是神話

浚縣第二實驗小學(xué)

張連鋒

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

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

一、化零為整，每天循序漸進(jìn)

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

二、固定時間，養(yǎng)成習(xí)慣

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

三、整合資源，為我所用

國學(xué)經(jīng)典走進(jìn)課堂，給孩子們種植文化底蘊(yùn)?！兜茏右?guī)》《百家姓》《論語》《孟子》等紛紛走進(jìn)各年級的課堂?！吨腥A經(jīng)典誦讀》這套教材編的非常好，原文下面有注釋，注釋下面有譯文，譯文下面有故事鏈接。孩子們完全可以通過自己的用心閱讀來理解，內(nèi)化，吸收。我們這學(xué)期學(xué)的是《孟子》，孩子們已經(jīng)不單單滿足于每周五的閱讀課來閱讀這本書，放學(xué)后，吃飯余，他們都廢寢忘食的讀著。后來，他們紛紛找我說希望閱讀更多的經(jīng)典，于是我把課題組里其他班級的《增廣賢文》借過來發(fā)到班里，孩子們?nèi)琊囁瓶实淖x起來。這樣，我們用了同樣的時間讀了兩本經(jīng)典誦讀，孩子們都滿足而驕傲的說：“我們無法決定時間的長度，但我們拓寬了它的寬度。”

四、課本主角，力求詳解

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

五、快速閱讀，事半功倍

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

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