网站首页
网站导航
Ctrl+D收藏
首 页
代码段
源码包
文档库
工具箱
代码语言
.
CSharp
.
JS
Java
Asp.Net
C
MSSQL
PHP
Css
PLSQL
Python
Shell
EBS
ASP
Perl
ObjC
VB.Net
VBS
MYSQL
GO
Delphi
AS
DB2
Domino
Rails
ActionScript
Scala
代码分类
文件
系统
字符串
数据库
网络相关
图形/GUI
多媒体
算法
游戏
Jquery
Extjs
Android
HTML5
菜单
网页交互
WinForm
控件
企业应用
安全与加密
脚本/批处理
开放平台
其它
【
C#
】
TopN算法与排行榜
作者:
博文
/ 发布于
2017-2-23
/
134
如果一个对象要参与TopN排行榜,则其必须实现IOrdered接口,表明其可以被Top排序。
/// <summary> /// IOrdered 参与排行榜排序的对象必须实现的接口。 /// </summary> /// <typeparam name="TOrderedObj">参与排行榜排序的对象的类型</typeparam> public interface IOrdered<TOrderedObj> { bool IsTopThan(TOrderedObj other); } 之所以使用泛型参数TOrderedObj,是为了避免派生类在实现IsTopThan方法时,需要将参数other进行向下转换。 接下来是TopNOrderedContainer实现的源码: /// <summary> /// TopNOrderedContainer 用于始终保持排行榜前N名的Object。该实现是线程安全的。 /// zhuweisky 2009.05.23 /// </summary> /// <typeparam name="TID">被排名的对象的标志类型</typeparam> /// <typeparam name="TObj">被排名的对象类型</typeparam> public class TopNOrderedContainer<TObj> where TObj : IOrdered<TObj> { private TObj[] orderedArray = null; private int validObjCount = 0; private SmartRWLocker smartRWLocker = new SmartRWLocker(); #region TopNumber private int topNumber = 10; public int TopNumber { get { return topNumber; } set { topNumber = value; } } #endregion #region Ctor public TopNOrderedContainer() { } public TopNOrderedContainer(int _topNumber) { this.topNumber = _topNumber; } #endregion #region Initialize public void Initialize() { if (this.topNumber < 1) { throw new Exception("The value of TopNumber must greater than 0 "); } this.orderedArray = new TObj[this.topNumber]; } #endregion #region Add List public void Add(IList<TObj> list) { if (list == null) { return; } using (this.smartRWLocker.Lock(AccessMode.Write)) { foreach (TObj obj in list) { this.DoAdd(obj); } } } #endregion #region Add public void Add(TObj obj) { using (this.smartRWLocker.Lock(AccessMode.Write)) { this.DoAdd(obj); } } #endregion #region GetTopN public TObj[] GetTopN() { using (this.smartRWLocker.Lock(AccessMode.Read)) { return (TObj[])this.orderedArray.Clone(); } } #endregion #region Private #region DoAdd private void DoAdd(TObj obj) { if (obj == null) { return; } if (this.validObjCount < this.topNumber) { this.orderedArray[this.validObjCount] = obj; this.Adjust(this.validObjCount); ++this.validObjCount; return; } if (this.orderedArray[this.topNumber - 1].IsTopThan(obj)) { return; } this.orderedArray[this.topNumber - 1] = obj; this.Adjust(this.topNumber - 1); } #endregion #region Adjust /// <summary> /// Adjust 调整posIndex处的对象到合适的位置。 /// 与相邻前一个对象比较,如果当前对象更加Top,则与前一个对象交换位置。 /// </summary> private void Adjust(int posIndex) { TObj obj = this.orderedArray[posIndex]; for (int index = posIndex; index > 0; index--) { if (obj.IsTopThan(this.orderedArray[index - 1])) { TObj temp = this.orderedArray[index - 1]; this.orderedArray[index - 1] = obj; this.orderedArray[index] = temp; } else { break; } } } #endregion #endregion } 源码面前毫无秘密。 但是有几点我还是需要说明一下: (1)ESBasic.ObjectManagement.TopNOrderedContainer位于我的ESBasic.dll类库中,其实现时用到的SmartRWLocker是一个读写锁,也是ESBasic.dll类库中的一员。你可以从这里下载ESBasic.dll直接试用。 (2)为何不将TopN排序直接实现为一个静态方法,如: public static TObj[] GetTopN<TObj>(IList<TObj> list) where TObj : IOrdered<TObj> 如果要是这样实现,那我们就没有办法继续动态的Add新的TObj对象进来,如果要达到这样的目的,就只有构造新的list,再次调用static GetTopN方法,如此会重复做一些工作。 最后,我们来测试一下TopNOrderedContainer与List.Sort方法的性能比较,测试的对象数目为500000个,取出Top20。测试代码如下: public class UserData : IOrdered<UserData> { #region UserID private string userID; public string UserID { get { return userID; } set { userID = value; } } #endregion #region Score private int score; public int Score { get { return score; } set { score = value; } } #endregion public UserData(string _userID, int _score) { this.userID = _userID; this.score = _score; } #region IOrdered<string> 成员 public bool IsTopThan(UserData other) { return this.Score > other.Score; } public override string ToString() { return this.score.ToString(); } #endregion } private void button4_Click(object sender, EventArgs e) { List<UserData> list = new List<UserData>(); for (int i = 0; i < 500000; i++) { list.Add(new UserData("User" + i.ToString(), i * i * i - 3 * i * i + 4 * i + 8)); } List<UserData> list2 = new List<UserData>(); for (int i = 0; i < 500000; i++) { list2.Add(new UserData("User" + i.ToString(), i * i * i - 3 * i * i + 4 * i + 8)); } Stopwatch stopwatch = new Stopwatch(); stopwatch.Start(); list.Sort(this); stopwatch.Stop(); long ms1 = stopwatch.ElapsedMilliseconds; stopwatch.Reset(); stopwatch.Start(); TopNOrderedContainer<UserData> container = new TopNOrderedContainer<UserData>(20); container.Initialize(); container.Add(list2); UserData[] res = container.GetTopN(); stopwatch.Stop(); long ms2 = stopwatch.ElapsedMilliseconds; } #region IComparer<UserData> 成员 public int Compare(UserData x, UserData y) { return (y.Score - x.Score); } #endregion
评论列表
本站所提供的代码,版权归原作者所有,若有侵犯作者版权,请与我们联系,我们将立即删除或修改。谢谢!
本站所有代码发布及提供者。
试试其它关键字
同语言下
.
利用ffmpeg将MP4文件切成ts和m3u8
.
实现 ffmpeg视频转码、播放
.
视频处理,调用强大的ffmpeg
.
c# 生成微信公众帐号带参数二维码类
.
asp.net 实现微信公众平台的主动推送信息
.
分词帮助类
.
将dt转化成Json数据
.
中文分词算法(实现从文章中提取关键字算法)
.
实现工作日和休息日(包括法定节假日)的计算
.
MVC使用Newtonsoft无需实体类,实现JSON数据返回给前
可能有用的
.
利用ffmpeg将MP4文件切成ts和m3u8
.
实现 ffmpeg视频转码、播放
.
视频处理,调用强大的ffmpeg
.
c# 生成微信公众帐号带参数二维码类
.
asp.net 实现微信公众平台的主动推送信息
.
分词帮助类
.
将dt转化成Json数据
.
中文分词算法(实现从文章中提取关键字算法)
.
实现工作日和休息日(包括法定节假日)的计算
.
MVC使用Newtonsoft无需实体类,实现JSON数据返回给前
博文
贡献的其它代码
(
10
)
.
查询sqlserver中某个表的定义的sql语句
.
判断手机浏览器
.
TopN算法与排行榜
.
#从HDFS加载数据
.
查询是否连接没有释放引起
.
调用手机本地通讯录查看联系人
.
不在同一时间出现的那个人--反选
.
不同类型的不连续的最小值
.
无向图块(bfs邻接阵形式)
.
复利计算
地图
本站
我们
服务
版权
联系
回馈
博客