以前在音樂做過一些實時投票,積分排名;單曲、專輯等排行榜;遊戲中也有類似的戰鬥力排行;SNS的遊戲又有好友排行等,對於此類的排行算法在此做個總結。
需求背景:
查看前top N的排名用戶
查看自己的排名
用戶積分變更後,排名及時更新
方案一:
利用MySQL來實現,存放一張用戶積分表user_score,結構如下:
取前top N,自己的排名都可以通過簡單的sql語句搞定。
算法簡單,利用sql的功能,不需要其他復雜邏輯,對於數據量比較少、性能要求不高,可以使用。但是對於海量數據,性能是無法接受的。
方案二:積分排名數組實現
如有1百萬用戶進行排名,就用一個大小為1,000,000的數組表示積分和排名的對應關系,其中rank[s]表示積分s所對應的排名。初始化時,rank數組可以由user_score表在O(n)的復雜度內計算而來。用戶排名的查詢和更新基於這個數組來進行。查詢積分s所對應的排名直接返回rank[s]即可,復雜度為O(1);當用戶積分從s變為s+n,隻需要把rank[s]到rank[s+n-1]這n個元素的值增加1即可,復雜度為O(n)。
方案三:用GCC的pb_ds庫中有assoc_container來進行實現。
參考如下:tree_order_statistics.cc
存取效率都可以達到O(log(n)),不足就是程序重啟後數據會丟失。
方案四:自己實現排序樹
大致實現思路如下:
我們可以把[0, 1,000,000)作為一級區間;再把一級區間分為兩個2級區間[0, 500,000), [500,000, 1,000,000),然後把二級區間二分為4個3級區間[0, 250,000), [250,000, 500,000), [500,000, 750,000), [750,000, 1,000,000),依此類推,最終我們會得到1,000,000個21級區間[0,1), [1,2) … [999,999, 1,000,000)。這實際上是把區間組織成瞭一種平衡二叉樹結構,根結點代表一級區間,每個非葉子結點有兩個子結點,左子結點代表低分區間,右子結點代表高分區間。樹形分區結構需要在更新時保持一種不變量,非葉子結點的count值總是等於其左右子結點的count值之和。
以後,每次用戶積分有變化所需要更新的區間數量和積分變化量有關系,積分變化越小更新的區間層次越低。總體上,每次所需要更新的區間數量是用戶積分變量的log(n)級別的,也就是說如果用戶積分一次變化在百萬級,更新區間的數量在二十這個級別。在這種樹形分區積分表的輔助下查詢積分為s的用戶排名,實際上是一個在區間樹上由上至下、由粗到細一步步明確s所在位置的過程。比如,對於積分499,000,我們用一個初值為0的排名變量來做累加;首先,它屬於1級區間的左子樹[0, 500,000),那麼該用戶排名應該在右子樹[500,000, 1,000,000)的用戶數count之後,我們把該count值累加到該用戶排名變量,進入下一級區間;其次,它屬於3級區間的[250,000, 500,000),這是2級區間的右子樹,所以不用累加count到排名變量,直接進入下一級區間;再次,它屬於4級區間的…;直到最後我們把用戶積分精確定位在21級區間[499,000, 499,001),整個累加過程完成,得出排名!
雖然,本算法的更新和查詢都涉及到若幹個操作,但如果我們為區間的from_score和to_score建立索引,這些操作都是基於鍵的查詢和更新,不會產生表掃描,因此效率更高。另外,本算法並不依賴於關系數據模型和SQL運算,可以輕易地改造為NoSQL等其他存儲方式,而基於鍵的操作也很容易引入緩存機制進一步優化性能。進一步,我們可以估算一下樹形區間的數目大約為2,000,000,考慮每個結點的大小,整個結構隻占用幾十M空間。所以,我們完全可以在內存建立區間樹結構,並通過user_score表在O(n)的時間內初始化區間樹,然後排名的查詢和更新操作都可以在內存進行。一般來講,同樣的算法,從數據庫到內存算法的性能提升常常可以達到10^5以上;因此,本算法可以達到非常高的性能。
算法特點
- 優點:結構穩定,不受積分分佈影響;每次查詢或更新的復雜度為積分最大值的O(log(n))級別,且與用戶規模無關,可以應對海量規模;不依賴於SQL,容易改造為NoSQL或內存數據結構。
- 缺點:算法相對更復雜。
方案五:skiplist的實現
實現方案四的時候,發現代碼比較復雜,調試起來特別不方便。遊戲這邊有個同事也實現瞭個,代碼地址:http://km.oa.com/articles/show/158740
於是就想到的跳表,發現用這個實現起來比較簡單;用hashmap來存儲具體的對象;用skiplist用來排序。也可以簡單的用一個map和set來實現。Map內面存具體對象,set用來排序。
關於skip list這裡簡單介紹下:skip list是鏈表的一種特殊形式,對鏈表的一種優化;保證INSERT和REMOVE操作是O(logn),而通用鏈表的復雜度為O(n);
- 優點:實現較簡單,效率基本上O(log(N))
- 缺點:當達到億級別時的數據時,性能會急劇下降
方案六:基於redis的 sort set的實現
後來看redis發現redis的zset天生是用來做排行榜的、好友列表, 去重, 歷史記錄等業務需求。接口使用非常簡單。接口非常豐富,基本上需要的實現都能滿足,說明如下:
ZAdd/ZRem是O(log(N)),ZRangeByScore/ZRemRangeByScore是O(log(N)+M),N是Set大小,M是結果/操作元素的個數。
ZSET的實現用到瞭兩個數據結構:hash table 和 skip list(跳躍表),其中hash table是具體使用redis中的dict來實現的,主要是為瞭保證查詢效率為O(1) ,而skip list(跳躍表)主要是保證元素有序並能夠保證INSERT和REMOVE操作是O(logn)的復雜度。
音樂現在的通用投票排名系統就是基於redis來實現的,運行還不錯。
- 優點:基於redis開發,速度快;使用redis相關特性
- 缺點:當達到億級別時的數據時,性能會急劇下降
來實現排行榜的方法很多,可以根據自己的具體需求,參考選用。
from:gad