如何在C#中使用二叉树实时计算海量用户积分排名
本篇内容主要讲解“如何在C#中使用二叉树实时计算海量用户积分排名”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“如何在C#中使用二叉树实时计算海量用户积分排名”吧!
网站建设哪家好,找成都创新互联!专注于网页设计、网站建设、微信开发、小程序开发、集团企业网站建设等服务项目。为回馈新老客户创新互联还提供了长岛免费建站欢迎大家使用!
思路解析
关于算法核心思想前面的文章中写的很详细,我不再重复描述,这里只用一个具体示例演示这个过程。假设积分范围是0-5,我们对它不断进行中位分区直到不能分为止,形成如下一棵二叉树:
其中每个树节点包含2个信息:节点范围range[min,max)
和命中数量计数器count
,可以看到叶子节点的range一定是相邻的2个数。
假如现在有一个积分3要插入到树中,该如何操作呢?当前节点从根节点开始,分别判断是否包含于左右子节点,如果包含的话当前节点改为这个子节点,同时计数器加1,然后再次进行相同判断,直到遍历到叶子节点为止,遍历顺序如下:
再依次插入1和4,二叉树的演变情况为:
数据放进去后怎么判断它是排名多少呢?还是从根节点开始,判断它是否包含于左子节点,如果包含的话说明它比右子节点中count个数小(在count名之外),然后再往下一级做同样的判断;如果包含于右子节点那就继续往下判断,直到碰到叶子节点为止。依次累加count最后加上叶子节点占的一位就得到了它在这棵树里的排名,以1为例演示判断步骤(排名为2+1=3):
好了,一切就绪,只欠代码。
撸码实现
树结构由节点构成,那首先设计一个节点类:
////// 树节点对象 /// public class TreeNode { ////// 节点的最小值 /// public int ValueFrom { get; set; } ////// 节点的最大值 /// public int ValueTo { get; set; } ////// 在节点范围内的数量 /// public int Count { get; set; } ////// 节点高度(树的层级) /// public int Height { get; set; } ////// 父节点 /// public TreeNode Parent { get; set; } ////// 左子节点 /// public TreeNode LeftChildNode { get; set; } ////// 右子节点 /// public TreeNode RightChildNode { get; set; } } 树节点的属性主要包含范围值ValueFrom、ValueTo、计数器Count、左子节点LeftChildNode和右子节点RightChildNode,由此组成一个有层次的树结构。然后就是定义我们的树对象了,它的核心字段就是代表源头的根节点: public class RankBinaryTree { ////// 根节点 /// private TreeNode _root; } 根据前面的算法思想,创建树的时候要用积分范围初始化所有节点,这里约定了最小积分为0,通过构造函数传入最大值并创建树结构: ////// 构造函数初始化根节点 /// /// 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); } ////// 遍历创建子节点 /// /// /// /// ///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; } 有了树以后下一步就是往里面插入数据,根据前面介绍的逻辑: /// /// 往树中插入一个值 /// /// public void Insert(int value) { InnerInsert(_root, value); _data.Add(value); } ////// 子节点判断范围遍历插入 /// /// /// private void InnerInsert(TreeNode node, int value) { if (node == null) return; //判断是否在这个节点范围内 if (value >= node.ValueFrom && value < node.ValueTo) { //更新节点总数信息 node.Count++; //更新左子节点 InnerInsert(node.LeftChildNode, value); //更新右子节点 InnerInsert(node.RightChildNode, value); } } 下一步提供方法获取指定值在树中的排名: ////// 从树中获取总排名 /// /// ///public int GetRank(int value) { if (value < 0) return 0; return InnerGet(_root, value); } /// /// 遍历子节点获取累计排名 /// /// /// ///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) { //当这个值存在于左子节点中时,要累加右子节点的总数(表示这个数在多少名之后) return node.RightChildNode.Count + InnerGet(node.LeftChildNode, value); } else { //如果在右子节点中就继续遍历 return InnerGet(node.RightChildNode, value); } }
到这里,核心功能已经实现了。考虑到有积分更新的情况,我们可以加上节点更新和删除的方法。删除很容易,和插入逆向操作就行,更新就更容易了,把旧节点删除再计算出新值插入即可,完整代码已经上传到Github。这棵树究竟效率如何,下面我们跑个分看看。
测试走起来
在测试程序中,我模拟了积分范围0-1000000的场景,这个范围几乎覆盖了真实业务中90%的积分值,100万积分以上的会员系统应该比较少见了。
而会员的积分值分布也是不均匀的,一般来说拥有小额积分的用户比例最大,积分值越高所占用户比例越小。在程序中我假设有100万个会员,其中50W用户积分都在100以内,30W用户积分在100-10000,15W用户积分在10000-50000,5W用户积分在50000以上。
下面是各个操作的耗时时间:
可以看到,这个效率不是一般的快啊,其中获取排名的查询时间几乎可以忽略不计。这时候有人问了,这么多数据会不会非常吃内存,下面用任务管理器分别查看不使用树和使用树的内存情况:
运行环境是.NetCore3.0 Console,测试主机配置情况:
100万数据只有130M内存占用,对现代计算机来说简直是洒洒水~
业务环境中使用务必注意线程安全问题!!!
到此,相信大家对“如何在C#中使用二叉树实时计算海量用户积分排名”有了更深的了解,不妨来实际操作一番吧!这里是创新互联网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!
标题名称:如何在C#中使用二叉树实时计算海量用户积分排名
文章起源:http://scyanting.com/article/goidpg.html