TopN算法与排行榜代码,C#代码库,德仔网

代码语言
代码分类
【C#】 TopN算法与排行榜
作者:博文 / 发布于2017/2/23/ 576
如果一个对象要参与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
试试其它关键字
同语言下
可能有用的
博文贡献的其它代码(10)