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

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

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

1.Bloom filter

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

基本原理及要點：

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

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

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

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

擴展：

Bloom filter將集合中的元素映射到位數(shù)組中，用k（k為哈希函數(shù)個數(shù)）個映射位是否全1表示元素在不在這個集合中。Counting bloom filter（CBF）將位數(shù)組中的每一位擴展為一個counter，從而支持了元素的刪除操作。Spectral Bloom Filter（SBF）將其與集合元素的出現(xiàn)次數(shù)關聯(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是一一對應的，就可以轉換成ip，則大大簡單了。

2.Hashing

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

基本原理及要點：

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

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

擴展：

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

問題實例：

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

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

3.bit-map

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

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

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

問題實例：

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

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

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

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

4.堆

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

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

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

問題實例：

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

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

5.雙層桶劃分

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

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

擴展：

問題實例：

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就可以直接解決了。也就是說只要有足夠的磁盤空間，就可以很方便的解決。

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)計了。

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

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

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

擴展：

問題實例：

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” 將對應集合的交集。

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

擴展：

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

8.外排序

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

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

擴展：

問題實例：

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

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

9.trie樹

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

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

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

問題實例：

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

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

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

10.分布式處理 mapreduce

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

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

擴展：

問題實例：

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個機器，每個機器上有N個數(shù)。每個機器最多存O(N)個數(shù)并對它們操作。如何找到N^2個數(shù)的中數(shù)(median)？

經(jīng)典問題分析

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

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

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

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

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

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

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

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

第二篇：大數(shù)據(jù)量,海量數(shù)據(jù) 處理方法總結

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

下面的方法是我對海量數(shù)據(jù)的處理方法進行了一個一般性的總結，當然這些方法可能并不能完全覆蓋所有的問題，但是這樣的一些方法也基本可以處理絕大多數(shù)遇到的問題。下面的一些問題基本直接來源于公司的面試筆試題目，方法不一定最優(yōu)，如果你有更好的處理方法，歡迎與我討論。1.Bloom filter 適用范圍：可以用來實現(xiàn)數(shù)據(jù)字典，進行數(shù)據(jù)的判重，或者集合求交集

基本原理及要點：

對 于原理來說很簡單，位數(shù)組+k個獨立hash函數(shù)。將hash函數(shù)對應的值的位數(shù)組置1，查找時如果發(fā)現(xiàn)所有hash函數(shù)對應位都是1說明存在，很明顯這 個過程并不保證查找的結果是100%正確的。同時也不支持刪除一個已經(jīng)插入的關鍵字，因為該關鍵字對應的位會牽動到其他的關鍵字。所以一個簡單的改進就是 counting Bloom filter，用一個counter數(shù)組代替位數(shù)組，就可以支持刪除了。還有一個比較重要的問題，如 何根據(jù)輸入元素個數(shù)n，確定位數(shù)組m的大小及hash函數(shù)個數(shù)。當hash函數(shù)個數(shù)k=(ln2)*(m/n)時錯誤率最小。在錯誤率不大于E的情況 下，m至少要等于n*lg(1/E)才能表示任意n個元素的集合。但m還應該更大些，因為還要保證bit數(shù)組里至少一半為0，則m應 該>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2為底的對數(shù))。舉個例子我們假設錯誤率為0.01，則此時m應大概是n的13倍。這樣k大概是8個。

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

擴展：

Bloom filter將集合中的元素映射到位數(shù)組中，用k（k為哈希函數(shù)個數(shù)）個映射位是否全1表示元素在不在這個集合中。Counting bloom filter（CBF）將位數(shù)組中的每一位擴展為一個counter，從而支持了元素的刪除操作。Spectral Bloom Filter（SBF）將其與集合元素的出現(xiàn)次數(shù)關聯(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。現(xiàn)在可用的是340億，相差并不多，這樣可能會使出錯率上升些。另外如果這些urlip是一一對應的，就可以轉換成ip，則大大簡單了。2.Hashing 適用范圍：快速查找，刪除的基本數(shù)據(jù)結構，通常需要總數(shù)據(jù)量可以放入內(nèi)存

基本原理及要點：

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

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

擴展：

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

IP的數(shù)目還是有限的，最多2^32個，所以可以考慮使用hash將ip直接存入內(nèi)存，然后進行統(tǒng)計。3.bit-map 適用范圍：可進行數(shù)據(jù)的快速查找，判重，刪除，一般來說數(shù)據(jù)范圍是int的10倍以下 基本原理及要點：使用bit數(shù)組來表示某些元素是否存在，比如8位電話號碼

擴展：bloom filter可以看做是對bit-map的擴展 問題實例： 1)已知某個文件內(nèi)包含一些電話號碼，每個號碼為8位數(shù)字，統(tǒng)計不同號碼的個數(shù)。

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

2)2.5億個整數(shù)中找出不重復的整數(shù)的個數(shù)，內(nèi)存空間不足以容納這2.5億個整數(shù)。將bit-map擴展一下，用2bit表示一個數(shù)即可，0表示未出現(xiàn)，1表示出現(xiàn)一次，2表示出現(xiàn)2次及以上?；蛘呶覀儾挥?bit來進行表示，我們用兩個bit-map即可模擬實現(xiàn)這個2bit-map。

4.堆 適用范圍：海量數(shù)據(jù)前n大，并且n比較小，堆可以放入內(nèi)存 基 本原理及要點：最大堆求前n小，最小堆求前n大。方法，比如求前n小，我們比較當前元素與最大堆里的最大元素，如果它小于最大元素，則應該替換那個最大元 素。這樣最后得到的n個元素就是最小的n個。適合大數(shù)據(jù)量，求前n小，n的大小比較小的情況，這樣可以掃描一遍即可得到所有的前n元素，效率很高。

擴展：雙堆，一個最大堆與一個最小堆結合，可以用來維護中位數(shù)。問題實例： 1)100w個數(shù)中找最大的前100個數(shù)。

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

5.雙層桶劃分 適用范圍：第k大，中位數(shù)，不重復或重復的數(shù)字

基本原理及要點：因為元素范圍很大，不能利用直接尋址表，所以通過多次劃分，逐步確定范圍，然后最后在一個可以接受的范圍內(nèi)進行。可以通過多次縮小，雙層只是一個例子。擴展： 問題實例： 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就可以直接解決了。也就是說只要有足夠的磁盤空間，就可以很方便的解決。

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)計了。6.數(shù)據(jù)庫索引 適用范圍：大數(shù)據(jù)量的增刪改查 基本原理及要點：利用數(shù)據(jù)的設計實現(xiàn)方法，對海量數(shù)據(jù)的增刪改查進行處理。擴展： 問題實例： 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” 將對應集合的交集。正 向索引開發(fā)出來用來存儲每個文檔的單詞的列表。正向索引的查詢往往滿足每個文檔有序頻繁的全文查詢和每個單詞在校驗文檔中的驗證這樣的查詢。在正向索引 中，文檔占據(jù)了中心的位置，每個文檔指向了一個它所包含的索引項的序列。也就是說文檔指向了它包含的那些單詞，而反向索引則是單詞指向了包含它的文檔，很 容易看到這個反向的關系。擴展： 問題實例：文檔檢索系統(tǒng)，查詢那些文件包含了某單詞，比如常見的學術論文的關鍵字搜索。8.外排序 適用范圍：大數(shù)據(jù)的排序，去重 基本原理及要點：外排序的歸并方法，置換選擇 敗者樹原理，最優(yōu)歸并樹

擴展：

問題實例： 1).有一個1G大小的一個文件，里面每一行是一個詞，詞的大小不超過16個字節(jié)，內(nèi)存限制大小是1M。返回頻數(shù)最高的100個詞。這個數(shù)據(jù)具有很明顯的特點，詞的大小為16個字節(jié)，但是內(nèi)存只有1m做hash有些不夠，所以可以用來排序。內(nèi)存可以當輸入緩沖區(qū)使用。9.trie樹 適用范圍：數(shù)據(jù)量大，重復多，但是數(shù)據(jù)種類小可以放入內(nèi)存 基本原理及要點：實現(xiàn)方式，節(jié)點孩子的表示方式 擴展：壓縮實現(xiàn)。問題實例： 1).有10個文件，每個文件1G，每個文件的每一行都存放的是用戶的query，每個文件的query都可能重復。要你按照query的頻度排序。

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

3).尋找熱門查詢：查詢串的重復度比較高，雖然總數(shù)是1千萬，但如果除去重復后，不超過3百萬個，每個不超過255字節(jié)。10.分布式處理 mapreduce 適用范圍：數(shù)據(jù)量大，但是數(shù)據(jù)種類小可以放入內(nèi)存

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

擴展：

問題實例： 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個機器，每個機器上有N個數(shù)。每個機器最多存O(N)個數(shù)并對它們操作。如何找到N^2個數(shù)的中數(shù)(median)？ 經(jīng)典問題分析 上千萬or億數(shù)據(jù)（有重復），統(tǒng)計其中出現(xiàn)次數(shù)最多的前N個數(shù)據(jù),分兩種情況：可一次讀入內(nèi)存，不可一次讀入。

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

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

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

當 然還有更好的方法，就是可以采用分布式計算，基本上就是map-reduce過程，首先可以根據(jù)數(shù)據(jù)值或者把數(shù)據(jù)hash(md5)后的值，將數(shù)據(jù)按照范 圍劃分到不同的機子，最好可以讓數(shù)據(jù)劃分后可以一次讀入內(nèi)存，這樣不同的機子負責處理各種的數(shù)值范圍，實際上就是map。得到結果后，各個機子只需拿出各 自的出現(xiàn)次數(shù)最多的前N個數(shù)據(jù)，然后匯總，選出所有的數(shù)據(jù)中出現(xiàn)次數(shù)最多的前N個數(shù)據(jù)，這實際上就是reduce過程。實際上可能想直 接將數(shù)據(jù)均分到不同的機子上進行處理，這樣是無法得到正確的解的。因為一個數(shù)據(jù)可能被均分到不同的機子上，而另一個則可能完全聚集到一個機子上，同時還可 能存在具有相同數(shù)目的數(shù)據(jù)。比如我們要找出現(xiàn)次數(shù)最多的前100個，我們將1000萬的數(shù)據(jù)分布到10臺機器上，找到每臺出現(xiàn)次數(shù)最多的前 100個，歸并之后這樣不能保證找到真正的第100個，因為比如出現(xiàn)次數(shù)最多的第100個可能有1萬個，但是它被分到了10臺機子，這樣在每臺上只有1千 個，假設這些機子排名在

1000個之前的那些都是單獨分布在一臺機子上的，比如有1001個，這樣本來具有1萬個的這個就會被淘汰，即使我們讓每臺機子選 出出現(xiàn)次數(shù)最多的1000個再歸并，仍然會出錯，因為可能存在大量個數(shù)為1001個的發(fā)生聚集。因此不能將數(shù)據(jù)隨便均分到不同機子上，而是要根據(jù)hash 后的值將它們映射到不同的機子上處理，讓不同的機器處理一個數(shù)值范圍。

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

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

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

火龍果?整理 uml.org.cn

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

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

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

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

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

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

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

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

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

六、加大虛擬內(nèi)存如果系統(tǒng)資源有限，內(nèi)存提示不足，則可以靠增加虛擬內(nèi)存來解決。筆者在實際項目中曾經(jīng)遇到針對18億條的數(shù)據(jù)進行處理，內(nèi)存為1GB，1個P4 2.4G的CPU，對這么大的數(shù)據(jù)量進行聚合操作是有問題的，提示內(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ù)再進行合并操作，這樣逐個擊破，有利于小數(shù)據(jù)量的處理，不至于面對大數(shù)據(jù)量帶來的問題，不過這種方法也要因時因勢進行，如果不允許拆分數(shù)據(jù)，還需要另想辦法。不過一般的數(shù)據(jù)按天、按月、按年等存儲的，都可以采用先分后合的方法，對數(shù)據(jù)進行分開處理。

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

火龍果?整理 uml.org.cn

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

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

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

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

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

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

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

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

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

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

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

一是分批操作。

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

火龍果?整理 uml.org.cn

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

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

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

下面的方法是我對海量數(shù)據(jù)的處理方法進行了一個一般性的總結，當然這些方法可能并不能完全覆蓋所有的問題，但是這樣的一些方法也基本可以處理絕大多數(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ù)處理問題的解決方案。歡迎大家關注。

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

（二）【什么是Bloom Filter】

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

【適用范圍】

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

【基本原理及要點】

火龍果?整理 uml.org.cn

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

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

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

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

【擴展】

Bloom filter將集合中的元素映射到位數(shù)組中，用k（k為哈希函數(shù)個數(shù)）個映射位是否全1表示元素在不在這個集合中。Counting bloom filter（CBF）將位數(shù)組中的每一位擴展為一個counter，從而支持了元素的刪除操作。Spectral Bloom Filter（SBF）將其與集合元素的出現(xiàn)次數(shù)關聯(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是一一對應的，就可以轉換成ip，則大大簡單了。

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

（三）什么是Hash

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

火龍果?整理 uml.org.cn

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

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

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

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

index = value % 16

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

2，平方散列法

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

火龍果?整理 uml.org.cn

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

index =(value * value)>> 28

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

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

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

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

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

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

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

i ndex =(value * 2654435769)>> 28

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

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

火龍果?整理 uml.org.cn

【適用范圍】

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

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

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

【擴展】

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

【問題實例】

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

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

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

（四）【什么是Bit-map】

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

如果說了這么多還沒明白什么是Bit-map，那么我們來看一個具體的例子，假設我們要對0-7內(nèi)的5個元素(4,7,2,5,3)排序（這里假設這些元素沒有重復）。那么我們就可以采用Bit-map的方法來達到排序的目的。要表示8個數(shù)，我們就只需要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，這時候的內(nèi)存的Bit位的狀態(tài)如下：

然后我們現(xiàn)在遍歷一遍Bit區(qū)域，將該位是一的位的編號輸出（2，3，4，5，7），這樣就達到了排序的目的。下面的代碼給出了一個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)//為了簡單起見，我們不考慮負數(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，否則結果不可預知。memset(pBuffer,0,BufferLen);for(int i=0;i＜9;i++){

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

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

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

} pBuffer++;

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

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

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

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

火龍果?整理 uml.org.cn

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

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

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

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ù)字對應一個Bit位，所以只需要99M個Bit==1.2MBytes，這樣，就用了小小的1.2M左右的內(nèi)存表示了所有的8位數(shù)的電話）

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

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

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

（五）【什么是堆】

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

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

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

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

火龍果?整理 uml.org.cn

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

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

火龍果?整理 uml.org.cn

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

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

火龍果?整理 uml.org.cn

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

【適用范圍】

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

【基本原理及要點】

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

【擴展】

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

【問題實例】

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

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

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

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

【什么是雙層桶】

事實上，與其說雙層桶劃分是一種數(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ù)里面不能有重復，這也是我為什么用雙層桶劃分思想的另外一個原因。

第四篇：調(diào)研數(shù)據(jù)處理方法：

調(diào)研數(shù)據(jù)處理辦法：調(diào)研數(shù)據(jù)顯示新一季MINISO名創(chuàng)優(yōu)品在華知名度高達63%

當前國內(nèi)實體零售業(yè)市場普遍收縮的大環(huán)境下，MINISO名創(chuàng)優(yōu)品的異軍突起，為廣大零售業(yè)界同行所震撼。為剖析MINISO名創(chuàng)優(yōu)品品牌逆勢而上的品牌戰(zhàn)略，探究其贏取市場青睞的原因，本所組織成立研究生項目調(diào)研小組開展了獨立的針對MINISO名創(chuàng)優(yōu)品品牌現(xiàn)狀調(diào)研項目，現(xiàn)撰寫形成《MINISO名創(chuàng)優(yōu)品品牌現(xiàn)狀調(diào)研報告2.0》。

半年來，國內(nèi)零售業(yè)市場驚現(xiàn)了休閑時尚百貨品牌MINISO名創(chuàng)優(yōu)品強勢來襲的景象，其以驚人的開業(yè)速度進軍全國各大重要商圈，特別是改革開放前沿陣地的廣東，僅上下九商圈就開設了5家MINISO名創(chuàng)優(yōu)品店鋪，深受廣大消費者熱捧，成績斐然。在當前國內(nèi)實體零售業(yè)市場普遍收縮的大環(huán)境下，MINISO名創(chuàng)優(yōu)品的異軍突起，為廣大零售業(yè)界同行所震撼。為剖析MINISO名創(chuàng)優(yōu)品品牌逆勢而上的品牌戰(zhàn)略，本所組織成立研究生項目調(diào)研小組開展了獨立的針對MINISO名創(chuàng)優(yōu)品品牌現(xiàn)狀調(diào)研項目。本項目獲得了名創(chuàng)優(yōu)品（中國）有限公司的支持，向項目組提供了很多有關其品牌、新媒體渠道、深度訪問協(xié)助等間接資料和幫助。

第一季度調(diào)研時間：2014年3月1日10時始至31日16時止；調(diào)研對象：部分城市消費者；調(diào)研主要方式：網(wǎng)絡問卷自填定量調(diào)研；調(diào)研輔助方式：購物現(xiàn)場消費者深度訪問的定性調(diào)研；調(diào)研問卷設計維度：從消費者對品牌的知曉度、首次進店行為興奮點、首次賣場感知、品牌接受狀況、購買心動理由、品牌分享意愿等6個維度設計問卷。據(jù)統(tǒng)計，第一季度品牌調(diào)研活動共吸引了44247人查收電子調(diào)研問卷，回收問卷15034份，有效問卷14712份，最終形成《MINISO名創(chuàng)優(yōu)品品牌現(xiàn)狀調(diào)研報告1.0》。

《MINISO名創(chuàng)優(yōu)品品牌現(xiàn)狀調(diào)研報告1.0》主要內(nèi)容回顧如下：

1)62％的消費者表示沒聽說過MINISO名創(chuàng)優(yōu)品，僅38%的消費者表示聽說過MINISO名

創(chuàng)優(yōu)品，可見當前的MINISO名創(chuàng)優(yōu)品品牌知曉度不高，需加快全國重要商圈布局開店步伐，同時需配合高密度的廣告策略。

2)51％的消費者醉心于MINISO名創(chuàng)優(yōu)品高端大氣的店鋪形象，MINISO名創(chuàng)優(yōu)品高端大

氣的SI是針對商圈經(jīng)過人群的高效殺傷性武器。

3)50％的消費者認同MINISO名創(chuàng)優(yōu)品品牌理念，認同MINISO名創(chuàng)優(yōu)品“真正物美價廉”的品牌主張，消費者品牌體驗良好。

4)72％的消費者明確表示會再度光臨消費，且會因價格吸引愿意購買計劃外商品。

5)60％的消費者認為使其做出購買決定的最心動理由是其商品超高的性價比。

6)82％的消費者愿意將MINISO名創(chuàng)優(yōu)品品牌動態(tài)信息分享給身邊好友。

第二季度調(diào)研時間：2014年5月21日12時始至6月20日12時止；調(diào)研對象：部分城市消費者；調(diào)研主要方式：網(wǎng)絡問卷自填定量調(diào)研；調(diào)研輔助方式：購物現(xiàn)場消費者深度訪問的定性調(diào)研；調(diào)研問卷設計維度：從品牌知曉度、品牌令你最心動的原因、購買的首要考慮因素、偏向購買的品類、關注的媒介渠道、品牌分享意愿等6個維度設計問卷。據(jù)統(tǒng)計，該調(diào)研活動共吸引了88250人查收電子調(diào)研問卷，回收問卷56139份，有效問卷55578份，最終形成《MINISO名創(chuàng)優(yōu)品品牌現(xiàn)狀調(diào)研報告2.0》。

《MINISO名創(chuàng)優(yōu)品品牌現(xiàn)狀調(diào)研報告2.0》調(diào)研基本結果簡述：

1)MINISO名創(chuàng)優(yōu)品品牌知名度同比第一季度調(diào)研結果提升25％，高達63％。

2)MINISO名創(chuàng)優(yōu)品主張的“真正物美價廉”品牌理念的認同度同比第一季度調(diào)研結果提

升了14％，高達64％。

3)MINISO名創(chuàng)優(yōu)品消費者購買的首要考慮因素有51％集中在品牌主張的“真正物美價廉”的先發(fā)優(yōu)勢區(qū)間，即超高性價比，同時25％消費者折服在國際著名休閑時尚百貨品牌的影響力下。

4)MINISO名創(chuàng)優(yōu)品品牌代表的區(qū)隔品類是“休閑時尚百貨”，62％的消費者用購買行動

認同和支持著品牌引入初期的品類區(qū)隔，有利于品牌差異化識別，其中37％的消費者會首選生活百貨，25％的消費者會首選創(chuàng)意家居。

5)92％的消費者明確表示會選擇通過MINISO名創(chuàng)優(yōu)品微信、微博等自媒體平臺收聽其品

牌動態(tài)和商品信息，夯實了MINISO名創(chuàng)優(yōu)品自媒體低成本傳播的基礎，確保其可持續(xù)提供“真正物美價廉”的商品。

6)97％的消費者會支持MINISO名創(chuàng)優(yōu)品媒介策略，并愿意將其良好的消費體驗和海量物

美價廉信息分享推廣，支持MINISO名創(chuàng)優(yōu)品低成本品牌推廣策略。

第五篇：大學物理實驗數(shù)據(jù)處理方法總結

有效數(shù)字

1、有效數(shù)字不同的數(shù)相加減時，以參加運算各量中有效數(shù)字最末一位位數(shù)最高的為準，最后結果與它對其，余下的尾數(shù)按舍入規(guī)則處理。

2、乘除法以參與運算的數(shù)值中有效位數(shù)最少的那個數(shù)為準，但當結果的第1位數(shù)較小，比如1、2、3時可以多保留一位（較?。航Y果的第一位數(shù)小于 有效數(shù)字最少的結果第一位數(shù)）！例如：n=tg56° θ=56° dθ=1°

dn?dtg?d?d??d?cos2???1???0.05cos2?cos256?180

帶入??56?，???1?

?n??n?tg56??1.48（8為保留）

3、可以數(shù)字只出現(xiàn)在最末一位：對函數(shù)運算以不損失有效數(shù)字為準。例如：20*lg63.4 可疑最小位變化0.1 Y=20lgx dy?20dlnx20dx200.1dx???0.01

ln10dxln10xln1063.?20lg63.4?36.04

4、原始數(shù)據(jù)記錄、測量結果最后表示，嚴格按有效數(shù)字規(guī)定處理。（中間過程、結果多算幾次）5、4舍5入6湊偶

6、不估計不確定度時，有效數(shù)字按相應運算法則取位；計算不確定度時以不確定度的處理結果為準。

真值和誤差

1、誤差=測量值-真值

ΔN=N-A

2、誤差既有大小、方向與政府。

3、通常真值和誤差都是未知的。

4、相對約定真值，誤差可以求出。

5、用相對誤差比較測量結果的準確度。

6、ΔN/A≈ΔN/N

7、系統(tǒng)誤差、隨機誤差、粗大誤差

8、隨機誤差：統(tǒng)計意義下的分布規(guī)律。粗大誤差：測量錯誤

9、系統(tǒng)誤差和隨機誤差在一定條件下相互轉化。

不確定度

1、P（x）是概率密度函數(shù)

x測量結果落在xp?dx之間的概率是P(xP)dx當x取遍所有可能的概率值為1.2、正態(tài)分布且消除了系統(tǒng)誤差，概率最大的位置是真值A

3、曲線“胖”精密度低“瘦”精密度高。

4、標準誤差：無限次測量?(x)??（X?A）P(X)dx 有限次測量且真值不知道標準偏

-??2差近似給出S(X)??(Xi?X)2K?1

5、正態(tài)分布的測量結果落入X左右?范圍內(nèi)的概率是0.683

6、真值落入測定值Xi左右?區(qū)間內(nèi)的概率為0.683

7、不確定度是測量結果帶有的一個參數(shù)，用以表征合理賦予被測量值的分散性。

8、A類：用統(tǒng)計方法獲得不確定度 B類：非統(tǒng)計方法。

例如：單擺測量為A類

B類：準確度級別 1.0級電流報表 ΔI=1.0%X15mA=0.15mA為不確定度極限

9、不確定度分量的合成1、重復性誤差S1由平均值的標準差算出

2、儀器誤差由儀器誤差線除以根號3算出

3、方法誤差由實際公式通過理論導出。

不確定度的方差合成

1、方差u?u?????u?????不確定度（標準差形式）

2、uj-標準不確定度分量 標準差?或s。由儀器最大誤差限給出的誤差稱為展伸不確定度。Uj=kuj.uj為標準不確定度，K稱謂包含因子或置信印子。正太分布K=

3、均勻分布K=根號3.3、（樣本）標準偏差2212j?ujn2j uj是參與第j個不確定度的分量開根號后即為合成S(X)??(Xi?X)2n?1（單次測量的標準偏差）。平均值的標準偏差S(X)?S(X)。n4、多次測量的算術平均值X?

5、間接測量不確定度的傳播

?Xiin平均值X的標準偏差S(X)??(Xii?X)2。

n(n?1)例如：伏安法測電阻Rx。Rx?V?Rg IV~V?u(V)??I~I?u(I)?u(Rx)Rg~Rg?u(Rg)?? 由于u(I)u(V)u(Rg)，??1 ,把由此造成的不確定度看成微分看成IVRgV1?RX?R?RdI?XdV?XdRg dRX??2dI?dV?dRg

II?I?V?RgdRX?22222 u(RX)?u1?u2?u3 u2(RX)?u12?u2?u3u1??RX?RXV?RX1u(Rg)?u(Rg)u(I)?2u(I)u2?u(v)?u(v)u3??Rg?II?vI222推廣到多個分量u(Y)?uX1?uX2????uXn

ux1(Y)??Y?Yu(X1)??uxn(Y)?u(Xn)?X1?Xn6、乘除或冪指數(shù)形式采用相對不確定度往往要簡單

乘除 左右同時取對數(shù)后再求微分 例如 ??bb' ln??11d?1db1db?lnb?lnb? 微分 ?? 22?2b2b?222?u(?)??1u(b)??1u(b?)?把微分符號改換成不確定度的合成法則????2b???2b?? ???????U(α)即可求出

7、不確定度提供了在概率含義下的誤差可能取值范圍的一種估計

8、不確定度原則上只保留一位非零數(shù)字，被測量的取位與不確定度對齊，例如u(L)=0.0851cm 第一位不為零的數(shù)為8 而51大于50 所以最后是0.09cm。對中間過程多保留幾位。9、10、方差合成的成立條件 ：各分量是小量并且相互獨立。物理實驗中的數(shù)據(jù)處理方法

1、列表法 作圖法 線性回歸法 逐差法

2、列表法：方法簡便 對應直觀 常用于原始數(shù)據(jù)的記錄 或其它數(shù)據(jù)處理的基礎

①表格的設計明確合理 ②數(shù)據(jù)記錄的規(guī)范和完整 ③注意環(huán)境參數(shù) 列出引用的東西 注意原始數(shù)據(jù)的記錄。

3、作圖法：把實驗數(shù)據(jù)依據(jù)自變量和因變量的關系做成曲線以便反映兩者的函數(shù)關系找出經(jīng)驗

①列表法的基本要求給出原始的數(shù)據(jù)表格 ②坐標的選取和分度 ：最小分度與儀器的最小分度相對應③實驗點用便于識別位置的符號表示，曲線擬合要平滑。不適用于校準曲線例如校準電流表

4、求公式： 直線處理 ：經(jīng)驗公式，直線兩頭的坐標 求出斜率以及截距 b?y2?y1

x2?x1??x2y1?x1y2 取點從擬合后的直線上進行 不取原來的實驗點，應在實驗范圍內(nèi)，盡量x2?x1遠離。

5、一元線性回歸方法（最小二乘法）

y=a+bx 實驗測得數(shù)據(jù)并不嚴格符合直線關系 選出一條直線使得實驗數(shù)據(jù)到直線Δy的平方和最小

??yi?min

i2b?xy?xyX?X22 ??y?bx

①變量關系的選擇 等精度測量u(yi)相等 X-無誤差 ②線性關系的檢驗: 線性模型的合理性 數(shù)據(jù)的相關性 檢驗方法：（1）物理規(guī)律（2）計算相關系數(shù)r r?xy?xy(x?x)(y?y)2222 ?1?r??1 r接近于零 不相關

③曲線改直線

6、逐差法