在C#中使用二叉樹實時計算海量用戶積分排名的實現(xiàn)詳解
從何說起
前些天和朋友討論一個問題，他們的應用有幾十萬會員然后對應有積分，現(xiàn)在想做積分排名的需求，問有沒有什么好方案。這個問題也算常見，很多地方都能看到，常規(guī)做法一般是數(shù)據(jù)定時跑批把計算結果到中間表然后直接查表就行，或者只顯示個TOP N的排行榜，名次高的計算真實名次，名次比較低的直接顯示在xxx名開外這種。但是出于探索問題的角度，我還是想找一下有沒有實時計算的辦法，并且效率能夠接受。
在博客園搜到一篇不錯的文章，基本羅列了常用的方案，每種算法詳細介紹了具體思路，其中基于二叉樹的算法是個非常不錯的方案，文章中只給了思路沒有給出代碼，于是我決定自己用C#實現(xiàn)出來。
這里只討論具體算法實現(xiàn)，不考慮業(yè)務需求是否合理。
思路解析
關于算法核心思想前面的文章中寫的很詳細，我不再重復描述，這里只用一個具體示例演示這個過程。
假設積分范圍是0-5，我們對它不斷進行中位分區(qū)直到不能分為止，形成如下一棵二叉樹：
其中每個樹節(jié)點包含2個信息：節(jié)點范圍range[min，max) 和命中數(shù)量計數(shù)器count ，可以看到葉子節(jié)點的range一定是相鄰的2個數(shù)。
假如現(xiàn)在有一個積分3要插入到樹中，該如何操作呢？當前節(jié)點從根節(jié)點開始，分別判斷是否包含于左右子節(jié)點，如果包含的話當前節(jié)點改為這個子節(jié)點，同時計數(shù)器加1，然后再次進行相同判斷，直到遍歷到葉子節(jié)點為止，遍歷順序如下：
再依次插入1和4，二叉樹的演變情況為：
數(shù)據(jù)放進去后怎么判斷它是排名多少呢？還是從根節(jié)點開始，判斷它是否包含于左子節(jié)點，如果包含的話說明它比右子節(jié)點中count個數(shù)?。ㄔ赾ount名之外），然后再往下一級做同樣的判斷；如果包含于右子節(jié)點那就繼續(xù)往下判斷，直到碰到葉子節(jié)點為止。依次累加count最后加上葉子節(jié)點占的一位就得到了它在這棵樹里的排名，以1為例演示判斷步驟（排名為2+1=3）：
好了，一切就緒，只欠代碼。
擼碼實現(xiàn)
樹結構由節(jié)點構成，那首先設計一個節(jié)點類：
/// <summary>
/// 樹節(jié)點對象
/// </summary>
public class TreeNode
{
/// <summary>
/// 節(jié)點的最小值
/// </summary>
public int ValueFrom { get; set; }
/// <summary>
/// 節(jié)點的最大值
/// </summary>
public int ValueTo { get; set; }
/// <summary>
/// 在節(jié)點范圍內(nèi)的數(shù)量
/// </summary>
public int Count { get; set; }
/// <summary>
/// 節(jié)點高度（樹的層級）
/// </summary>
public int Height { get; set; }
/// <summary>
/// 父節(jié)點
/// </summary>
public TreeNode Parent { get; set; }
/// <summary>
/// 左子節(jié)點
/// </summary>
public TreeNode LeftChildNode { get; set; }
/// <summary>
/// 右子節(jié)點
/// </summary>
public TreeNode RightChildNode { get; set; }
}
樹節(jié)點的屬性主要包含范圍值ValueFrom、ValueTo、計數(shù)器Count、左子節(jié)點LeftChildNode和右子節(jié)點RightChildNode，由此組成一個有層次的樹結構。
然后就是定義我們的樹對象了，它的核心字段就是代表源頭的根節(jié)點：
public class RankBinaryTree
{
/// <summary>
/// 根節(jié)點
/// </summary>
private TreeNode _root;
}
根據(jù)前面的算法思想，創(chuàng)建樹的時候要用積分范圍初始化所有節(jié)點，這里約定了最小積分為0，通過構造函數(shù)傳入最大值并創(chuàng)建樹結構：
/// <summary>
/// 構造函數(shù)初始化根節(jié)點
/// </summary>
/// <param name="max"></param>
public RankBinaryTree(int max)
{
_root = new TreeNode() { ValueFrom = 0, ValueTo = max+1, Height = 1 };
_root.LeftChildNode = CreateChildNode(_root, 0, max / 2);
_root.RightChildNode = CreateChildNode(_root, max / 2, max);
}
/// <summary>
/// 遍歷創(chuàng)建子節(jié)點
/// </summary>
/// <param name="current"></param>
/// <param name="min"></param>
/// <param name="max"></param>
/// <returns></returns>
private TreeNode CreateChildNode(TreeNode current, int min, int max)
{
if (min == max) return null;
var node = new TreeNode() { ValueFrom = min, ValueTo = max, Height = current.Height + 1 };
node.Parent = current;
int center = (min + max) / 2;
if (min < max - 1)
{
node.LeftChildNode = CreateChildNode(node, min, center);
node.RightChildNode = CreateChildNode(node, center, max);
}
return node;
}
有了樹以后下一步就是往里面插入數(shù)據(jù)，根據(jù)前面介紹的邏輯：
/// <summary>
/// 往樹中插入一個值
/// </summary>
/// <param name="value"></param>
public void Insert(int value)
{
InnerInsert(_root, value);
_data.Add(value);
}
/// <summary>
/// 子節(jié)點判斷范圍遍歷插入
/// </summary>
/// <param name="node"></param>
/// <param name="value"></param>
private void InnerInsert(TreeNode node, int value)
{
if (node == null) return;
//判斷是否在這個節(jié)點范圍內(nèi)
if (value >= node.ValueFrom && value < node.ValueTo)
{
//更新節(jié)點總數(shù)信息
node.Count++;
//更新左子節(jié)點
InnerInsert(node.LeftChildNode, value);
//更新右子節(jié)點
InnerInsert(node.RightChildNode, value);
}
}
下一步提供方法獲取指定值在樹中的排名：
/// <summary>
/// 從樹中獲取總排名
/// </summary>
/// <param name="value"></param>
/// <returns></returns>
public int GetRank(int value)
{
if (value < 0) return 0;
return InnerGet(_root, value);
}
/// <summary>
/// 遍歷子節(jié)點獲取累計排名
/// </summary>
/// <param name="node"></param>
/// <param name="value"></param>
/// <returns></returns>
private int InnerGet(TreeNode node, int value)
{
if (node.LeftChildNode == null || node.RightChildNode == null) return 1;
if (value >= node.LeftChildNode.ValueFrom && value < node.LeftChildNode.ValueTo)
{
//當這個值存在于左子節(jié)點中時，要累加右子節(jié)點的總數(shù)（表示這個數(shù)在多少名之后）
return node.RightChildNode.Count + InnerGet(node.LeftChildNode, value);
}
else
{
//如果在右子節(jié)點中就繼續(xù)遍歷
return InnerGet(node.RightChildNode, value);
}
}
到這里，核心功能已經(jīng)實現(xiàn)了?？紤]到有積分更新的情況，我們可以加上節(jié)點更新和刪除的方法。刪除很容易，和插入逆向操作就行，更新就更容易了，把舊節(jié)點刪除再計算出新值插入即可，完整代碼已經(jīng)上傳到Github。
這棵樹究竟效率如何，下面我們跑個分看看。
測試走起來
在測試程序中，我模擬了積分范圍0-1000000的場景，這個范圍幾乎覆蓋了真實業(yè)務中90%的積分值，100萬積分以上的會員系統(tǒng)應該比較少見了。
而會員的積分值分布也是不均勻的，一般來說擁有小額積分的用戶比例最大，積分值越高所占用戶比例越小。
在程序中我假設有100萬個會員，其中50W用戶積分都在100以內(nèi)，30W用戶積分在100-10000，15W用戶積分在10000-50000，5W用戶積分在50000以上。
下面是各個操作的耗時時間：
可以看到，這個效率不是一般的快啊，其中獲取排名的查詢時間幾乎可以忽略不計。
這時候有人問了，這么多數(shù)據(jù)會不會非常吃內(nèi)存，下面用任務管理器分別查看不使用樹和使用樹的內(nèi)存情況：
運行環(huán)境是.NetCore3.0 Console，測試主機配置情況：
100萬數(shù)據(jù)只有130M內(nèi)存占用，對現(xiàn)代計算機來說簡直是灑灑水~
業(yè)務環(huán)境中使用務必注意線程安全問題?。?！
寫在最后
以上的二叉樹算法處理排名問題確實比較巧妙，實現(xiàn)起來也不算特別復雜，如果上述代碼有缺陷或有其他更好的方案，歡迎探討，也算拋磚引玉了~
完整代碼及測試用例請戳這里https://github.com/hey-hoho/NetCoreDemo/tree/master/ConsoleApp/ScoreRank
以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關文章
這篇文章主要介紹了c# 模擬線性回歸的示例，幫助大家利用c#進行機器學習，感興趣的朋友可以了解下2020-10-10
c#動態(tài)類型,及動態(tài)對象的創(chuàng)建,合并2個對象,map實例
下面小編就為大家?guī)硪黄猚#動態(tài)類型,及動態(tài)對象的創(chuàng)建,合并2個對象,map實例。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-02-02
在winform中實現(xiàn)雙向數(shù)據(jù)綁定的方法
雙向數(shù)據(jù)綁定是一種允許我們創(chuàng)建持久連接的技術,使模型數(shù)據(jù)和用戶界面(UI)之間的交互能夠自動同步,今天我想通過winform中DataGridView控件為例,介紹在winform中如何實現(xiàn)雙向數(shù)據(jù)綁定,需要的朋友可以參考下2024-03-03
關于C# 4.0新特性“缺省參數(shù)”的實現(xiàn)詳解
這篇文章主要給大家介紹了關于C# 4.0新特性“缺省參數(shù)”的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家學習或者使用C# 4.0具有一定的參考學習價值，需要的朋友們下面來一起學習學習吧2020-06-06
這篇文章主要為大家詳細介紹了Unity3D實現(xiàn)扭動擠壓瀏覽效果，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-02-02
這篇文章主要介紹了c#中利用Tu Share獲取股票交易信息,本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-06-06
這篇文章主要介紹了C#運行CGI程序的方法,實例講述了具體的配置步驟與實現(xiàn)代碼,具有一定的參考借鑒價值,需要的朋友可以參考下2014-12-12
C#中IsNullOrEmpty和IsNullOrWhiteSpace的使用方法及區(qū)別解析
今天我們將探討C#中兩個常用的字符串處理方法：IsNullOrEmpty和IsNullOrWhiteSpace，本文中，我們將詳細解釋這兩個方法的功能和使用場景，并幫助您更好地理解它們之間的區(qū)別，本文結合實例代碼給大家介紹的非常詳細，需要的朋友參考下吧2023-07-07
當下, 由于存儲結構需要, 用多維數(shù)組, 順便學習了一下, 將學習經(jīng)過備忘如下2012-09-09
洗牌算法的要求是這樣的:將N個數(shù)亂序后輸出.由于和撲克牌的洗牌過程比較相似所以我也就稱為洗牌算法了.很多地方都不自覺的需要這個算法的支持.也可以將這個算法擴展為從N個數(shù)中取出M個不重復的數(shù)(0<M<=N).今天我們看下如何用C#來實現(xiàn)2015-03-03