caoporm97国产在线视频|欧美性XXXXX精品|一本一道久久a久久精品综合开|精品久久久久久久久久久AⅤ|

十年專注于品牌網(wǎng)站建設(shè) 十余年專注于網(wǎng)站建設(shè)_小程序開發(fā)_APP開發(fā),低調(diào)、敢創(chuàng)新、有情懷!
南昌百恒網(wǎng)絡(luò)微信公眾號(hào) 掃一掃關(guān)注
小程序
tel-icon全國(guó)服務(wù)熱線:400-680-9298,0791-88117053
掃一掃關(guān)注百恒網(wǎng)絡(luò)微信公眾號(hào)
掃一掃打開百恒網(wǎng)絡(luò)微信小程序

百恒網(wǎng)絡(luò)

南昌百恒網(wǎng)絡(luò)

在線商城海量用戶積分統(tǒng)計(jì)排名算法探討

百恒網(wǎng)絡(luò) 2016-11-08 4810

例如中國(guó)婚慶糖果網(wǎng)有大量用戶的網(wǎng)站,用戶擁有積分,積分可能會(huì)在使用過程中隨時(shí) 更新?,F(xiàn)在要為該網(wǎng)站設(shè)計(jì)?一種算法,在每次用戶登錄時(shí)顯示其 當(dāng)前積分排名。用戶大規(guī)模為2億;積分為非負(fù)整數(shù),且小于 100萬。

存儲(chǔ)結(jié)構(gòu)

首先,我們用?一張用戶積分表user_score來保存用戶的積分信息。

表結(jié)構(gòu):

user_score表結(jié)構(gòu)

示例數(shù)據(jù):

user_score示例數(shù)據(jù)

下面的算法會(huì)基于這個(gè)基本的表結(jié)構(gòu)來進(jìn)行。

算法1:簡(jiǎn)單SQL查詢 首先,我們很容易想到用?一條簡(jiǎn)單的SQL語句查詢出積分大于該用戶積分的用戶數(shù)量:

select 1 + count(t2.uid) as rank from user_score t1, user_score t2 where t1.uid = @uid and t2.score > t1.score

對(duì)于4號(hào)用戶我們可以得到下面的結(jié)果:

SQL查詢

算法特點(diǎn)

優(yōu)點(diǎn):簡(jiǎn)單,利用了SQL的功能,不需要復(fù)雜的查詢邏輯,也不引入額外的存儲(chǔ)結(jié)構(gòu),對(duì)小規(guī)模或性能要求不高的應(yīng)用不失為?一 種良好的解決方案。

缺點(diǎn):需要對(duì)user_score表進(jìn)行全表掃描,還需要考慮到查詢的 同時(shí)若有積分更新會(huì)對(duì)表造成鎖定,在海量數(shù)據(jù)規(guī)模和高并發(fā)的 應(yīng)用中,這樣做性能是無法接受的。

算法2:均勻分區(qū)設(shè)計(jì)

在許多應(yīng)用中緩存是解決性能問題的重要途徑,我們自然會(huì)想:

能不能把用戶排名用Memcached緩存下來呢?不過再?一想發(fā)現(xiàn) 緩存似乎幫不上什么忙,因?yàn)橛脩襞琶?一個(gè)全局性的統(tǒng)計(jì)指 標(biāo),而并非用戶的私有屬性,其他用戶的積分變化可能會(huì)馬上影 響到本用戶的排名。然而,真實(shí)的應(yīng)用中積分的變化其實(shí)也是有 ?一定規(guī)律的,通常?一個(gè)用戶的積分不會(huì)突然暴增暴減,?一般用戶 總是要在低分區(qū)混跡很長(zhǎng)?一段時(shí)間才會(huì)慢慢升入高分區(qū),也就是 說用戶積分的分布總體說來是有區(qū)段的,我們進(jìn)?一步注意到高分 區(qū)用戶積分的細(xì)微變化其實(shí)對(duì)低分段用戶的排名影響不大。于 是,我們可以想到按積分區(qū)段進(jìn)行統(tǒng)計(jì)的方法,引入?一張分區(qū)積 分表score_range:

表結(jié)構(gòu):

score_range表結(jié)構(gòu)

數(shù)據(jù)示例:

score_range數(shù)據(jù)示例

表示[from_score, to_score)區(qū)間有count個(gè)用戶。若我們按每 1000分劃分?一個(gè)區(qū)間則有[0, 1000), [1000, 2000), …, [999 000, 1 000 000)這1000個(gè)區(qū)間,以后對(duì)用戶積分的更新要相應(yīng)地更新 score_range表的區(qū)間值。在分區(qū)積分表的輔助下查詢積分為s的 用戶的排名,可以首先確定其所屬區(qū)間,把高于s的積分區(qū)間的 count值累加,然后再查詢出該用戶在本區(qū)間內(nèi)的排名,二者相 加即可獲得用戶的排名。

乍一看,這個(gè)方法貌似通過區(qū)間聚合減少了查詢計(jì)算量,實(shí)則不然。大的問題在于:如何查詢用戶在本區(qū)間內(nèi)的排名呢?如果是在算法1中的SQL中加上積分條件:

select 1 + count(t2.uid) as rank from user_score t1, user_score t2 where t1.uid = @uid and t2.score > t1.score and t2.score < @to_score

在理想情況下,由于把t2.score的范圍限制在了1000以內(nèi),如果 對(duì)score字段建立索引,我們期望本條SQL語句將通過索引大大 減少掃描的user_score表的行數(shù)。不過真實(shí)情況并非如此, t2.score的范圍在1000以內(nèi)并不意味著該區(qū)間內(nèi)的用戶數(shù)也是 1000,因?yàn)檫@里有積分相同的情況存在!二八定律告訴我們, 前20%的低分區(qū)往往集中了80%的用戶,這就是說對(duì)于大量低分 區(qū)用戶進(jìn)行區(qū)間內(nèi)排名查詢的性能遠(yuǎn)不及對(duì)少數(shù)高分區(qū)用戶進(jìn)行 排名查詢,所以在?一般情況下這種分區(qū)方法不會(huì)帶來實(shí)質(zhì)性的性 能提升。

算法特點(diǎn)

優(yōu)點(diǎn):注意到了積分區(qū)間的存在,并通過預(yù)先聚合消除查詢的全 表掃描。

缺點(diǎn):積分非均勻分布的特點(diǎn)使得性能提升并不理想。

算法3:樹形分區(qū)設(shè)計(jì)

均勻分區(qū)查詢算法的失敗是由于積分分布的非均勻性,那么我們 自然就會(huì)想,能不能按二八定律,把score_range表設(shè)計(jì)為非均 勻區(qū)間呢?比如,把低分區(qū)劃密集?一點(diǎn),10分?一個(gè)區(qū)間,然后逐 漸變成100分,1000分,10 000分 …… 當(dāng)然,這不失為?一種方 法,不過這種分法有?一定的隨意性,不容易把握好,而且整個(gè)系 統(tǒng)的積分分布會(huì)隨著使用而逐漸發(fā)生變化,初的較好的分區(qū)方 法可能會(huì)變得不適應(yīng)未來的情況了。我們希望找到?一種分區(qū)方 法,既可以適應(yīng)積分非均勻性,又可以適應(yīng)系統(tǒng)積分分布的變 化,這就是樹形分區(qū)。 我們可以把[0, 1 000 000)作為?一級(jí)區(qū)間;再把?一級(jí)區(qū)間分為兩 個(gè)2級(jí)區(qū)間[0, 500 000), [500 000, 1 000 000),然后把二級(jí)區(qū)間 二分為4個(gè)3級(jí)區(qū)間[0, 250 000), [250 000, 500 000), [500 000, 750 000), [750 000, 1 000 000),依此類推,終我們會(huì)得到1 000 000個(gè)21級(jí)區(qū)間[0,1), [1,2) … [999 999, 1 000 000)。這實(shí)際 上是把區(qū)間組織成了?一種平衡二叉樹結(jié)構(gòu),根結(jié)點(diǎn)代表?一級(jí)區(qū) 間,每個(gè)非葉子結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn),左子結(jié)點(diǎn)代表低分區(qū)間,右 子結(jié)點(diǎn)代表高分區(qū)間。樹形分區(qū)結(jié)構(gòu)需要在更新時(shí)保持?一種不變 量(Invariant):非葉子結(jié)點(diǎn)的count值總是等于其左右子結(jié)點(diǎn)的 count值之和。

雖然,本算法的更新和查詢都涉及若干個(gè)操作,但如果我們?yōu)閰^(qū) 間的from_score和to_score建立索引,這些操作都是基于鍵的查 詢和更新,不會(huì)產(chǎn)生表掃描,因此效率更高。另外,本算法并不依賴于關(guān)系數(shù)據(jù)模型和SQL運(yùn)算,可以輕易地改造為NoSQL等 其他存儲(chǔ)方式,而基于鍵的操作也很容易引入緩存機(jī)制進(jìn)?一步優(yōu) 化性能。進(jìn)?一步,我們可以估算?一下樹形區(qū)間的數(shù)目大約為200 000 000,考慮每個(gè)結(jié)點(diǎn)的大小,整個(gè)結(jié)構(gòu)只占用幾十M空間。 所以,我們完全可以在內(nèi)存建立區(qū)間樹結(jié)構(gòu),并通過user_score 表在O(n)的時(shí)間內(nèi)初始化區(qū)間樹,然后排名的查詢和更新操作都 可以在內(nèi)存進(jìn)行。?一般來講,同樣的算法,從數(shù)據(jù)庫到內(nèi)存算法 的性能提升常??梢赃_(dá)到105以上;因此,本算法可以具有非常 高的性能。

算法特點(diǎn)

優(yōu)點(diǎn):結(jié)構(gòu)穩(wěn)定,不受積分分布影響;每次查詢或更新的復(fù)雜度 為積分大值的O(log n)級(jí)別,且與用戶規(guī)模無關(guān),可以應(yīng)對(duì)海 量規(guī)模;不依賴于SQL,容易改造為NoSQL或內(nèi)存數(shù)據(jù)結(jié)構(gòu)。

缺點(diǎn):算法相對(duì)更復(fù)雜。

算法4:積分排名數(shù)組

算法3雖然性能較高,達(dá)到了積分變化的O(log n)的復(fù)雜度,但 是實(shí)現(xiàn)上比較復(fù)雜。另外,O(log n)的復(fù)雜度只在n特別大的時(shí) 候才顯出它的優(yōu)勢(shì),而實(shí)際應(yīng)用中積分的變化情況往往不會(huì)太 大,這時(shí)和O(n)的算法相比往往沒有明顯的優(yōu)勢(shì),甚至可能更 慢。

考慮到這?一情況,仔細(xì)觀察?一下積分變化對(duì)排名的具體影響,可 以發(fā)現(xiàn)某用戶的積分從s變?yōu)閟+n,積分小于s或者大于等于s+n 的其他用戶排名實(shí)際上并不會(huì)受到影響,只有積分在[s, s+n)區(qū) 間內(nèi)的用戶排名會(huì)下降1位。我們可以用?一個(gè)大小為100 000 000 的數(shù)組表示積分和排名的對(duì)應(yīng)關(guān)系,其中rank[s]表示積分s所對(duì) 應(yīng)的排名。初始化時(shí),rank數(shù)組可以由user_score表在O(n)的復(fù) 雜度內(nèi)計(jì)算而來。用戶排名的查詢和更新基于這個(gè)數(shù)組來進(jìn)行。 查詢積分s所對(duì)應(yīng)的排名直接返回rank[s]即可,復(fù)雜度為O(1); 當(dāng)用戶積分從s變?yōu)閟+n,只需要把rank[s]到rank[s+n-1]這n個(gè)元 素的值增加1即可,復(fù)雜度為O(n)。

算法特點(diǎn)。

優(yōu)點(diǎn):積分排名數(shù)組比區(qū)間樹更簡(jiǎn)單,易于實(shí)現(xiàn);排名查詢復(fù)雜 度為O(1);排名更新復(fù)雜度O(n),在積分變化不大的情況下非常 高效。

缺點(diǎn):當(dāng)n比較大時(shí),需要更新大量元素,效率不如算法3。

總結(jié)

上面介紹了用戶積分排名的幾種算法,算法1簡(jiǎn)單,易于理解和 實(shí)現(xiàn),適用于小規(guī)模和低并發(fā)應(yīng)用;算法3引入了較復(fù)雜的樹形 分區(qū)結(jié)構(gòu),但是O(log n)的復(fù)雜度性能優(yōu)越,可以應(yīng)用于海量規(guī) 模和高并發(fā);算法4采用簡(jiǎn)單的排名數(shù)組,易于實(shí)現(xiàn),在積分變 化不大的情況下性能不亞于算法3。本問題是?一個(gè)開放性的問 題,相信?一定還有其他優(yōu)秀的算法和解決方案

本文僅限內(nèi)部技術(shù)人員查閱學(xué)習(xí)交流,不得作于其他商業(yè)用途.原創(chuàng)文章出自:南昌網(wǎng)站建設(shè)公司-百恒網(wǎng)絡(luò) http://m.gimmickmag.com 此文禁止轉(zhuǎn)載,謝謝合作!

400-680-9298,0791-88117053
掃一掃關(guān)注百恒網(wǎng)絡(luò)微信公眾號(hào)
掃一掃打開百恒網(wǎng)絡(luò)小程序

歡迎您的光顧,我們將竭誠(chéng)為您服務(wù)×

售前咨詢 售前咨詢
 
售前咨詢 售前咨詢
 
售前咨詢 售前咨詢
 
售前咨詢 售前咨詢
 
售前咨詢 售前咨詢
 
售后服務(wù) 售后服務(wù)
 
售后服務(wù) 售后服務(wù)
 
備案專線 備案專線
 
×