TopN排行榜容器 TopNOrderedContainer -- ESBasic 可复用的.NET类库(20)

本文涉及的产品
容器服务 Serverless 版 ACK Serverless,317元额度 多规格
容器镜像服务 ACR,镜像仓库100个 不限时长
容器服务 Serverless 版 ACK Serverless,952元额度 多规格
简介: 1.缘起:     假设我们的会员管理系统有一个排行榜的功能,需要每隔一段时间就对系统中的所有会员(假设会员数有100万)的积分进行排序,然后对其中的前100名进行某些奖励。     这是一个典型的TopN算法――对巨大数量的对象进行排序,然后只需要取出最Top的前N名(N比对象总数小很多),作为排行榜的数据。

1.缘起:

    假设我们的会员管理系统有一个排行榜的功能,需要每隔一段时间就对系统中的所有会员(假设会员数有100万)的积分进行排序,然后对其中的前100名进行某些奖励。

    这是一个典型的TopN算法――对巨大数量的对象进行排序,然后只需要取出最Top的前N名(N比对象总数小很多),作为排行榜的数据。

    解决这样的问题,我们要注意一点,如果我们每次都对所有的对象进行完全排序,那无疑效率非常低下,而且非常不划算。因为我们只需要前N名,而不是所有对象的先后顺序。

    我设计了ESBasic.ObjectManagement.TopNOrderedContainer来解决排行榜算法,TopNOrderedContainer只将资源花费在真正需要计算的地方,另外,TopNOrderedContainer支持在运行过程中,将不断新产生的对象加入到排行榜。

 

2.适用场合:

    TopNOrderedContainer用于对巨大数量的对象进行TopN排序。其适用场合有如下特点:

(1)需要被排序的对象的数量非常巨大(如几百万、甚至几千万)。

(2)对系统有价值的排序结果只有前N名。

(3)N远小于总的对象数量。

 

3.设计思想与实现

    TopNOrderedContainer的排行榜算法的思路是这样的,使用一个长度为N的数组,来存放最TopN个对象,越Top的对象其在数组中的Index就越小。这样,每次加入一个对象时:

(1)首先,判断当前的排行榜的最后一名是否比新加入的对象更Top,如果是则丢弃它。

(2)其次,看新加入的对象是否比当前排行榜的第一名更Top,如果是,则新的对象应该被放置在index0的位置。

(3)否则,就采用二分查找算法为新加入的对象找到合适的位置,并调整排行榜中位于插入位置后面的对象的位置。

当然,在具体实现的源码中,我们看到了还有一些边界条件的处理这里没描述出来。

     TopNOrderedContainer的类图如下所示:

    我们看到TopNOrderedContainer有一个泛型参数TObj,它是进行排序的对象的类型。TObj的泛型约束表明TObj必须实现IOrdered接口。IOrdered接口定义如下:

 

    ///   <summary>
    
///  IOrdered 参与排行榜排序的对象必须实现的接口。
    
///   </summary>
    
///   <typeparam name="TOrderedObj"> 参与排行榜排序的对象的类型 </typeparam>
     public   interface   IOrdered < TOrderedObj >
    {
        
bool  IsTopThan( TOrderedObj  other);
    }

 

关于这个接口要注意两点:

    第一,该接口的唯一方法的名字为什么不是类似IsGreaterThanIsSmallerThan等,而是IsTopThan?因为不同的应用有不同的需求,有的可能是要选择前N个最大的,有的是要选择前N个最小的,甚至有的可能选择前N个最著名的,等等。而IsTopThan可以覆盖所有这些情况,反正都是最TopN个嘛。

    第二,IOrdered接口之所以使用泛型参数TOrderedObj,是为了避免派生类在实现IsTopThan方法时,需要将参数other的类型进行向下转换。

      

    现在我们在回到TopNOrderedContainer,关于其实现要注意以下几点:

(1)排行榜容器可以在多线程的环境中使用。TopNOrderedContainer使用SmartRWLocker来对Add方法进行同步,之所以选择读写锁而不是简单的lock,是因为使排行榜容器在应对多读/少写的状况时能支持更大的并发。

(2)排行榜的生成采用的是插入排序策略,排序的具体算法是二分查找排序。Adjust方法的实现就是二分查找算法的体现。

(3)GetTopN方法用于返回当前的排行榜的拷贝。之所以返回一个拷贝,是因为外部对返回的数组进行任何操作都不会影响到TopNOrderedContainer的内部集合。

(4)为何不将TopN排序直接实现为一个静态方法?如果以静态的方式实现,那我们就没有办法继续动态的Add新的对象进入排行榜,即使要达到这样的目的,也就只有构造新的list,再次调用static GetTopN方法,如此就浪费了前面的计算成果。

 

4. 使用时的注意事项

    如果要排序的对象的数量与TopNN值的差距并不大,那么使用TopNOrderedContainer并不一定是最佳的选择,这时我们可以采用一些高效的完全排序算法对所有的对象进行排序,然后再取出前N名,可能速度会更快。

  当然,我们也可以使用最大最小堆的算法来实现TopN的排序,也是完全可行的。

 

5.扩展

    TopN排行榜容器TopNOrderedContainer暂时没有任何扩展。

 

注: ESBasic已经开源,点击这里下载源码。
    
ESBasic开源前言

 

 

目录
相关文章
|
IDE API 开发工具
拦截|篡改|伪造.NET类库中不限于public的类和方法
本文除了回顾拦截.NET类库中的方法,实现方法参数的篡改、方法返回结果的伪造,再着重介绍.NET类库中非public类及方法如何拦截。
拦截|篡改|伪造.NET类库中不限于public的类和方法
|
容器
.net core Autofac IOC 容器的简单使用
## 书接上回,介绍了[.net core 读取配置文件的几种方式](https://developer.aliyun.com/article/1363340?spm=a2c6h.13148508.setting.14.21764f0ehMR1KI ".net core 读取配置文件的几种方式"),本文学习Autofac的同时再次增加一种读取配置文件的方法。 ## 本文介绍Auofac,一个优秀的.NET IOC框架 ## 源码地址:https://github.com/autofac/Autofac # 1、打开NuGet包管理器安装Autofac.Extensions.Dependenc
86 0
|
3月前
|
应用服务中间件 API 网络安全
运维笔记:宿主机转发实现多容器复用CA证书
运维笔记:宿主机转发实现多容器复用CA证书
37 4
|
3月前
|
开发框架 .NET Linux
2款高效的.NET二维码生成类库
2款高效的.NET二维码生成类库
|
3月前
|
XML 开发框架 数据格式
.Net Core 开发框架,支持多版本的类库
.Net Core 开发框架,支持多版本的类库
57 0
|
4月前
|
人工智能 开发框架 Devops
.NET技术概览:** 本文探讨了.NET的核心特性,包括多语言支持、Common Language Runtime、丰富的类库和跨平台能力,强调其在企业级、Web、移动及游戏开发中的应用。
【7月更文挑战第4天】.NET技术概览:** 本文探讨了.NET的核心特性,包括多语言支持、Common Language Runtime、丰富的类库和跨平台能力,强调其在企业级、Web、移动及游戏开发中的应用。此外,讨论了.NET如何通过性能优化、DevOps集成、AI与ML支持以及开源策略应对未来挑战,为开发者提供强大工具,共创软件开发新篇章。
51 3
|
4月前
|
人工智能 前端开发 Devops
NET技术在现代开发中的影响力日益增强,本文聚焦其核心价值,如多语言支持、强大的Visual Studio工具、丰富的类库和跨平台能力。
【7月更文挑战第4天】**.NET技术在现代开发中的影响力日益增强,本文聚焦其核心价值,如多语言支持、强大的Visual Studio工具、丰富的类库和跨平台能力。实际应用涵盖企业系统、Web、移动和游戏开发,以及云服务。面对性能挑战、容器化、AI集成及跨平台竞争,.NET持续创新,开发者应关注技术趋势,提升技能,并参与社区,共同推进技术发展。**
39 1
|
5月前
|
Linux Docker 容器
蓝易云 - net.ipv4.ip_forward=0导致docker容器无法与外部通信
完成以上步骤后,Docker容器应该能够正常与外部通信了。
241 2
|
4月前
|
开发框架 .NET API
.NET Core 和 .NET 标准类库项目类型有什么区别?
在 Visual Studio 中,可创建三种类库:.NET Framework、.NET Standard 和 .NET Core。.NET Standard 是规范,确保跨.NET实现的API一致性,适用于代码共享。.NET Framework 用于特定技术,如旧版支持。.NET Core 库允许访问更多API但限制兼容性。选择取决于兼容性和所需API:需要广泛兼容性时用.NET Standard,需要更多API时用.NET Core。.NET Standard 替代了 PCL,促进多平台共享代码。
|
6月前
|
C# 数据安全/隐私保护
一款实用的.NET Core加密解密工具类库
一款实用的.NET Core加密解密工具类库

热门文章

最新文章