本文關(guān)鍵詞：算法，由筆耕文化傳播整理發(fā)布。

【CSDN報道】幾天前，CSDN編譯了國外AddThis公司的數(shù)據(jù)分析副總監(jiān)Matt Abrams在High Scalability上發(fā)表的一篇文章，Matt Abrams在這篇文章中向讀者介紹了AddThis僅用了1.5KB內(nèi)存就計算了十億個不同的對象，充分展示了算法的魅力。

這篇文章在微博上得到了廣泛關(guān)注，并得知一淘的算法也同樣出彩。為此，CSDN采訪了一淘數(shù)據(jù)部的張洋（他曾先后就讀于煙臺大學和北京航空航天大學，2011年在北京航空航天大學取得計算機理論碩士學位，同年加入淘寶，目前在一淘數(shù)據(jù)部工作），請他講解一下一淘的相關(guān)算法。

圖：一淘數(shù)據(jù)部工程師 張洋

CSDN：首先請您介紹一下自己以及平時的工作？

張洋：我叫張洋，在公司的花名是夜沨。目前是一淘數(shù)據(jù)部一名普通碼農(nóng)，和千千萬萬碼農(nóng)一樣，每天以敲代碼寫程序為工作，同時也將其視為人生第二大樂趣（第一大樂趣是吃）。我對PHP、Nginx、數(shù)據(jù)挖掘、機器學習、算法、編譯器和分布式存儲計算等技術(shù)興趣濃厚，喜愛數(shù)學和歷史。我很喜歡寫程序這個工作，也希望能將編程作為畢生的職業(yè)。寫程序之余也喜歡研究數(shù)學和算法，同時我很樂于將自己學到的東西總結(jié)成文章發(fā)表在博客上和大家分享，有興趣的朋友可以來我博客逛逛：codinglabs.org。

我在一淘數(shù)據(jù)部的職位是前端開發(fā)，但是我這個“前端開發(fā)”比一般意義上的前端工程師做的事要雜一些，除了負責HTML、CSS和JavaScript外，也開發(fā)PHP、Lua的后臺程序，偶爾也會根據(jù)興趣和需要來開發(fā)一些C和算法的程序（我很喜歡寫C和算法，，十分樂在其中），同時我還做一些運維工作，例如搭建服務(wù)器環(huán)境和維護線上服務(wù)器。

CSDN：是什么原因促使您對算法感興趣的？

張洋：可能是源自我對數(shù)學的興趣吧，我一直很喜歡數(shù)理性的東西。正式接觸算法是大二的時候，當時買了一本算法導論，才真正開始了解漸近復(fù)雜度、算法分析、動態(tài)規(guī)劃、貪心算法、NP問題等一系列算法領(lǐng)域最基本的東西�？吹臅r候就覺得很神奇，感覺書中的每個算法都閃耀著人類的智慧，閱讀和學習這些東西給我?guī)硪环N難以用語言表達的滿足感和快感。在后來的學習和工作中我不斷從實際應(yīng)用中了解和領(lǐng)會算法是如何解決各個領(lǐng)域的實際問題，推動人類文明的發(fā)展，這更加深了我對算法的崇敬。

CSDN：一淘數(shù)據(jù)部為什么會開發(fā)這個基數(shù)估計算法？

張洋：一淘數(shù)據(jù)部主要在電子商務(wù)領(lǐng)域做一些數(shù)據(jù)的分析挖掘，并將這些技術(shù)與業(yè)務(wù)緊密結(jié)合形成一些數(shù)據(jù)產(chǎn)品和服務(wù)，例如數(shù)據(jù)分析、推薦系統(tǒng)等我們都有做。這些數(shù)據(jù)產(chǎn)品既對外服務(wù)，也會對公司或集團內(nèi)部的運作提供支持。

在電子商務(wù)的數(shù)據(jù)分析領(lǐng)域有一些很關(guān)鍵的指標（例如unique visitor，簡稱UV，指在一定的時間空間維度約束下獨立訪客的數(shù)量）的計算是很常見的任務(wù)。一般來說我們首先會通過某種手段給每一個獨立訪客做一個標記（例如通過cookie），然后會在所有訪問日志中記錄下訪客的標記，這樣一來，UV的計算就等價為在一個可重復(fù)的用戶標記集合中計算不重復(fù)元素的個數(shù)，也就是數(shù)學上的基數(shù)。

基數(shù)的計算有兩個難點：

一是不利于實時流計算的實現(xiàn)。例如我們的一些產(chǎn)品中經(jīng)常會提供實時UV，也就是從某個時間點開始（例如今天零點）到目前的獨立訪客數(shù)。為了做到這點，需在內(nèi)存中為每一個UV數(shù)值維護一個查找性能高的數(shù)據(jù)結(jié)構(gòu)（例如B樹），這樣當實時流中新來一個訪問時，能快速查找這個訪客是否已經(jīng)來過，由此確定UV值是增加1還是不變。如果我們要為100萬家店鋪同時提供這種服務(wù)，就要在內(nèi)存中維護100萬個B樹，而如果還要分不同來源維度計算UV的話，這個數(shù)量還會迅速膨脹。這對我們的服務(wù)器計算資源和內(nèi)存資源都是一個很大的挑戰(zhàn)。

第二點就是傳統(tǒng)的基數(shù)計算方法無法有效合并。例如，前一小時和這一小時的UV雖然分別計算出來了，但是要看這兩個小時的總UV依然要重新進行一遍復(fù)雜的計算。使用bitmap數(shù)據(jù)結(jié)構(gòu)的方案雖然可以快速合并，但是空間復(fù)雜度太高，因為時間段的任意組合數(shù)量與時間段數(shù)量呈冪級關(guān)系，所以不論是B樹還是簡單的bitmap在大數(shù)據(jù)面前都不是一個有效的方案。

基于以上背景，一淘數(shù)據(jù)部的技術(shù)專家王曉哲（花名清無）研究了基數(shù)估計的相關(guān)算法及Clearspring的一個java實現(xiàn)（stream-lib），并率先在我們的全息效果平臺（代號月光寶盒）的項目中引入了基數(shù)估計算法，目前已成功實現(xiàn)利用少量內(nèi)存對大量UV進行計算的技術(shù)難題，并承擔了雙十一和雙十二大促中天貓和淘寶所有會場坑位的效果實時計算任務(wù)。

為了方便更多的非Java項目使用此類算法，王曉哲和我根據(jù)相關(guān)論文并參考stream-lib給出了一個C版本的實現(xiàn)ccard-lib，接著一淘數(shù)據(jù)部的工程師張維（花名民瞻）又實現(xiàn)了PHP的擴展。目前這個C的實現(xiàn)已經(jīng)在一淘數(shù)據(jù)部多個產(chǎn)品中開始使用，并且也已經(jīng)。

CSDN：能不能向讀者詳細介紹一下一淘數(shù)據(jù)部的基數(shù)估計算法？

張洋：我們使用的算法主要是Adaptive Counting算法，這個算法出現(xiàn)在 “Fast and accurate traffic matrix measurement using adaptive cardinality counting” 這篇論文里，但是我同時在ccard-lib里也實現(xiàn)了Linear Counting、LogLog Counting和HyperLogLog Counting等常見的基數(shù)估計算法。

這些算法是概率算法，就是通過犧牲一定的準確性（但是精度可控，并可以通過數(shù)學分析給出控制精度的方法），來大幅節(jié)省計算的資源使用。例如我們僅僅使用8k的內(nèi)存就可以對一個數(shù)億量級的UV進行估計，而誤差不超過2%，這比使用B樹或原始bitmap要大幅節(jié)省內(nèi)存。同時基數(shù)估計算法用到了經(jīng)過哈希變換的bitmap空間，在大幅節(jié)省內(nèi)存的同時依然可以實現(xiàn)高效合并，這就同時解決了上面提到的兩個難點。

使用2^16（64K）位時，估算結(jié)果如下：

Linear Counting with Murmurhash:

actual: 50000, estimated: 50062, error: 0.12%

actual: 100000, estimated: 99924, error: 0.08%

actual: 150000, estimated: 149865, error: 0.09%

actual: 200000, estimated: 199916, error: 0.04%

actual: 250000, estimated: 250123, error: 0.05%

actual: 300000, estimated: 299942, error: 0.02%

actual: 350000, estimated: 349801, error: 0.06%

actual: 400000, estimated: 400101, error: 0.03%

actual: 450000, estimated: 449955, error: 0.01%

actual: 500000, estimated: 500065, error: 0.01%

Linear Counting with Lookup3hash:

actual: 50000, estimated: 49835, error: 0.33%

actual: 100000, estimated: 99461, error: 0.54%

actual: 150000, estimated: 149006, error: 0.66%

actual: 200000, estimated: 198501, error: 0.75%

actual: 250000, estimated: 248365, error: 0.65%

actual: 300000, estimated: 298065, error: 0.65%

actual: 350000, estimated: 347504, error: 0.71%

actual: 400000, estimated: 397292, error: 0.68%

actual: 450000, estimated: 446700, error: 0.73%

actual: 500000, estimated: 495944, error: 0.81%

Hyperloglog Counting with Murmurhash:

actual: 50000, estimated: 50015, error: 0.03%

actual: 100000, estimated: 100048, error: 0.05%

actual: 150000, estimated: 149709, error: 0.19%

actual: 200000, estimated: 201595, error: 0.80%

actual: 250000, estimated: 250168, error: 0.07%

actual: 300000, estimated: 299864, error: 0.05%

actual: 350000, estimated: 348571, error: 0.41%

actual: 400000, estimated: 398583, error: 0.35%

actual: 450000, estimated: 448632, error: 0.30%

actual: 500000, estimated: 498330, error: 0.33%

Hyperloglog Counting with Lookup3hash:

actual: 50000, estimated: 49628, error: 0.74%

actual: 100000, estimated: 99357, error: 0.64%

actual: 150000, estimated: 148880, error: 0.75%

actual: 200000, estimated: 200475, error: 0.24%

actual: 250000, estimated: 249362, error: 0.26%

actual: 300000, estimated: 299119, error: 0.29%

actual: 350000, estimated: 349225, error: 0.22%

actual: 400000, estimated: 398805, error: 0.30%

actual: 450000, estimated: 448373, error: 0.36%

actual: 500000, estimated: 498183, error: 0.36%

Adaptive Counting with Murmurhash:

actual: 50000, estimated: 50015, error: 0.03%

actual: 100000, estimated: 100048, error: 0.05%

actual: 150000, estimated: 149709, error: 0.19%

actual: 200000, estimated: 201059, error: 0.53%

actual: 250000, estimated: 249991, error: 0.00%

actual: 300000, estimated: 300067, error: 0.02%

actual: 350000, estimated: 349610, error: 0.11%

actual: 400000, estimated: 399875, error: 0.03%

actual: 450000, estimated: 450348, error: 0.08%

actual: 500000, estimated: 500977, error: 0.20%

Adaptive Counting with Lookup3hash:

actual: 50000, estimated: 49628, error: 0.74%

actual: 100000, estimated: 99357, error: 0.64%

actual: 150000, estimated: 148880, error: 0.75%

actual: 200000, estimated: 199895, error: 0.05%

actual: 250000, estimated: 249563, error: 0.17%

actual: 300000, estimated: 299047, error: 0.32%

actual: 350000, estimated: 348665, error: 0.38%

actual: 400000, estimated: 399266, error: 0.18%

actual: 450000, estimated: 450196, error: 0.04%

actual: 500000, estimated: 499516, error: 0.10%

Loglog Counting with Murmurhash:

actual: 50000, estimated: 59857, error: 19.71%

actual: 100000, estimated: 103108, error: 3.11%

actual: 150000, estimated: 150917, error: 0.61%

actual: 200000, estimated: 201059, error: 0.53%

actual: 250000, estimated: 249991, error: 0.00%

actual: 300000, estimated: 300067, error: 0.02%

actual: 350000, estimated: 349610, error: 0.11%

actual: 400000, estimated: 399875, error: 0.03%

actual: 450000, estimated: 450348, error: 0.08%

actual: 500000, estimated: 500977, error: 0.20%

Loglog Counting with Lookup3hash:

actual: 50000, estimated: 59870, error: 19.74%

actual: 100000, estimated: 103044, error: 3.04%

actual: 150000, estimated: 150435, error: 0.29%

actual: 200000, estimated: 199895, error: 0.05%

actual: 250000, estimated: 249563, error: 0.17%

actual: 300000, estimated: 299047, error: 0.32%

actual: 350000, estimated: 348665, error: 0.38%

actual: 400000, estimated: 399266, error: 0.18%

actual: 450000, estimated: 450196, error: 0.04%

actual: 500000, estimated: 499516, error: 0.10%

限于篇幅，我在這里不能具體描述這些算法的細節(jié)，之前我在博客上發(fā)表了一篇翻譯的文章，不過內(nèi)容也是概括性描述。但是我已經(jīng)在準備寫博文詳細介紹基數(shù)估計算法了，那里面會包括算法的數(shù)理細節(jié)以及對論文的一些解讀，歡迎有興趣的朋友關(guān)注我的博客。

CSDN：看到您微博上自稱“代碼潔癖重度患者”，這是一個很有趣的稱呼，那么是否可以理解為您對代碼的規(guī)范性很在意，您在平時在編碼過程中如何保持代碼的規(guī)范？

張洋：這么說其實是有點自嘲的意思吧。對代碼格式我確實是很在意的，如果看到代碼不規(guī)范、不整齊甚至多一個空行我都會覺得非常不舒服，骨子里對代碼格式有一種完美主義傾向。

不過這個事情要分兩面看，如果是我自己開發(fā)的比較專的東西，如算法庫，可以堅持這種完美主義，但需要多人合作的場合實際上是不太合適的。實事求是的說，業(yè)務(wù)代碼總是不可能一直很漂亮，需要在業(yè)務(wù)進度和代碼質(zhì)量中間做一個權(quán)衡。在保持代碼規(guī)范方面，我始終認為不能完全靠程序員的自覺和代碼規(guī)范的宣講，通過工具（例如lint）和流程去保證會更有效一些。

CSDN：還有哪些困難是需要在未來工作中克服的？

張洋：需要克服的困難主要來自兩方面吧。

一方面是算法本身改進的困難，這世界不存在完美無暇的算法，例如上面的基數(shù)估計算法，雖然大大降低了內(nèi)存使用，但是如果維度爆炸的話，內(nèi)存使用仍然會很夸張，而且合并bitmap也不是沒有代價，有時需要進行內(nèi)存和磁盤bitmap的合并，當bitmap量過大時磁盤IO會稱為瓶頸，因此如何結(jié)合具體場景來優(yōu)化和改進算法就成為一個難點。一個方法是查閱相關(guān)論文，了解和借鑒目前全球各大研究機構(gòu)和公司對相關(guān)算法的最新研究成果。另一個方法就是自己進行改進，這塊需要對算法本身極其相關(guān)的數(shù)學分析有非常深入掌握，因此對相關(guān)工程師的理論水平要求較高。

另一方面就是算法和業(yè)務(wù)產(chǎn)品的結(jié)合方案。算法畢竟是較為形式化的東西，要具體應(yīng)用到產(chǎn)品中還有很長一段路要走。尋求算法與產(chǎn)品的最佳契合點和結(jié)合方案也是工作中的重點和難點之一。

2012已經(jīng)過去，我們度過了世界末日，迎來世界新篇章。在2013年，我們也會進入互聯(lián)網(wǎng)發(fā)展的新時代，各種數(shù)據(jù)充斥在網(wǎng)絡(luò)中，大數(shù)據(jù)成為各個互聯(lián)網(wǎng)公司都要面對的問題之一。如何消耗最小的資源來獲得盡可能多的有用信息，這應(yīng)該是每個互聯(lián)網(wǎng)公司都要考慮的問題。通過最近關(guān)于算法的兩篇文章，想必各位讀者都能心中有數(shù)。當然，每種算法都有各自的優(yōu)缺點，我們還是要根據(jù)在平時工作中的實際使用情況來對算法進行選擇，不能一概而論。（王旭東/作者 包研/審校）

擴展閱讀：大數(shù)據(jù)計數(shù)：如何僅用1.5KB內(nèi)存為十億對象計數(shù)

  本文關(guān)鍵詞：算法，由筆耕文化傳播整理發(fā)布。

本文編號：127553