本篇內(nèi)容主要講解“如何在C#中使用二叉樹實時計算海量用戶積分排名”,感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷,實用性強。下面就讓小編來帶大家學習“如何在C#中使用二叉樹實時計算海量用戶積分排名”吧!
網(wǎng)站建設哪家好,找成都創(chuàng)新互聯(lián)!專注于網(wǎng)頁設計、網(wǎng)站建設、微信開發(fā)、小程序開發(fā)、集團企業(yè)網(wǎng)站建設等服務項目。為回饋新老客戶創(chuàng)新互聯(lián)還提供了長島免費建站歡迎大家使用!
思路解析
關于算法核心思想前面的文章中寫的很詳細,我不再重復描述,這里只用一個具體示例演示這個過程。假設積分范圍是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é)構(gòu)由節(jié)點構(gòu)成,那首先設計一個節(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é)構(gòu)。然后就是定義我們的樹對象了,它的核心字段就是代表源頭的根節(jié)點: public class RankBinaryTree { /// <summary> /// 根節(jié)點 /// </summary> private TreeNode _root; } 根據(jù)前面的算法思想,創(chuàng)建樹的時候要用積分范圍初始化所有節(jié)點,這里約定了最小積分為0,通過構(gòu)造函數(shù)傳入最大值并創(chuàng)建樹結(jié)構(gòu): /// <summary> /// 構(gòu)造函數(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)境中使用務必注意線程安全問題?。。?/p>
到此,相信大家對“如何在C#中使用二叉樹實時計算海量用戶積分排名”有了更深的了解,不妨來實際操作一番吧!這里是創(chuàng)新互聯(lián)網(wǎng)站,更多相關內(nèi)容可以進入相關頻道進行查詢,關注我們,繼續(xù)學習!
網(wǎng)站題目:如何在C#中使用二叉樹實時計算海量用戶積分排名
分享鏈接:http://bm7419.com/article36/goidpg.html
成都網(wǎng)站建設公司_創(chuàng)新互聯(lián),為您提供虛擬主機、自適應網(wǎng)站、企業(yè)網(wǎng)站制作、云服務器、網(wǎng)站導航、搜索引擎優(yōu)化
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請盡快告知,我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時需注明來源: 創(chuàng)新互聯(lián)