最近被調(diào)過(guò)去做日志分析系統(tǒng)侦镇，接觸所謂的大數(shù)據(jù)曲伊。學(xué)校的時(shí)候也做過(guò)空間數(shù)據(jù)庫(kù)索引與數(shù)據(jù)挖掘研究（LBS方向）燃观，但是工作3年一直做通信協(xié)議褒脯，有些東西也忘掉了。面對(duì)茫茫前途缆毁，討厭這種模糊不清的狀態(tài)番川，因此，計(jì)劃系統(tǒng)學(xué)習(xí)理論并用于實(shí)踐脊框。后續(xù)會(huì)寫(xiě)一點(diǎn)相關(guān)的技術(shù)學(xué)習(xí)記錄颁督。
??本周寫(xiě)一下基本的亞線性算法，這里要感謝哈工大的王宏志老師的講義浇雹。
??大數(shù)據(jù)這個(gè)字眼在當(dāng)今生活中隨處可見(jiàn)沉御，比如：某某基于大數(shù)據(jù)的社交網(wǎng)絡(luò)分析、基于大數(shù)據(jù)的醫(yī)療分析昭灵、基于大數(shù)據(jù)的政企數(shù)據(jù)分析吠裆、基于大數(shù)據(jù)的金融分析等等。
??那什么是大數(shù)據(jù)烂完？網(wǎng)上給出的定義有很多請(qǐng)自行谷歌或百度试疙。這里說(shuō)一下我看到的一種定義：
??“大數(shù)據(jù)”就是一種需要新的處理方式才能具有更強(qiáng)決策力、洞察發(fā)現(xiàn)力和流程優(yōu)化能力的海量抠蚣、高增長(zhǎng)率和多樣化的信息資產(chǎn)祝旷。
??從定義上，我們可以獲取的信息有：新的處理方式柱徙、大數(shù)據(jù)的作用（決策缓屠、發(fā)現(xiàn)奇昙、流程優(yōu)化）护侮、以及它的特點(diǎn)（海量 、高增長(zhǎng)率储耐、多樣化）羊初。哈哈，注意對(duì)我來(lái)說(shuō)有個(gè)更關(guān)鍵的詞資產(chǎn)什湘，我的潛意識(shí)“資產(chǎn)==錢(qián)”长赞，那它就有研究?jī)r(jià)值了。
??上面定義說(shuō)我們需要新的處理方式闽撤，為什么呢得哆？因?yàn)?em>大數(shù)據(jù) 具有4V特點(diǎn)（很多文章定義為3V）：數(shù)據(jù)量（Volume）、速度（Velocity）哟旗、多樣性（Variety）贩据、價(jià)值（Value）栋操。有了這些特性就給我們處理 大數(shù)據(jù) 帶來(lái)如下困難：

1. 無(wú)法在有限時(shí)間內(nèi)讀取所有數(shù)據(jù)。有人會(huì)說(shuō)現(xiàn)在到處大數(shù)據(jù)平臺(tái)hadoop讀寫(xiě)數(shù)據(jù)怎么會(huì)說(shuō)無(wú)法讀取所有數(shù)據(jù)呢饱亮？我理解是要注意有限時(shí)間內(nèi)矾芙！用戶在電商網(wǎng)站買(mǎi)個(gè)充氣娃娃，如果處理慢了近上，等用戶離開(kāi)了網(wǎng)站剔宪，再提供推薦結(jié)果已經(jīng)沒(méi)有任何意義了。
2. 數(shù)據(jù)難以存放在內(nèi)存上壹无。數(shù)據(jù)量很大葱绒，內(nèi)存是有限而且相對(duì)于磁盤(pán)更貴。因此更多數(shù)據(jù)是存放在磁盤(pán)上斗锭。能夠用于計(jì)算的數(shù)據(jù)必須是在內(nèi)存上哈街。
3. 單一的計(jì)算機(jī)已經(jīng)沒(méi)辦法存儲(chǔ)和計(jì)算整體數(shù)據(jù)。其實(shí)這個(gè)問(wèn)題算是1拒迅、2的結(jié)合了骚秦。這提示我們擴(kuò)大硬件數(shù)目。
4. 計(jì)算機(jī)的計(jì)算能力和知識(shí)不足璧微。這個(gè)指光靠計(jì)算機(jī)不行了要靠人的知識(shí)參與作箍，人工智能要在大數(shù)據(jù)領(lǐng)域發(fā)揮巨大作用了。

所以前硫，我們要采用新的處理方式了胞得。問(wèn)題1，有限時(shí)間內(nèi)我們可以犧牲精度采用近似算法讀取部分?jǐn)?shù)據(jù)（比如抽樣算法）來(lái)計(jì)算結(jié)果屹电，這也引出來(lái)我們接下來(lái)要介紹的時(shí)間亞線性算法阶剑。問(wèn)題2，有限的內(nèi)存空間危号，根據(jù)問(wèn)題1的講述牧愁，我們肯定會(huì)想到采用近似算法讀取少量數(shù)據(jù)僅內(nèi)存，空間亞線性算法也出來(lái)了外莲；同時(shí)猪半，既然數(shù)據(jù)要存到外存那么相關(guān)的外存算法。問(wèn)題3偷线，單一不行我們自然想到了并行計(jì)算磨确，并行計(jì)算目前使用廣泛的計(jì)算框架有hadoop、spark等（后續(xù)會(huì)有系列文檔來(lái)聊聊我的學(xué)習(xí)經(jīng)歷和目前做的日志分析系統(tǒng)）声邦。問(wèn)題4乏奥，暫且不提了，后續(xù)再聊亥曹。
??大數(shù)據(jù)算法設(shè)計(jì)與分析邓了，顧名思義兩方面：設(shè)計(jì)與分析盏檐。算法有但不限于：精確算法設(shè)計(jì)（我們學(xué)校上的算法課，后續(xù)也要好好整理整理）驶悟、近似算法胡野、并行算法、外存算法痕鳍、隨機(jī)算法硫豆、在線/數(shù)據(jù)流算法、面向新體系結(jié)構(gòu)算法（硬件比如GPU笼呆、FPGA<業(yè)內(nèi)已經(jīng)很多家涉入其中比如微軟熊响、華為、中興等>）诗赌、現(xiàn)代優(yōu)化算法汗茄。分析：時(shí)間空間復(fù)雜性（有算法就有它）、IO復(fù)雜性（并行計(jì)算通信復(fù)雜度铭若、外存算法IO復(fù)雜度）洪碳、結(jié)果質(zhì)量（既然采用了近似計(jì)算、隨機(jī)算法那么就存在結(jié)果質(zhì)量的問(wèn)題叼屠，關(guān)鍵看誤差在不在你容忍的范圍內(nèi)）瞳腌。
??扯了半天廢話，估計(jì)大家也煩了镜雨，下面進(jìn)入正題：亞線性算法嫂侍。

1. 亞線性算法定義

時(shí)間/空間/通訊/IO等消耗復(fù)雜度為o（輸入規(guī)模n）的算法。主要有兩種：空間亞線性算法荚坞、時(shí)間亞線性算法挑宠。

1. 空間亞線性算法---水庫(kù)抽樣算法

空間亞線性算法顧名思義就是想我們?cè)谛∮诰€性O(shè)(n)的空間復(fù)雜度完成目標(biāo)，內(nèi)存有限是其特征颓影。
? ?這里我以水庫(kù)抽樣算法為例聊聊一下有限空間約束下各淀，我們?nèi)绾瓮瓿稍O(shè)下的目標(biāo)。

問(wèn)題描述：
輸入：一組源源不斷的數(shù)據(jù)流瞭空，數(shù)據(jù)大小未知
輸出：這個(gè)數(shù)據(jù)流的K個(gè)均勻抽樣
要求：每個(gè)數(shù)據(jù)僅能讀取一遍揪阿；可用空間為K疗我；當(dāng)數(shù)據(jù)累計(jì)個(gè)數(shù)為n時(shí)（n>K）咆畏，保存當(dāng)前已掃描數(shù)據(jù)的K個(gè)均勻抽樣。

首先明確什么叫均勻抽樣吴裤，大家肯定都知道就是每個(gè)數(shù)據(jù)被等概率抽取唄旧找。
? ?那我們就分開(kāi)想想，如果就只有n=K個(gè)元素麦牺，可用空間正好也是K钮蛛，那我們正好把K個(gè)數(shù)據(jù)都保存起來(lái)鞭缭，均勻吧！每個(gè)掃描到的數(shù)據(jù)都存起來(lái)了魏颓！
? ?但是如果n>K呢岭辣？要想均勻抽樣，概率當(dāng)然是

蛋疼的簡(jiǎn)書(shū)不能用LaTeX

• a. 每個(gè)新到達(dá)的元素 i 被選人有限空間（K數(shù)組）的概率是K/i;
• b. 第n個(gè)元素過(guò)來(lái)的時(shí)候我們之前選取的元素還在有限空間內(nèi)的話，那么它的概率應(yīng)該是K/n就可以了叹话。

如果能驗(yàn)證證明就可以了偷遗，因此，方法一如下：
??空間總共K個(gè)驼壶，第i個(gè)元素過(guò)來(lái)的時(shí)候氏豌，它以K/i的概率被抽取，第n過(guò)來(lái)的時(shí)候它被抽取到的概率是k/n热凹。即求第n個(gè)元素的過(guò)來(lái)的時(shí)候它留在K個(gè)空間的概率：

蛋疼的簡(jiǎn)書(shū)不能用LaTeX

void getRandomSamplesK(int *pdataStream, int n, int k)
{
    int i = 0;
    int *randomSampleK = (int*)malloc(k*sizeof(int));
    int r = 0;
    int replaceIndex = 0;
    int j = 0;
    if(NULL == randomSampleK)
    {
        return;
    }
    for(;i<k;i++)
    {
        randomSampleK[i]=pdataStream[i];
    }
    for(;i<n;i++)
    {
        srand((unsigned int)time(NULL));
        r = (int)rand();
        replaceIndex = r%i;
        if(replaceIndex<k)//被選中替換的概率(k/i+1)*(1/k)
        {
            randomSampleK[replaceIndex] = pdataStream[i];
        }
    }
    for(;j<k;j++)
    {
        printf("%d ",randomSampleK[j]);
    }
    free(randomSampleK);
    return ;
}

方法二，利用數(shù)學(xué)歸納法證明：

前提：（1）前K個(gè)元素被等概率選中的概率為1般妙；（2）已掃描的n個(gè)元素被等概率抽樣的概率為k/n涣旨；即第n個(gè)新來(lái)的元素被選中的概率為k/n。
假設(shè)：第i（i>k）個(gè)元素被抽中的概率為k/i股冗；原蓄水池中的元素仍舊在蓄水池中的概率為k/i;
證明目標(biāo)：第i+1個(gè)元素被抽中的概率為k/（i+1）霹陡；原蓄水池中的元素仍舊在的概率為k/(i+1)；
證明：
（1）第i+1個(gè)元素被抽中的概率為k/（i+1）止状；
（2）根據(jù)假設(shè)第i個(gè)元素到來(lái)烹棉，原蓄水池元素概率為k/i；事件A={第i+1個(gè)元素被抽中后怯疤，原元素仍舊在蓄水池}的對(duì)立事件為B={第i+1個(gè)元素被抽中后浆洗，原元素被替換}。因此：
P(A) = 1-P(B);
因?yàn)槭录﨏={掃描了i+1個(gè)元素集峦，原蓄水池中元素仍在}是串聯(lián)：原元素在蓄水池伏社，第i+1沒(méi)有替換原元素；
所以：

蛋疼的簡(jiǎn)書(shū)不能用LaTeX

本小節(jié)總結(jié)：本節(jié)通過(guò)一個(gè)面試經(jīng)常遇到題目講述了空間亞線性算法通過(guò)有限的內(nèi)存空間來(lái)獲得了一個(gè)數(shù)據(jù)流的抽樣信息塔淤，這里注意雖然我們做了抽樣但是卻沒(méi)有近似摘昌，不是所有抽樣算法都是近似算法。學(xué)習(xí)算法一方面是為了鍛煉自己的邏輯思維高蜂；更重要的是要學(xué)以致用聪黎，要知道算法的應(yīng)用場(chǎng)景！蓄水池抽樣算法最直觀的應(yīng)用就獲取隨機(jī)數(shù)（不是庫(kù)函數(shù)提供的偽隨機(jī)數(shù)）备恤，后續(xù)會(huì)整理講述的算法的應(yīng)用場(chǎng)景稿饰，這里mark一下锦秒！

2. 空間亞線性算法---數(shù)據(jù)流中最頻繁元素

上一小節(jié)分享的蓄水池抽樣算法雖然是抽樣算法卻不是近似算法。本節(jié)分享一下有限內(nèi)存利用近似解求數(shù)據(jù)流中最頻繁的元素喉镰。
??先講解一下大數(shù)據(jù)的數(shù)據(jù)流模型特點(diǎn)：

1. 數(shù)據(jù)只能掃描1次或幾次旅择；
2. 能夠使用的內(nèi)存是有限的（內(nèi)存<<數(shù)據(jù)規(guī)模）；
3. 希望通過(guò)維護(hù)一個(gè)內(nèi)存結(jié)果（數(shù)據(jù)流概要）來(lái)給出相關(guān)性質(zhì)的一個(gè)評(píng)估侣姆；

總結(jié)來(lái)說(shuō)：數(shù)據(jù)要快速處理砌左；空間亞線性。

問(wèn)題描述：
輸入：大數(shù)據(jù)流序列<x1,x2,x3... ...>铺敌。
輸出：找出數(shù)據(jù)流中當(dāng)前掃描的元素序列中出現(xiàn)最頻繁的元素的信息汇歹。
問(wèn)題分析：當(dāng)前已掃描元素?cái)?shù)目m，元素種類n偿凭，內(nèi)存可用單元數(shù)k产弹，n>>k。

元素種類為n弯囊，如果分配n個(gè)計(jì)數(shù)器統(tǒng)計(jì)個(gè)數(shù)痰哨，最后比較得到值最大的那個(gè)元素就是最頻繁的元素，計(jì)數(shù)器的值就是其出現(xiàn)的次數(shù)匾嘱。但是這里要求n>>k斤斧。怎么辦呢？

算法： 當(dāng)一個(gè)元素x1到來(lái)霎烙，

• IF x1 所屬類的計(jì)數(shù)器在內(nèi)存中不存在且內(nèi)存中有空閑的計(jì)數(shù)器撬讽，THEN 給x1分配一個(gè)計(jì)數(shù)器，計(jì)數(shù)器值+1悬垃；
• IF x1所屬類的計(jì)數(shù)器在內(nèi)存存在游昼，THEN x1對(duì)應(yīng)的計(jì)數(shù)器+1；
• IF x1所屬類的計(jì)數(shù)器在內(nèi)存不存在且內(nèi)存中無(wú)空余的計(jì)數(shù)器尝蠕，THEN k個(gè)計(jì)數(shù)器的值均-1烘豌；當(dāng)計(jì)數(shù)器的值等于0時(shí)，此計(jì)數(shù)器為空閑計(jì)數(shù)器看彼。

實(shí)例化（按照下圖大家應(yīng)該可以能夠自己舉個(gè)例子理解一下）：
32, 12, 14, 32, 7, 12, 32, 7, 6, 12, 4,

markdown畫(huà)圖還沒(méi)有學(xué)好...囧

大家實(shí)例化后肯定會(huì)說(shuō)這個(gè)結(jié)果不準(zhǔn)廊佩。
比如：32, 12, 14, 32, 7, 12, 6, 7, 8, 4（m=10,k=3,n=7）
32：+1，+1靖榕，-1标锄，-1---空閑---8：+1，
12序矩；+1鸯绿，-1，--空閑---12：+1簸淀，-1---空閑---4：+1
14：+1瓶蝴，-1，---空閑---6：+1租幕，-1---空閑---

最頻繁的元素是8舷手、 4，這顯然是有誤差的劲绪。上述算法在什么場(chǎng)景下可以找出最頻繁的元素呢男窟？答案是最頻繁的元素的個(gè)數(shù)超過(guò)m/(k+1)；這樣贾富，最頻繁元素才能抵消其他種類元素而存在于內(nèi)存中歉眷。因此這里有個(gè)很重要的原則：

Zipf原則：典型的概率分布是高度傾斜的，只有少數(shù)的最頻繁元素颤枪。占元素種類10%的元素卻占了元素總個(gè)數(shù)的90%汗捡。

接下來(lái)，如果我們需要知道最頻繁元素出現(xiàn)的次數(shù)的話畏纲，內(nèi)存中的概要數(shù)據(jù)誤差是多少扇住？即該元素的計(jì)數(shù)器被減去了多少？
??分析：每次計(jì)數(shù)器減少會(huì)一次性減少k個(gè)盗胀，另外本次輸入的元素也不再計(jì)入次數(shù)艘蹋，因此一次減少了k+1個(gè)；總共減少了m-a(k個(gè)計(jì)數(shù)器的和)票灰；所以女阀，每個(gè)計(jì)數(shù)器減少了(m-a)/（k+1）個(gè)。

結(jié)論：

• 誤差與內(nèi)存大小K成反比屑迂，說(shuō)明內(nèi)存越大誤差越星科贰；
• 當(dāng)掃描的元素總數(shù)m>>(m-a)/（k+1）屈糊，可以得到一個(gè)好的概要估計(jì)
• 該算法成立前提：Zipf原則

算法算是說(shuō)明白了吧的榛？如果有問(wèn)題請(qǐng)大家隨時(shí)郵件（qiaowei0077@126.com）交流。下面附上找頻繁元素的小代碼逻锐，此問(wèn)題也可以應(yīng)用于一道面試題（尋找發(fā)帖水王夫晌，條件發(fā)的帖子超過(guò)m/k！）昧诱。

/*
*elem:數(shù)據(jù)流中的元素：type：類型晓淀，value：值
*counterArray:計(jì)數(shù)器數(shù)組:counter:技術(shù)，type：元素類型
*counterNum:計(jì)數(shù)器數(shù)目
*/
void findFrequent(Element elem,Counter *counterArray,int counterNum)
{
    /*如果該類型存在盏档，則返回計(jì)數(shù)器ID凶掰；
    *如果該類型不存在且計(jì)數(shù)器有空余，則返回新分配的計(jì)數(shù)器ID；
    *如果該類型不存在且計(jì)數(shù)器無(wú)空余則返回-1懦窘；
    */
    int counterID = getCounter(elem.type,counterArray,counterNum);
    if(-1==counterID)
    {
        for(int i = 0;i<counterNum;i++)
        {
            counterArray[i].counter--;
        }
        return;
    }
    counterArray[counterID].counter++;
    counterArray[counterID].type = elem.type;
    return;
}

第一次寫(xiě)技術(shù)博客前翎，有問(wèn)題請(qǐng)大家指出來(lái)，qiaowei0077@126.com畅涂！