如何在C#中使用二叉樹(shù)實(shí)時(shí)計(jì)算海量用戶積分排名

本篇內(nèi)容主要講解“如何在C#中使用二叉樹(shù)實(shí)時(shí)計(jì)算海量用戶積分排名”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“如何在C#中使用二叉樹(shù)實(shí)時(shí)計(jì)算海量用戶積分排名”吧!

思路解析

關(guān)于算法核心思想前面的文章中寫的很詳細(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)，如果包含的話當(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)，如果包含的話說(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)類：

/// <summary>  /// 樹(shù)節(jié)點(diǎn)對(duì)象  /// </summary>  public class TreeNode  {    /// <summary>    /// 節(jié)點(diǎn)的最小值    /// </summary>    public int ValueFrom { get; set; }    /// <summary>    /// 節(jié)點(diǎn)的最大值    /// </summary>    public int ValueTo { get; set; }    /// <summary>    /// 在節(jié)點(diǎn)范圍內(nèi)的數(shù)量    /// </summary>    public int Count { get; set; }    /// <summary>    /// 節(jié)點(diǎn)高度（樹(shù)的層級(jí)）    /// </summary>    public int Height { get; set; }    /// <summary>    /// 父節(jié)點(diǎn)    /// </summary>    public TreeNode Parent { get; set; }    /// <summary>    /// 左子節(jié)點(diǎn)    /// </summary>    public TreeNode LeftChildNode { get; set; }    /// <summary>    /// 右子節(jié)點(diǎn)    /// </summary>    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  {    /// <summary>    /// 根節(jié)點(diǎn)    /// </summary>    private TreeNode _root;  }
根據(jù)前面的算法思想，創(chuàng)建樹(shù)的時(shí)候要用積分范圍初始化所有節(jié)點(diǎn)，這里約定了最小積分為0，通過(guò)構(gòu)造函數(shù)傳入最大值并創(chuàng)建樹(shù)結(jié)構(gòu)：
/// <summary>    /// 構(gòu)造函數(shù)初始化根節(jié)點(diǎn)    /// </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é)點(diǎn)    /// </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ù)以后下一步就是往里面插入數(shù)據(jù)，根據(jù)前面介紹的邏輯：
/// <summary>    /// 往樹(shù)中插入一個(gè)值    /// </summary>    /// <param name="value"></param>    public void Insert(int value)    {      InnerInsert(_root, value);      _data.Add(value);    }    /// <summary>    /// 子節(jié)點(diǎn)判斷范圍遍歷插入    /// </summary>    /// <param name="node"></param>    /// <param name="value"></param>    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ù)中的排名：
/// <summary>    /// 從樹(shù)中獲取總排名    /// </summary>    /// <param name="value"></param>    /// <returns></returns>    public int GetRank(int value)    {      if (value < 0) return 0;      return InnerGet(_root, value);    }    /// <summary>    /// 遍歷子節(jié)點(diǎn)獲取累計(jì)排名    /// </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)      {        //當(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ō)擁有小額積分的用戶比例最大，積分值越高所占用戶比例越小。在程序中我假設(shè)有100萬(wàn)個(gè)會(huì)員，其中50W用戶積分都在100以內(nèi)，30W用戶積分在100-10000，15W用戶積分在10000-50000，5W用戶積分在50000以上。

下面是各個(gè)操作的耗時(shí)時(shí)間：

可以看到，這個(gè)效率不是一般的快啊，其中獲取排名的查詢時(shí)間幾乎可以忽略不計(jì)。這時(shí)候有人問(wèn)了，這么多數(shù)據(jù)會(huì)不會(huì)非常吃內(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ù)必注意線程安全問(wèn)題?。?！

到此，相信大家對(duì)“如何在C#中使用二叉樹(shù)實(shí)時(shí)計(jì)算海量用戶積分排名”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！