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

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

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

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

CSDN：首先請(qǐng)您介紹一下自己以及平時(shí)的工作？

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

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

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

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

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

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

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

基數(shù)的計(jì)算有兩個(gè)難點(diǎn)：

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

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

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

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

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

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

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

使用2^16（64K）位時(shí)，估算結(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%

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

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

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

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

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

張洋：需要克服的困難主要來(lái)自兩方面吧。

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

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

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

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

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

本文編號(hào)：127553