本篇內(nèi)容主要講解“如何在C#中使用二叉樹(shù)實(shí)時(shí)計(jì)算海量用戶(hù)積分排名”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“如何在C#中使用二叉樹(shù)實(shí)時(shí)計(jì)算海量用戶(hù)積分排名”吧!
成都創(chuàng)新互聯(lián)公司專(zhuān)注為客戶(hù)提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于網(wǎng)站建設(shè)、
網(wǎng)站設(shè)計(jì)、湘潭網(wǎng)絡(luò)推廣、成都微信小程序、湘潭網(wǎng)絡(luò)營(yíng)銷(xiāo)、湘潭企業(yè)策劃、湘潭品牌公關(guān)、搜索引擎seo、人物專(zhuān)訪(fǎng)、企業(yè)宣傳片、企業(yè)代運(yùn)營(yíng)等，從售前售中售后，我們都將竭誠(chéng)為您服務(wù)，您的肯定，是我們大的嘉獎(jiǎng)；
成都創(chuàng)新互聯(lián)公司為所有大學(xué)生創(chuàng)業(yè)者提供
湘潭建站搭建服務(wù)，24小時(shí)服務(wù)熱線(xiàn)：18980820575，官方網(wǎng)址：www.cdcxhl.com
思路解析
關(guān)于算法核心思想前面的文章中寫(xiě)的很詳細(xì)，我不再重復(fù)描述，這里只用一個(gè)具體示例演示這個(gè)過(guò)程。假設(shè)積分范圍是0-5，我們對(duì)它不斷進(jìn)行中位分區(qū)直到不能分為止，形成如下一棵二叉樹(shù)：
其中每個(gè)樹(shù)節(jié)點(diǎn)包含2個(gè)信息：節(jié)點(diǎn)范圍range[min，max) 和命中數(shù)量計(jì)數(shù)器count ，可以看到葉子節(jié)點(diǎn)的range一定是相鄰的2個(gè)數(shù)。
假如現(xiàn)在有一個(gè)積分3要插入到樹(shù)中，該如何操作呢？當(dāng)前節(jié)點(diǎn)從根節(jié)點(diǎn)開(kāi)始，分別判斷是否包含于左右子節(jié)點(diǎn)，如果包含的話(huà)當(dāng)前節(jié)點(diǎn)改為這個(gè)子節(jié)點(diǎn)，同時(shí)計(jì)數(shù)器加1，然后再次進(jìn)行相同判斷，直到遍歷到葉子節(jié)點(diǎn)為止，遍歷順序如下：
再依次插入1和4，二叉樹(shù)的演變情況為：
數(shù)據(jù)放進(jìn)去后怎么判斷它是排名多少呢？還是從根節(jié)點(diǎn)開(kāi)始，判斷它是否包含于左子節(jié)點(diǎn)，如果包含的話(huà)說(shuō)明它比右子節(jié)點(diǎn)中count個(gè)數(shù)小（在count名之外），然后再往下一級(jí)做同樣的判斷；如果包含于右子節(jié)點(diǎn)那就繼續(xù)往下判斷，直到碰到葉子節(jié)點(diǎn)為止。依次累加count最后加上葉子節(jié)點(diǎn)占的一位就得到了它在這棵樹(shù)里的排名，以1為例演示判斷步驟（排名為2+1=3）：
好了，一切就緒，只欠代碼。
擼碼實(shí)現(xiàn)
樹(shù)結(jié)構(gòu)由節(jié)點(diǎn)構(gòu)成，那首先設(shè)計(jì)一個(gè)節(jié)點(diǎn)類(lèi)：
/// /// 樹(shù)節(jié)點(diǎn)對(duì)象 /// public class TreeNode { /// /// 節(jié)點(diǎn)的最小值 /// public int ValueFrom { get; set; } /// /// 節(jié)點(diǎn)的較大值 /// public int ValueTo { get; set; } /// /// 在節(jié)點(diǎn)范圍內(nèi)的數(shù)量 /// public int Count { get; set; } /// /// 節(jié)點(diǎn)高度（樹(shù)的層級(jí)） /// public int Height { get; set; } /// /// 父節(jié)點(diǎn) /// public TreeNode Parent { get; set; } /// /// 左子節(jié)點(diǎn) /// public TreeNode LeftChildNode { get; set; } /// /// 右子節(jié)點(diǎn) /// public TreeNode RightChildNode { get; set; } }
樹(shù)節(jié)點(diǎn)的屬性主要包含范圍值ValueFrom、ValueTo、計(jì)數(shù)器Count、左子節(jié)點(diǎn)LeftChildNode和右子節(jié)點(diǎn)RightChildNode，由此組成一個(gè)有層次的樹(shù)結(jié)構(gòu)。然后就是定義我們的樹(shù)對(duì)象了，它的核心字段就是代表源頭的根節(jié)點(diǎn)：
public class RankBinaryTree { /// /// 根節(jié)點(diǎn) /// private TreeNode _root; }
根據(jù)前面的算法思想，創(chuàng)建樹(shù)的時(shí)候要用積分范圍初始化所有節(jié)點(diǎn)，這里約定了最小積分為0，通過(guò)構(gòu)造函數(shù)傳入較大值并創(chuàng)建樹(shù)結(jié)構(gòu)：
/// /// 構(gòu)造函數(shù)初始化根節(jié)點(diǎn) /// /// 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); } /// /// 遍歷創(chuàng)建子節(jié)點(diǎn) /// /// /// /// /// 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ù)以后下一步就是往里面插入數(shù)據(jù)，根據(jù)前面介紹的邏輯：
/// /// 往樹(shù)中插入一個(gè)值 /// /// public void Insert(int value) { InnerInsert(_root, value); _data.Add(value); } /// /// 子節(jié)點(diǎn)判斷范圍遍歷插入 /// /// /// private void InnerInsert(TreeNode node, int value) { if (node == null) return; //判斷是否在這個(gè)節(jié)點(diǎn)范圍內(nèi) if (value >= node.ValueFrom && value < node.ValueTo) { //更新節(jié)點(diǎn)總數(shù)信息 node.Count++; //更新左子節(jié)點(diǎn) InnerInsert(node.LeftChildNode, value); //更新右子節(jié)點(diǎn) InnerInsert(node.RightChildNode, value); } }
下一步提供方法獲取指定值在樹(shù)中的排名：
/// /// 從樹(shù)中獲取總排名 /// /// /// public int GetRank(int value) { if (value < 0) return 0; return InnerGet(_root, value); } /// /// 遍歷子節(jié)點(diǎn)獲取累計(jì)排名 /// /// /// /// 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) { //當(dāng)這個(gè)值存在于左子節(jié)點(diǎn)中時(shí)，要累加右子節(jié)點(diǎn)的總數(shù)（表示這個(gè)數(shù)在多少名之后） return node.RightChildNode.Count + InnerGet(node.LeftChildNode, value); } else { //如果在右子節(jié)點(diǎn)中就繼續(xù)遍歷 return InnerGet(node.RightChildNode, value); } }
到這里，核心功能已經(jīng)實(shí)現(xiàn)了?？紤]到有積分更新的情況，我們可以加上節(jié)點(diǎn)更新和刪除的方法。刪除很容易，和插入逆向操作就行，更新就更容易了，把舊節(jié)點(diǎn)刪除再計(jì)算出新值插入即可，完整代碼已經(jīng)上傳到Github。這棵樹(shù)究竟效率如何，下面我們跑個(gè)分看看。
測(cè)試走起來(lái)
在測(cè)試程序中，我模擬了積分范圍0-1000000的場(chǎng)景，這個(gè)范圍幾乎覆蓋了真實(shí)業(yè)務(wù)中90%的積分值，100萬(wàn)積分以上的會(huì)員系統(tǒng)應(yīng)該比較少見(jiàn)了。
而會(huì)員的積分值分布也是不均勻的，一般來(lái)說(shuō)擁有小額積分的用戶(hù)比例較大，積分值越高所占用戶(hù)比例越小。在程序中我假設(shè)有100萬(wàn)個(gè)會(huì)員，其中50W用戶(hù)積分都在100以?xún)?nèi)，30W用戶(hù)積分在100-10000，15W用戶(hù)積分在10000-50000，5W用戶(hù)積分在50000以上。
下面是各個(gè)操作的耗時(shí)時(shí)間：
可以看到，這個(gè)效率不是一般的快啊，其中獲取排名的查詢(xún)時(shí)間幾乎可以忽略不計(jì)。這時(shí)候有人問(wèn)了，這么多數(shù)據(jù)會(huì)不會(huì)非常吃?xún)?nèi)存，下面用任務(wù)管理器分別查看不使用樹(shù)和使用樹(shù)的內(nèi)存情況：
運(yùn)行環(huán)境是.NetCore3.0 Console，測(cè)試主機(jī)配置情況：
100萬(wàn)數(shù)據(jù)只有130M內(nèi)存占用，對(duì)現(xiàn)代計(jì)算機(jī)來(lái)說(shuō)簡(jiǎn)直是灑灑水~
業(yè)務(wù)環(huán)境中使用務(wù)必注意線(xiàn)程安全問(wèn)題?。?！
到此，相信大家對(duì)“如何在C#中使用二叉樹(shù)實(shí)時(shí)計(jì)算海量用戶(hù)積分排名”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是創(chuàng)新互聯(lián)建站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢(xún)，關(guān)注我們，繼續(xù)學(xué)習(xí)！
新聞名稱(chēng)：如何在C#中使用二叉樹(shù)實(shí)時(shí)計(jì)算海量用戶(hù)積分排名-創(chuàng)新互聯(lián)
鏈接地址：
http://weahome.cn/article/dejpgi.html
重慶分公司
重慶分公司
