List<T>在排序上的性能测试

看了老赵写的性能测试文章(数组排序方法的性能比较（上）：注意事项及试验),的确长了不少见识,不过我对他的结论也不完全同意,为此针对我的测试环境进行一翻改造。

第一条：ASP.NET执行.NET代码的时候，使用的是IIS进程中托管的CLR，它的配置和直接运行.NET应用程序时不同（不同的CLR托管方式配置很可能不一样——例如SQL Server里托管的CLR）。

所以我放弃asp.net,选用Console应用程序来进行性能测试。

第二条：更改数据结果，生成一个序号号分散的List<T>。

1：生成一个大的随机数组：

var random = new Random(DateTime.Now.Millisecond);
var array = Enumerable.Repeat(0, 500001).Select(_ => random.Next()).ToArray();

2：利用随机数组的元素做为我们测试用的List<T>子元素Person类的ID

代码

            List<Person> list = new List<Person>();
            for (int i = 0; i < 500001; i++)
            {
                Person p = new Person();
                p.firstName = i.ToString() + "firstName";
                p.lastName = i.ToString() + "lastName";
                p.ID = array[i];
                list.Add(p);

            }

第三条：增加测试次数。之前我只排序一次，这里我来排序5次。

代码

            int iCount=5;
            Stopwatch sw = new Stopwatch();
            sw = new Stopwatch();
            sw.Start();
            for (int i = 0; i < iCount; i++)
            {
                list.Sort(new PersonComparer());
            }
            sw.Stop();
            Console.WriteLine("Sort排序用时" + sw.ElapsedMilliseconds.ToString());

            sw = new Stopwatch();
            sw.Start();
            for (int i = 0; i < iCount; i++)
            {
                var pn = (from m in list
                          orderby m.ID descending
                          select m).ToList<Person>();
            }
            sw.Stop();
            Console.WriteLine("linq排序用时" + sw.ElapsedMilliseconds.ToString());

第四条:增加release版本的测试。

说明：代码中相关类如下：

代码

    public class Person
    {
        public string firstName
        { get; set; }
        public string lastName
        { get; set; }
        public int ID
        { get; set; }
    }
    public class PersonComparer : IComparer<Person>
    {
        public int Compare(Person x, Person y)
        {
            return x.ID.CompareTo(y.ID);
        }

    }

测试结果：还是和之前的结果一样，LINQ在排序上明显有优势。

我们来换一种测试，我是对List<T>来进行测试，其中的T是一个对象，并不是数值性的，老赵文中排序的是array[int]，下面代码中的array就是之前生成的无序数组。测试代码如下：

代码

            sw = new Stopwatch();
            sw.Start();
            for (int i = 0; i < iCount; i++)
            {
                SortWithDefaultComparer(array);
            }
            sw.Stop();
            Console.WriteLine("Sort 数组排序用时" + sw.ElapsedMilliseconds.ToString());

            sw = new Stopwatch();
            sw.Start();
            for (int i = 0; i < iCount; i++)
            {
                SortWithLinq(array);
            }
            sw.Stop();
            Console.WriteLine("linq 数组排序用时" + sw.ElapsedMilliseconds.ToString());

      测试结果：和老赵文中一样，LINQ会差很多。

      比较:老赵和我的测试环境还是一个特别大的差别,他在文中有这段话:每次生成新的序列也会带来开销，如果使用List<T>的话，填充元素的开销会很大，但如果是普通数组的话，就可以用性能很高的Array.Copy方法了。
             问题就在这，我的方法中是对Person类排序，排序字段为ID，而老赵排序的是int[],这里我再写一个测试，测试Array<T>的性能，当然这个T并非int,而是Person。

      1:我们先创建一个Person[],这个Person[]的ID和上面一样，是无序的。

代码

            Person[] alist = new Person[500001];
            for (int i = 0; i < 500001; i++)
            {
                Person p = new Person();
                p.firstName = i.ToString() + "firstName";
                p.lastName = i.ToString() + "lastName";
                p.ID = array[i];
                alist[i] = p;

            }

2：调用Array.Sort方法。

代码

        static void SortWithDefaultComparerList(Person []  array)
        {
            Array.Sort(array, new PersonComparer());
        }
        static T[] CloneArray<T>(T[] source)
        {
            var dest = new T[source.Length];
            Array.Copy(source, dest, source.Length);
            return dest;
        }

            sw = new Stopwatch();
            sw.Start();
            for (int i = 0; i < iCount; i++)
            {
                SortWithDefaultComparerList(CloneArray(alist ));

            }
            sw.Stop();
            Console.WriteLine("Arr数组排序用时" + sw.ElapsedMilliseconds.ToString());

测试结果：同样是LINQ方法更优。

总结:对于List<T>的排序,从性能角度来看:

1:T的类型会对结果产生重要影响,并不能片面的说LINQ方式排序更强于或者差于List.Sort或者是Array.Sort。

2:当T的属性越来越多时， LINQ方式的优势会更加明显。

本文可执行代码见文末:

老赵的codertimer执行情况和我的测试结果一样。

下图是debug下的结果，linq 效果明显，release版本下，linq稍微强一点点,相差无几。

release版本

代码

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.Diagnostics;
using System.Threading;
using System.Runtime.InteropServices;
namespace ConsoleApplication1
{
    public static class CodeTimer
    {
        public static void Initialize()
        {
            Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
            Thread.CurrentThread.Priority = ThreadPriority.Highest;
            Time("", 1, () => { });
        }
        public static void Time(string name, int iteration, Action action)
        {
            if (String.IsNullOrEmpty(name)) return;
            // warm up
            action();
            // 1.
            ConsoleColor currentForeColor = Console.ForegroundColor;
            Console.ForegroundColor = ConsoleColor.Yellow;
            Console.WriteLine(name);
            // 2.
            GC.Collect(GC.MaxGeneration, GCCollectionMode.Forced);
            int[] gcCounts = new int[GC.MaxGeneration + 1];
            for (int i = 0; i <= GC.MaxGeneration; i++)
            {
                gcCounts[i] = GC.CollectionCount(i);
            }
            // 3.
            Stopwatch watch = new Stopwatch();
            watch.Start();
            ulong cycleCount = GetCycleCount();
            for (int i = 0; i < iteration; i++) action();
            ulong cpuCycles = GetCycleCount() - cycleCount;
            watch.Stop();
            // 4.
            Console.ForegroundColor = currentForeColor;
            Console.WriteLine("\tTime Elapsed:\t" + watch.ElapsedMilliseconds.ToString("N0") + "ms");
            Console.WriteLine("\tCPU Cycles:\t" + cpuCycles.ToString("N0"));
            // 5.
            for (int i = 0; i <= GC.MaxGeneration; i++)
            {
                int count = GC.CollectionCount(i) - gcCounts[i];
                Console.WriteLine("\tGen " + i + ": \t\t" + count);
            }
            Console.WriteLine();
        }
        private static ulong GetCycleCount()
        {
            ulong cycleCount = 0;
            QueryThreadCycleTime(GetCurrentThread(), ref cycleCount);
            return cycleCount;
        }
        [DllImport("kernel32.dll")]
        [return: MarshalAs(UnmanagedType.Bool)]
        static extern bool QueryThreadCycleTime(IntPtr threadHandle, ref ulong cycleTime);
        [DllImport("kernel32.dll")]
        static extern IntPtr GetCurrentThread();
    }
    class Program
    {
        static void Main(string[] args)
        {


            var random = new Random(DateTime.Now.Millisecond);
            var array = Enumerable.Repeat(0, 500001).Select(_ => random.Next()).ToArray();
            List<Person> list = new List<Person>();
            for (int i = 0; i < 500001; i++)
            {
                Person p = new Person();
                p.firstName = i.ToString() + "firstName";
                p.lastName = i.ToString() + "lastName";
                p.ID = array[i];
                list.Add(p);

            }
            Person[] alist = new Person[500001];
            for (int i = 0; i < 500001; i++)
            {
                Person p = new Person();
                p.firstName = i.ToString() + "firstName";
                p.lastName = i.ToString() + "lastName";
                p.ID = array[i];
                alist[i] = p;

            }
            int iCount = 5;
            Stopwatch sw = new Stopwatch();


            sw = new Stopwatch();
            sw.Start();
            for (int i = 0; i < iCount; i++)
            {
                List<Person> newlist = list ;
                SortWithLinqList(newlist );
            }
            sw.Stop();
            Console.WriteLine("linq 数组排序用时" + sw.ElapsedMilliseconds.ToString());

            sw = new Stopwatch();
            sw.Start();
            for (int i = 0; i < iCount; i++)
            {
                SortWithDefaultComparerList(CloneArray(alist));
            }
            sw.Stop();
            Console.WriteLine("Arr数组排序用时" + sw.ElapsedMilliseconds.ToString());

            //老赵程序
            var randoms = new Random(DateTime.Now.Millisecond);
            var arrays = Enumerable.Repeat(0, 1000 * 500).Select(_ => new Person { ID = random.Next(),firstName="aaa",lastName ="bbb" }).ToArray();
            CodeTimer.Initialize();
            CodeTimer.Time("SortWithCustomComparer", 5, () => SortWithCustomComparer(CloneArray(arrays)));
            CodeTimer.Time("SortWithLinq", 5, () => SortWithLinq(CloneArray(arrays)));
            Console.ReadLine();
            Console.ReadKey();
        }
        static void SortWithCustomComparer(Person[] array)
        {
            Array.Sort(array, new PersonComparer());
        }
        static void SortWithDefaultComparer(int[] array)
        {
            Array.Sort(array, Comparer<int>.Default);
        }

        static void SortWithLinq(Person[] array)
        {
            var sorted =
                (from i in array
                 orderby i.ID
                 select i).ToList();
        }

        static void SortWithDefaultComparerList(Person[] array)
        {
            Array.Sort(array, new PersonComparer());
        }
        static T[] CloneArray<T>(T[] source)
        {
            var dest = new T[source.Length];
            Array.Copy(source, dest, source.Length);
            return dest;
        }
        static void SortWithLinqList(List<Person> list)
        {
            var sorted =
                (from i in list
                 orderby i.ID
                 select i).ToList();
        }


    }
    public class Person
    {
        public string firstName
        { get; set; }
        public string lastName
        { get; set; }
        public int ID
        { get; set; }
        public string lastName2
        { get; set; }
        public string lastName3
        { get; set; }
        public string lastName4
        { get; set; }
        public string lastName5
        { get; set; }
        public string lastName6
        { get; set; }
        public string lastName7
        { get; set; }
        public string lastName8
        { get; set; }
        public string lastName9
        { get; set; }
        public string lastName10
        { get; set; }
    }
    public class PersonComparer : IComparer<Person>
    {
        public int Compare(Person x, Person y)
        {
            return x.ID - y.ID;
        }

    }
}

List<T>在搜索和排序时采用不同方法的性能比较