在系统中，我们经常会遇到这样的需求：将大量（比如几十万、甚至上百万）的对象进行排序，然后只需要取出最Top的前N名作为排行榜的数据，这即是一个TopN算法。常见的解决方案有三种：
（1）直接使用List的Sort方法进行处理。
（2）使用排序二叉树进行排序，然后取出前N名。
（3）使用最大堆排序，然后取出前N名。
第一种方案的性能是最差的，后两种方案性能会好一些，但是还是不能满足我们的需求。最主要的原因在于使用二叉树和最大堆排序时，都是对所有的对象进行排序，而不是将代价花费在我们需要的少数的TopN上。为此，我自己实现了TopNOrderedContainer来解决这个问题。
思路是这样的，使用一个长度为N的数组，来存放最Top的N个对象，越Top的对象其在数组中的Index就越小。这样，每次加入一个对象时，就与Index最大的那个对象比较，如果比其更Top，则交换两个对象的位置。如果被交换的对象是数组中的最后一个对象（Index最大），则该对象会被抛弃。如此，可以保证容器中始终保持的都是最Top的N个对象。
接下来我们看具体的实现。
如果一个对象要参与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类库中的一员。你可以从这里直接试用。
（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