目錄

正文

三個題目

第一題

問題描述

統(tǒng)計出當(dāng)前這個一行一個IP的文件中，到底哪個IP出現(xiàn)的次數(shù)最多

解決思路

//必須要能讀取這個內(nèi)容  

        BufferedReader br = new BuffedReader(new FileInputStream(new File("c:/big.txt")));
          // 每次讀取一行
        String line = null;
        while( (line=br.readLine()) != null){
            // 處理這讀取到的一行內(nèi)容的代碼
        }

        //最簡單的一種思路：  初始化一個hashmap

        //hashmap中存儲的鍵值對的  key ： IP      value : 次數(shù)

        int count = 0;  // 就是用來進行存儲當(dāng)前出現(xiàn)次數(shù)最多的那個IP的次數(shù)
        String maxip = null;
        Set<String> ips = hashmap.keySet();
        for(String ip :  ips){
            int ipcount = hashmap.get(ip)
            if(ipcount > count){
                count = ipcount
                maxip = ip;
            }
        }
        System.out.println(maxip + " : " +count);

問題難點

1、當(dāng)讀取的文件的大小超過內(nèi)存的大小時，以上的解決方案是不可行的。

2、假如說你的內(nèi)存足夠大，能裝下這個文件中的所有ip，整個任務(wù)的執(zhí)行效率會非常低，消耗的時間會非常的長。

　　1GB -- 5分

　　1TB --- 1024 * 5 分

3、最終整個任務(wù)就使用一臺機器，那么最終整個任務(wù)執(zhí)行完成所消耗的時間是和數(shù)據(jù)的大小成正比。提升服務(wù)器的執(zhí)行性能來提高數(shù)據(jù)的處理速度。

　　　　當(dāng)前這一臺機器的執(zhí)行性能： 　　　　     5分鐘/GB

　　　　提升服務(wù)器的執(zhí)行性能： CPU ：i3 ---> i7 1分鐘/GB

在最開始的服務(wù)器領(lǐng)域：提升服務(wù)器對外提供服務(wù)的效率手段就是縱向提升服務(wù)器性能。理想是豐滿的，現(xiàn)實是骨感的，但是服務(wù)器性能提升有瓶頸。

摩爾定律：每隔18-24個月，服務(wù)器的性能提升一倍。

如果說數(shù)據(jù)的增長是每隔18-24個月就增長一倍,工作量增加了一倍。工作效率也增加了一倍，那么最終完成同一個任務(wù)所花費的時間是一樣的。

但是數(shù)據(jù)的增長速度是遠遠超過服務(wù)器性能的提升。在數(shù)據(jù)不斷增長的情況下，單位時間內(nèi)，服務(wù)器所需要處理的數(shù)據(jù)量是越來越大。

假如：

服務(wù)器的性能提升 速率 和 數(shù)據(jù)的增長速率一樣： 在18-24個月
10GB --- 性能： 1分鐘/GB --- 10分鐘
20GB --- 性能： 1分鐘/2GB --- 10分鐘

假如：

服務(wù)器的性能提升 速率 和 數(shù)據(jù)的增長速率不一樣： 在18-24個月
10GB --- 性能： 1分鐘/GB --- 10分鐘
100GB --- 性能： 1分鐘/2GB --- 50分鐘

最終的結(jié)論： 靠 縱向提升服務(wù)器性能的手段 在理論上有 瓶頸的。

最終解決方案：縱向不可取，所以采取橫向擴展。

所謂的橫向擴展：就是增加服務(wù)器的數(shù)量。

一個龐大的復(fù)雜任務(wù)就應(yīng)該 平均分配給所有的服務(wù)器做處理

10GB 一臺服務(wù)器 10分鐘

100GB 一臺服務(wù)器 100分鐘

100GB 10臺服務(wù)器 10分鐘

10000GB 1000臺 10分鐘

在理論上 有上限么？？沒有

兩種情況下：
1、在數(shù)據(jù)量比較小的情況下，單臺服務(wù)器就可以再用戶可接受的時限范圍內(nèi)完成任務(wù)。
2、當(dāng)數(shù)據(jù)量變大時，如果用戶也想在可接受的時限范圍內(nèi)完成任務(wù)，那么可行的方案就是進行服務(wù)器的橫向擴展。

核心思想： 大事化小 分而治之
終極解決方案：
1、先把文件切碎成很多的小文件。
2、每一個服務(wù)器節(jié)點去處理一個小文件。
3、再把所有服務(wù)器的處理結(jié)果匯總到一起。
4、再把所有的數(shù)據(jù)合并到一起求出出現(xiàn)次數(shù)最多的那個ip。

只要是通過網(wǎng)絡(luò)傳輸數(shù)據(jù)，就一定存在丟失數(shù)據(jù)的可能。

第二題

問題描述

在兩個龐大文件中，文件也都是存儲的URL地址（每行一個），比如文件名叫做file1和file2, 找出這兩個文件中的交集（相同的URL）？

以上問題等同于SQL：select url from file1 a join file2 b on a.url = b.url

問題分析

概念：出現(xiàn)在在file1中的元素也出現(xiàn)在file2中。這些元素的集合就是交集

需求：求2個文件的交集

文件中的元素：URL

解決方案

1.當(dāng)2個文件都比較小的時候

　　步驟：

　　　　1.　編寫一個程序可以去讀文件的內(nèi)容，把文件中的所有元素都放置在一個set1中

　　　　　　　　編寫一個流處理取讀取文件內(nèi)容，逐行讀取，每次讀取到的一行放入set1中

　　　　2.　運行相同的程序處理另外一個文件的內(nèi)容，把文件中的所有元素都放置在一個set2中

　　　　3.　先遍歷一個集合，每次遍歷出來的元素都去另外一個集合中判斷存在不存在。如果存在，就是共同元素，這個共同元素就存儲在某個集合中resultSet；如果不存在，就不是共同元素。

　　　　4.　結(jié)果集：集合resultSet

2.當(dāng)2個文件都比較大的時候

　　第一種思路：采取跟第一個題目一樣的大事化小的策略

　　第二種思路：改良第一種思路。避免第一種思路中的很多無效匹配　a1 * a2

　　　　　　　　必須做到合理的數(shù)據(jù)分區(qū)，數(shù)據(jù)分區(qū)的兩種最基本的思路：

　　　　　　　　　　1.先排序，然后分段==分區(qū)

　　　　　　　　　　2.hash散列　　--　　求hash值，然后利用hash值求和分區(qū)個數(shù)的余數(shù)，如果余數(shù)相同，就證明這些元素在同一個分區(qū)中

　　　　　　　　改良了實現(xiàn)思路之后，可以讓原來應(yīng)該執(zhí)行16個小任務(wù)的大任務(wù)。只需要執(zhí)行4個小任務(wù)即可。

終極解決方案：

1.先指定一個分區(qū)策略：hash散列

2.預(yù)估預(yù)估一下數(shù)據(jù)要被切分成多少個塊，一定要保證兩個文件切分出來的小文件個數(shù)成倍數(shù)

3.根據(jù)hash散列的策略，對兩份文件分別進行操作

4.根據(jù)原來指定的策略，尋找對應(yīng)的兩個大文件中的對應(yīng)小文件進行求交集操作

5.所有的結(jié)果，根本就不用再進行去重了。直接進行拼接即可。

學(xué)到的東西：

　　整個大數(shù)據(jù)生態(tài)系統(tǒng)中的很多技術(shù)軟件的底層處理數(shù)據(jù)的分區(qū)時，默認(rèn)的策略都是hash散列。

第三題

問題描述

現(xiàn)在有一個非常龐大的URL庫（10000E），然后現(xiàn)在還有一個URL，（迅速）判斷這個URL是否在這個URL庫中？

問題分析

需求：判斷一個元素在不在某個集合中

解決方案

1、計數(shù)排序

1、初始化一個數(shù)組 數(shù)組的長度 就是 集合中元素的區(qū)間長度

2、遍歷集合，把每個元素放入數(shù)組中 尋找對應(yīng)的下標(biāo)位置，找出值，然后重新設(shè)置成+1的值

3、按序遍歷即可

array[0] = 1, array[1] = 2, array[2] = 0, array[3] = 3,

0 1 1 3 3 3

2、改進需求：

求出某個元素在不在這個數(shù)組（數(shù)據(jù)結(jié)構(gòu)改良之前的集合）中

array[5] = count if count > 0

3、既然是判斷存在不存在。

所以結(jié)果其實就是一個狀態(tài) ： 要么存在 要么不存在

存在 ： 1
不存在： 0

把int數(shù)組進化成 為位數(shù)組

優(yōu)勢：把數(shù)組所要消耗的內(nèi)存降低到原來的 1/32

改良了之后這種數(shù)據(jù)結(jié)構(gòu)： BitMap

真正的結(jié)構(gòu)： 一個位數(shù)組 + 一個hash函數(shù)

4、BitMap再次進行進化

解決的問題： BitMap 中非常容易出現(xiàn) hash碰撞的問題

咱們可以結(jié)合使用多個hash函數(shù)來搞定

缺點： 存在一定的誤判率

1、如果這種數(shù)據(jù)結(jié)構(gòu)（BloomFilter） 告訴你說你要驗證的那個元素不在這個 BloomFilter 中
那就表示 這個元素一定不在這個 BloomFilter 中

2、如果它告訴你這個元素存在， 它告訴你的這個存在的結(jié)果 有可能是假的

真正的組成：

一個位數(shù)組 + 一組hash函數(shù)

如果要做工程實現(xiàn)：不管是什么變種的BloomFilter， 都一定要實現(xiàn)兩個方法：

1、第一個方法是往BloomFilter中存入一個元素

2、第二個方法是驗證一個元素是否在這個BloomFilter 中

誤判率的估計：

1、位數(shù)組的長度 m

2、總元素的個數(shù) n

3、hash函數(shù)的個數(shù) k

hash函數(shù)的個數(shù) 并不是越多越好

在誤判率最低的情況下。 這三個參數(shù)應(yīng)該滿足的一個公式： k = 0.7 * m / n