1.缘起:
假设我们的会员管理系统有一个排行榜的功能,需要每隔一段时间就对系统中的所有会员(假设会员数有100万)的积分进行排序,然后对其中的前100名进行某些奖励。
这是一个典型的TopN算法――对巨大数量的对象进行排序,然后只需要取出最Top的前N名(N比对象总数小很多),作为排行榜的数据。
解决这样的问题,我们要注意一点,如果我们每次都对所有的对象进行完全排序,那无疑效率非常低下,而且非常不划算。因为我们只需要前N名,而不是所有对象的先后顺序。
我设计了ESBasic.ObjectManagement.TopNOrderedContainer来解决排行榜算法,TopNOrderedContainer只将资源花费在真正需要计算的地方,另外,TopNOrderedContainer支持在运行过程中,将不断新产生的对象加入到排行榜。
2.适用场合:
TopNOrderedContainer用于对巨大数量的对象进行TopN排序。其适用场合有如下特点:
(1)需要被排序的对象的数量非常巨大(如几百万、甚至几千万)。
(2)对系统有价值的排序结果只有前N名。
(3)N远小于总的对象数量。
3.设计思想与实现
TopNOrderedContainer的排行榜算法的思路是这样的,使用一个长度为N的数组,来存放最Top的N个对象,越Top的对象其在数组中的Index就越小。这样,每次加入一个对象时:
(1)首先,判断当前的排行榜的最后一名是否比新加入的对象更Top,如果是则丢弃它。
(2)其次,看新加入的对象是否比当前排行榜的第一名更Top,如果是,则新的对象应该被放置在index为0的位置。
(3)否则,就采用二分查找算法为新加入的对象找到合适的位置,并调整排行榜中位于插入位置后面的对象的位置。
当然,在具体实现的源码中,我们看到了还有一些边界条件的处理这里没描述出来。
TopNOrderedContainer的类图如下所示:
我们看到TopNOrderedContainer有一个泛型参数TObj,它是进行排序的对象的类型。TObj的泛型约束表明TObj必须实现IOrdered接口。IOrdered接口定义如下:
<!--<br/ /><br/ />Code highlighting produced by Actipro CodeHighlighter (freeware)<br/ />http://www.CodeHighlighter.com/<br/ /><br/ />--> ///<summary>
///IOrdered参与排行榜排序的对象必须实现的接口。
///</summary>
///<typeparamname="TOrderedObj">参与排行榜排序的对象的类型</typeparam>
publicinterfaceIOrdered<TOrderedObj>
{
boolIsTopThan(TOrderedObjother);
}
关于这个接口要注意两点:
第一,该接口的唯一方法的名字为什么不是类似IsGreaterThan、IsSmallerThan等,而是IsTopThan?因为不同的应用有不同的需求,有的可能是要选择前N个最大的,有的是要选择前N个最小的,甚至有的可能选择前N个最著名的,等等。而IsTopThan可以覆盖所有这些情况,反正都是最Top的N个嘛。
第二,IOrdered接口之所以使用泛型参数TOrderedObj,是为了避免派生类在实现IsTopThan方法时,需要将参数other的类型进行向下转换。
现在我们在回到TopNOrderedContainer,关于其实现要注意以下几点:
(1)排行榜容器可以在多线程的环境中使用。TopNOrderedContainer使用SmartRWLocker来对Add方法进行同步,之所以选择读写锁而不是简单的lock,是因为使排行榜容器在应对多读/少写的状况时能支持更大的并发。
(2)排行榜的生成采用的是插入排序策略,排序的具体算法是二分查找排序。Adjust方法的实现就是二分查找算法的体现。
(3)GetTopN方法用于返回当前的排行榜的拷贝。之所以返回一个拷贝,是因为外部对返回的数组进行任何操作都不会影响到TopNOrderedContainer的内部集合。
(4)为何不将TopN排序直接实现为一个静态方法?如果以静态的方式实现,那我们就没有办法继续动态的Add新的对象进入排行榜,即使要达到这样的目的,也就只有构造新的list,再次调用static GetTopN方法,如此就浪费了前面的计算成果。
4. 使用时的注意事项
如果要排序的对象的数量与TopN的N值的差距并不大,那么使用TopNOrderedContainer并不一定是最佳的选择,这时我们可以采用一些高效的完全排序算法对所有的对象进行排序,然后再取出前N名,可能速度会更快。
当然,我们也可以使用最大最小堆的算法来实现TopN的排序,也是完全可行的。
5.扩展
TopN排行榜容器TopNOrderedContainer暂时没有任何扩展。
注:ESBasic源码可到http://esbasic.codeplex.com/下载。
ESBasic讨论:37677395
ESBasic开源前言
分享到:
相关推荐
本人将 zhuweisky博主的博客整理成了PDF文件,以便于脱机浏览,没有经过博主的同意就这么做 实在是不好意思^-^ 现将其资料免费下载 以示对博主的尊重 源博客地址:...
.NET设计规范:约定、惯用法与模式,在.net环境下进行开发设计的经典之作,权威指导.
LiteGo:「迷你」的Android异步并发类库LiteGo是一款基于Java语言的「异步并发类库」,它的核心是一枚「迷你」并发器,它可以自由地设置同一时段的最大「并发」数量,等待「排队」线程数量,还可以设置「排队策略」...
新版根据.NET Framework 3.0和3.5的新特性做了全面更新,主要关注的是直接影响框架可编程能力的设计问题。遵守这些规范对于使用.NET Framework创建高质量的应用程序至关重要。 本书提供配套光盘,内含Designing ...
NET应用架构设计原则、模式与实践.pdf NET应用架构设计原则、模式与实践.pdf
应用系统建立在此框架之上,采用构件式、可复用开发,节省开发成本,加快开发速度,在软件开发上更好的做到多快省。 适合低中高任意开发水平的开发者,可以开发OA、ERP、BPM、CRM、WMS、TMS、MIS、BI、电商平台后台、...
新版根据.NET Framework 3.0和3.5的新特性做了全面更新,主要关注的是直接影响框架可编程能力的设计问题。遵守这些规范对于使用.NET Framework创建高质量的应用程序至关重要。 本书提供配套光盘,内含Designing ...
自己写的ado.net类库,已实现有关数据库操作的各种方法,子类只需提供数据库连接,即可调用,极大了实现了代码复用.这是我针对实际开发中经常需要重复开发数据库操作而提出的解决方案. 注意,该类实现的是关于sqlserver...
2.2.3 自说明对象模型原则 20 2.2.4 分层架构原则 25 2.3 小结 27 第3章 命名规范 28 3.1 大小写约定 29 3.1.1 标识符的大小写规则 29 3.1.2 首字母缩写词的大小写 31 3.1.3 复合词和常用术语的大小...
博文地址:http://blog.csdn.net/csnd_ayo/article/details/72457190
这里收集一些著名的 C/C++ 开发库、SDK、类库、可复用类与结构代码 等信息,列举它们的介绍、参考和网站链接,为各位 C/C++ 程序员和爱好者提供检索和查阅类库的方便。 下面收集的 C/C++ 类库介绍整理来源于文章:...
自从.NET推出以来,他已使用.NET帮助很多行业的用户开发了体现其商业理念的软件产品.Xin Chen是.NET和EAI方面的专家,他与Microsoft和Accenture等多家技术领先的公司合作,为它们的客户提供了优秀的解决方案....
此外,还可以创建一个新类库实现软件复用。 • 第十章介绍.NET下的数据库支持,阐述了ADO.NET的基本概念和结构,并通过示例詊细介绍C#下Web Service数据库访问的方法。 • 第十一章将在以前的基础上介绍一个...
这些规范历经.NET框架三个版本的长期开发,凝聚了数千名开发人员的经验和智慧。微软的各开发组正在使用这些规范开发下一代影响世界的软件产品。 第1章 概述 1 1.1 精心设计的框架所具备的品质 2 1.1.1 精心...
.NET20 一种简单的窗口控件UI状态控制方法 翻译MSDN文章 —— 泛型FAQ:最佳实践 Visual C# 3.0 新特性概览 C# 2.0会给我们带来什么 泛型技巧系列:如何提供类型参数之间的转换 C#2.0 - Object Pool 简单实现 ...
Android应用源码开发Demo,主要用于毕业设计学习。
Android应用源码开发Demo,主要用于毕业设计学习。
本书结合设计实例从面向对象的设计中精选出23个设计模式,总结了面向对象设计中最有价值的经验,并且用简洁可复用的形式表达出来。本书分类描述了一组设计良好、表达清楚的软件设计模式,这些模式在实用环境下特别...
关于机载软件重用的咨询通告,为机载设备研制单位重用先前开发的软件提供指导。