大數(shù)據(jù)

Map-Reduce 和Hadoop 逐漸成為面試熱門
1. 介紹哈希函數(shù)

哈希函數(shù)又叫散列函數(shù)
1.1  典型的哈希函數(shù)都有無限的輸入值域。
1.2 輸入值相同時，返回值一樣。
1.3 輸入值不同時，返回值可能一樣，也可能不一樣
1.4 不同輸入值得到的哈希值，整體均分的分布在輸出域S上（重要）

1~3 點(diǎn)性質(zhì)是哈希函數(shù)的基礎(chǔ)，第4點(diǎn)是評價一個哈希函數(shù)優(yōu)劣的關(guān)鍵。
aaa1 aaa2 aaa3 雖然相似，但哈希值差異巨大。

2.介紹Map-Rdeduce

2.1  Map階段  把大任務(wù)分成子任務(wù)
2.2 Reduce階段  子任務(wù)并發(fā)處理，然后合并結(jié)果。

難點(diǎn)：工程上的處理

注意點(diǎn)：

1. 備份的考慮，分布式存儲的設(shè)計細(xì)節(jié)，以及容災(zāi)策略。
2. 任務(wù)分配策略與任務(wù)進(jìn)度跟蹤的細(xì)節(jié)設(shè)計，節(jié)點(diǎn)狀態(tài)的呈現(xiàn)
3. 多用戶權(quán)限的控制

map-reduce 方法統(tǒng)計文章的單詞

文章-> 預(yù)處理

1.去掉標(biāo)點(diǎn)符號  
2.連字符
3.對于縮寫的處理
4.大小寫的處理

對每個單詞生成詞頻為1

哈希函數(shù)

子任務(wù)進(jìn)行處理

海量數(shù)量處理技巧

1. 分而自治，通過哈希函數(shù)將大任務(wù)分流到機(jī)器或分流秤小文件
2. 常用hashMap 或bitamp

難點(diǎn)：通訊、時間和空間的估算。

• 請對10億個IPV4的ip地址進(jìn)行排序，每個ip只會出現(xiàn)一次。
  普通做法：
  ip-轉(zhuǎn)換為無符號整數(shù) 10億個整數(shù) 4G
  推薦做法：
  bitmap 2^32 bit類型的數(shù)組。

每個位置上是一個bit，只能表示0和1兩種狀態(tài)。
長度為2^32的bit數(shù)組，空間約為128m.

• 請對10億人的年齡進(jìn)行排序

  0~200
  計數(shù)排序

• 20億全是32位數(shù)整數(shù)的文件，空間限制大小2G

hashmap記錄所有出現(xiàn)的次數(shù)

key->具體某一種數(shù)
value-> 這種數(shù)出現(xiàn)的次數(shù)

內(nèi)存可能超出

文件分流

在40億個無符號整數(shù)的文件，所以在整個范圍中必然沒有出現(xiàn)過的數(shù)，可以使用最多10M的內(nèi)存，只用找到一個沒有出現(xiàn)過的數(shù)即可，該如何找？

hash 表 40億條 每一條4個字節(jié) 16G

bitmap 500M

64個區(qū)間
500M/64 8M
1、根據(jù)內(nèi)存限制決定區(qū)間大小，根據(jù)區(qū)間大小，得到有多少個變量，來記錄每個區(qū)間的數(shù)出現(xiàn)的次數(shù)。
2、 統(tǒng)計區(qū)間上的數(shù)的出現(xiàn)次數(shù)，找到不足的區(qū)間。
3、利用bitmap對不滿足的區(qū)間，進(jìn)行這個區(qū)間上的數(shù)的詞頻統(tǒng)計。

百億數(shù)據(jù)中，找到100個熱詞

分流 確定機(jī)器數(shù)

對每一個機(jī)器，進(jìn)行文件分流，小根堆 確定top100

工程師使用服務(wù)器集群來設(shè)計和是吸納數(shù)據(jù)緩存，以下是常見的側(cè)臉。

1. 無論是添加、查詢還是刪除數(shù)據(jù)，都先將數(shù)據(jù)的id通過哈希函數(shù)轉(zhuǎn)換成一個哈希值，記為key.

2.如果目前機(jī)器有N臺，則計算key%N的值，這個值就是該數(shù)據(jù)所屬的機(jī)器編號，無論是添加、刪除還是查詢操作，都只在這臺機(jī)器上進(jìn)行。請分析這種緩存策略可能帶來的問題。并提出改進(jìn)的方案。

如果增加或刪除機(jī)器，數(shù)據(jù)遷移的代價很大。

一致性哈希算法

數(shù)據(jù)id—> 0~ 2 ^32
key 和data 相鄰存儲
順時針進(jìn)行

動態(tài)規(guī)劃

給定數(shù)組arr，arr中所有的值杜偉整數(shù)且不重復(fù)。每個值代表一種面值的貨幣，每種面值的貨幣可以使用任意張，再給定一個整數(shù)aim代表要找的錢數(shù)，求換錢有多少種方法.

暴力搜索方法

記憶搜索方法

動態(tài)規(guī)劃方法

狀態(tài)繼續(xù)優(yōu)化

arr={5,10,25,1} aim={1000}

• 暴力搜索解決：

public int coins1(int[] arr,int aim){
    if(arr==null||arr.length==0||aim<0)
    {
        return 0;
    }

    return process1(arr,0,aim);
}

public int process1(int [] arr,int index,int aim){
    int res=0;
    if(index==arr.length){
        res=aim==0?1:0;
    }else{
         for(int i=0;arr[index]*i<=aim;i++){
            res+=process1(arr,index+1,aim-arr[index]*i);    
             }
         }
}

如果已經(jīng)使用0張5元和1張10元的情況下
后續(xù)將求：p1(arr,2,990)
這里2表示arr剩下的錢為arr[2,3] 即為[25,1]
990：表示要找的剩余錢數(shù)。

2張5元0張10元p1(arr,2,990)

• 記憶搜索方法：

  arr={5,10,24,1}, aim=1000
  p(index,aim) 結(jié)果表map

  1. 每計算完一個p(index,aim),都將結(jié)果放入map中，index和aim組成共同的key，
     返回結(jié)果為Value.

  2. 要進(jìn)入一個遞歸過程p(index,aim)
     先以index和aim注冊的key在map中查詢是否已經(jīng)在value中，如果存在，則直接取值，如果不存在，才進(jìn)行遞歸計算。

public int coins2(int[] arr,int aim){
    if(arr==null||arr.length==0||aim<0){
    return 0;
    }
    int[][] map=new int[arr.length+1][aim+1];
        return process2(arr,0,aim,map);
}

public int process2(int[] arr,int index,int aim,int[][] map){
    int res=0;
    if(index==arr.length){
        res=aim==0?1:0;
    }else{
        int mapValue=0;
        for(int i=0;arr[index]*i<=aim;i++){
            mapValue=mapValue==-1?0:mapValue;
            }else{
                res+=process2(arr,index+1,aim-arr[index]*i,map);
            }
        }
    }
    map[index][aim]=res==0?-1:res;
    return res;
}

• 動態(tài)規(guī)劃方法

  如果arr長度為N，生成行數(shù)為N，列數(shù)為aim+1的矩陣dp
  dp[i][j] 的含義是在使用arr[0..i]貨幣的情況下，有多少種方法。

什么是動態(tài)規(guī)劃方法

1. 其本質(zhì)是利用空間來記錄每一個暴力搜索的計算結(jié)果的時候直接使用，從而不再是用重復(fù)計算。

2. 動態(tài)規(guī)劃由于規(guī)定了每一種遞歸的計算順序，依次進(jìn)行計算。

面試中遇到暴力遞歸題目可以優(yōu)化成動態(tài)規(guī)劃方法的大體過程：

1. 實現(xiàn)暴力遞歸方法。
2. 在暴力搜索方法的函數(shù)中看看那些參數(shù)可以代表遞歸過程。
3. 找到代表遞歸過程的參數(shù)之后，記憶話搜索方法非常容易實現(xiàn)。
4. 通過分析記憶話搜索的依賴路徑，進(jìn)而實現(xiàn)動態(tài)規(guī)劃。
5. 根據(jù)記憶化搜索方法改出動態(tài)規(guī)劃，減少時間復(fù)雜度。

動態(tài)規(guī)劃的關(guān)鍵點(diǎn)：

1. 最優(yōu)化原理，也就是最優(yōu)子結(jié)構(gòu)性質(zhì)。這指的是一個最優(yōu)化策略具有這樣的性質(zhì)，不論過去狀態(tài)和決策如何，對前面的決策所形成的的狀態(tài)而言，余下的諸多決策必須構(gòu)成最優(yōu)決策，簡單來說就是一個最優(yōu)化的策略的子策略總是最優(yōu)的，如果一個問題滿足最優(yōu)化原理，就稱其具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

2. 無后效性。指的是某狀態(tài)下決策的收益，只與狀態(tài)和決策相關(guān)，與到達(dá)該狀態(tài)的方式無關(guān)。

3. 子問題的重疊性，動態(tài)規(guī)劃將原來具有指數(shù)級時間復(fù)雜度的暴力搜索算法改進(jìn)成了具有多項式時間復(fù)雜度的算法。其中的關(guān)鍵在于解決冗余，這是動態(tài)規(guī)劃算法的根本目的。

經(jīng)典動態(tài)規(guī)劃的問題

• 有n級臺階，一個每次上一級或者兩級，問有多少種走完n級的方法？

  f(1)=1
  f(2)=2
  f(i)= f(i-1)+f(i-2)

public int s1(int n){
    if(n<1)
    return 0;

}
    if(n==1||n==2){
    return n;
    }
    return s1(n-1)+s1(n-2);
}

• 求矩陣中最小的路徑和

  dp[i][j]=m[i][j]+dp[i-1][j]
  dp[i][j-1]

• 返回arr的最長遞增子序列長度

  2 1 5 3 6 4 8 9 7
  返回 1 3 4 8 9 長度為5

  arr 2 1 5 3 6 4 8 9 7
  dp: 1 1 2 2 3 3 4 5 4 長度為5

• 假設(shè)str1的長度為M，str2的長度為N，生成大小為M*N的矩陣dp.dp[i][j]的含義是str1[0..i] 與str2[0..j]的最長公共序列的長度。

待補(bǔ)：

• 一個背包有一定的承重W,有N件物品，每件都有自己的價值，記錄在數(shù)組V中，也都有自己的重量，記錄在數(shù)組W中，沒見物品只能選擇要裝入背包還是不裝入背包，要求在不超過背包承重的前提下，選出物品的總價值最大。

  假設(shè)物品編號1~n,一件一件物品考慮是否加入背包

  假設(shè)dp[x][y]表示前X件物品，不超過重量y的時候的最大價值。枚舉一下第X件物品的情況。

  情況一： 如果選擇第X件物品，則前X-1件物品得到的重量不能超過y-w[x].
  情況二：如果不選第X件物品，則前X-1件物品得到的重量不能超過

  所以dp[x][y]可能等于dp[x-1][y],也就是是不取第x件物品的時候，價值和之前一樣。
  
  也可能是dp[x-1][y-w[x]]+v[x], 也就是決定拿第x件物品的情況，當(dāng)然會獲得x物品的價值。
  
  兩種可能性中，應(yīng)該選擇價值最大的那個。dp[x][y]=max{dp[x-1][y],dp[x-1][y-w[x]]+v[x]}.
  
  
  對于dp矩陣來說，行數(shù)是物品的數(shù)量n，行數(shù)是背包的重量W。從左到右，再從上到下依次計算所有dp值即可。
  

最新評論