.NET中数组和List的排序“探秘”

昨天给某个同学做了一个Excel数据处理的小工具,最后需要把处理后的结果进行排序。大家都知道List类提供了一个Sort方法能够对列表中的元素进行排序,这个东东是怎么使用的呢?它又是怎么实现的呢?为了满足自己的“好奇心”,现在来进行“探秘”吧。

首先Array类的Sort方法有非常多的重载版本,其中每一种都有泛型和非泛型的方法:

QQ截图20140112110308

 

看参数类型就知道每一个重载的使用场合。基本上,对于整个数组的排序,它提供了三种方式:默认比较器、IComparer接口的比较器和Comparison<T>的泛型委托。

List<T>是泛型类,它的Sort方法重载要简洁得多,我们还是从List<T>开始吧:

        public void Sort();
        public void Sort(Comparison<T> comparison);
        public void Sort(IComparer<T> comparer);
        public void Sort(int index, int count, IComparer<T> comparer);

首先第一种方式,就是无参数的Sort方法,按照微软的说明,就是“使用默认比较器对整个 System.Collections.Generic.List<T> 中的元素进行排序”。这里的“默认比较器”,就是T类型实现的IComparable(或起泛型接口IComparable<T>)接口时所提供的比较器。对于简单的值类型,M$都实现了IComparable<T>接口,所以直接调用list.Sort()方法即可实现升序排列,非常简便。但是假如你的排序方式和默认的不同(例如是逆序或有其他特殊需求),又或者你使用的不是简单的值类型,那么.NET无论如何都不知道如何进行排序了,这时必须自己实现IComparable或泛型接口或者使用其他重载,否则会在运行时抛出System.InvalidOperationException类型的异常。这么说来在编译的时候,.NET是无法检测Sort方法是否有效的,因为在定义List<T>时它并未指定T是否需要实现IComparable<T>接口。

我现在定义了下面这样的一个OutputFormat结构体:

        internal struct OutputFormat
        {
            public string UserIdentity;
            public string OutputIdentity;
            public string Content;
            public decimal TotalMoney;
        }

然后呢,我希望它按照下面的规则进行排序:如果OutputIdentity是空字符串,那么就把它放在结果的最下面,其他的无所谓。

为了说明这个Sort方法比较“神奇”的地方,我分别尝试了如下几个实现方式:

1. 实现IComparable接口

这个接口并不是一个泛型接口,所以参数是一个object类型,首先呢,我按照下面这样来实现这个接口:

            public int CompareTo(object obj)
            {
                OutputFormat that = (OutputFormat)obj;

                if (that.OutputIdentity.Length == 0)
                    return 1;

                return -1;
            }

恩,只要OutputIdentity为空,就认为它在被比较的元素后面,否则呢就认为它在被比较元素的前面。非常偷懒吧?嘿嘿,下面我们来运行一下:

QQ截图20140112110308

 

杯具了,这么偷懒是不行的。错误提示里已经说得很清楚了,一个元素与自身比较时如果没有返回0,那么.NET认为比较器有问题,会抛出一个异常。

我偏偏就不信了,于是改成下面这样,不管怎么样都认为当前元素在另一元素的后面,这样也应该出错吧:

            public int CompareTo(object obj)
            {
                return 1;
            }

可是神奇的是并没有出错!最后得到的结果是乱序的,根本不知道是按什么顺序排的!那么疑问就来了:.NET在排序前不会检查x.CompareTo(x)是否会返回0,那么什么时候会有这种情况呢

2. 实现IComparable<T>接口

好吧,非泛型接口还要做类型转换,似乎比较麻烦,那么我们实现一下IComparable<T>这个泛型的接口吧,我还是像上面那样使用“错误”的方法进行排序:

            public int CompareTo(OutputFormat other)
            {
                if (other.OutputIdentity.Length == 0)
                    return 1;

                return -1;
            }

运行一下,嘿嘿,错误快抛出来!但是又杯具了,没有抛出任何异常,反而是程序无响应,说明Sort方法陷入了死循环!后来,我按照非泛型接口的方式直接return 1,这时错误又出现了!这个问题实在是很诡异,说明在调用这两个接口时,.NET的实现方式是不同的。它到底是如何实现的呢?我们还是来看一下.NET的源代码吧。

 

恩,跟踪源代码,发现List类调用的是Array.Sort<T>(_items, index, count, comparer),并且comparer传入了null值,那么还是看下Array类的代码吧。省略掉一些参数的判断和Contracts的检查,这个方法的代码如下:

            if (length > 1) {
                if (comparer == Comparer.Default || comparer == null) {
                    bool r = TrySZSort(keys, items, index, index + length - 1); 
                    if (r)
                        return; 
                } 

                Object[] objKeys = keys as Object[]; 
                Object[] objItems = null;
                if (objKeys != null)
                    objItems = items as Object[];
                if (objKeys != null && (items==null || objItems != null)) { 
                    SorterObjectArray sorter = new SorterObjectArray(objKeys, objItems, comparer);
                    sorter.IntrospectiveSort(index, length); 
                } 
                else {
                    SorterGenericArray sorter = new SorterGenericArray(keys, items, comparer); 
                    sorter.IntrospectiveSort(index, length);
                }
            }

总体来说分成了两种逻辑:提供了比较器和没提供比较器的。我们目前关心的当然是没提供比较器的情况,那么会使用TrySZSort这个方法。SZ的意思是“单维零下标”数组,看样子.NET似乎只能对这样的数组进行排序,如果不是单维或者不是0下标(这个是可以的),似乎是必须提供比较器的。

然后看TrySZSort方法,果然是native的代码,果断google取得之。绕了一大圈,最后调用了这个方法:

FCIMPL4(FC_BOOL_RET, ArrayHelper::TrySZSort, ArrayBase * keys, ArrayBase * items, UINT32 left, UINT32 right)
    WRAPPER_CONTRACT;
    STATIC_CONTRACT_SO_TOLERANT;

    VALIDATEOBJECTREF(keys);
	VALIDATEOBJECTREF(items);
    _ASSERTE(keys != NULL);

    if (keys->GetRank() != 1 || keys->GetLowerBoundsPtr()[0] != 0)
        FC_RETURN_BOOL(FALSE);

	_ASSERTE(left <= right);
	_ASSERTE(right < keys->GetNumComponents() || keys->GetNumComponents() == 0);

    TypeHandle keysTH = keys->GetArrayElementTypeHandle();
    const CorElementType keysElType = keysTH.GetVerifierCorElementType();
    if (!CorTypeInfo::IsPrimitiveType(keysElType))
        FC_RETURN_BOOL(FALSE);
	if (items != NULL) {
		TypeHandle itemsTH = items->GetArrayElementTypeHandle();
		if (keysTH != itemsTH)
			FC_RETURN_BOOL(FALSE);   // Can't currently handle sorting different types of arrays.
	}

	if (left == right || right == 0xffffffff)
		FC_RETURN_BOOL(TRUE);

    switch(keysElType) {
    case ELEMENT_TYPE_I1:
		ArrayHelpers<I1>::QuickSort((I1*) keys->GetDataPtr(), (I1*) (items == NULL ? NULL : items->GetDataPtr()), left, right);
		break;

    case ELEMENT_TYPE_U1:
    case ELEMENT_TYPE_BOOLEAN:
        ArrayHelpers<U1>::QuickSort((U1*) keys->GetDataPtr(), (U1*) (items == NULL ? NULL : items->GetDataPtr()), left, right);
        break;

    case ELEMENT_TYPE_I2:
        ArrayHelpers<I2>::QuickSort((I2*) keys->GetDataPtr(), (I2*) (items == NULL ? NULL : items->GetDataPtr()), left, right);
        break;
       //省略一大段基元类型的判断方法

    default:
        _ASSERTE(!"Unrecognized primitive type in ArrayHelper::TrySZSort");
        FC_RETURN_BOOL(FALSE);
    }
    FC_RETURN_BOOL(TRUE);
FCIMPLEND

哦,那么它首先使用keysTH.GetVerifierCorElementType取得数组元素类型的内部表示,这是一个CorElementType类型的枚举(参见这里),如果发现不是基元类型,直接return false了。我们的显然不是基元类型,所以又转回Array的Sort方法了。顺便一提,可以看到M$对基元类型都是使用的QuickSort这个方法。这个玩意我们以后再看吧。

回到Array.Sort方法,排序使用了两种内部类:SortObjectArray和SortGenericArray。参考注释,这两种类唯一的不同就是获取元素的方式,对于可以直接转换成object[]类型的数组,都会使用SortObjectArray这个类,其他情况使用另一个(有什么数组不能转换到object[]呢?这点我还不明白)。那么我们来看SortObjectArray好了。

(更新: 这个方法传入的items和keys参数的类型都是Array。Array并没有提供索引器的泛型方法,而是提供了GetValue和SetValue来对其中的元素进行访问,而这两个方法的对象类型都是Object。Array类的索引器是实现自IList接口,而其也是调用的GetValue和SetValue方法。

对于任何一个用户使用标准语法定义的数组,比如string[] s,系统会实现IList<T>接口,这是在SZArrayHelper这个类中实现的。这样才能使用s[index]的方式进行随机访问,且返回值类型不是Object。而这些数组都可以被显式转换成Object[]类型。在List<T>和其他集合的内部,大多都使用T[]的形式存储元素,所以他们调用Sort方法时都会使用SortObjectArray。

从通常的角度来说,并不是每一个从Array类派生的数组都实现了IList<T>,因此不能假定都可以以T[index]的方式对元素进行访问。故此处对这两种情况进行了区分。

如果不进行这样的区分而都使用IList非泛型接口,那么得到的值都是Object的类型,那么进行排序的效率会降低很多。由此可见,当无法转换成Object[]类型的时候,会不可避免地使用SortGenericArray,效率会比SortObjectArray低很多。

用户不能自己从Array类派生,所以大多数情况应该都实现了IList<T>。我目前还不知道有没实现这个接口且从Array类派生的情况。如果发现了以后再更新。)

(更新2:List<T>调用的Array类的Sort方法应该是泛型重载 Sort<T>(T[] array, int index, int length, IComparer<T> comparer) 这个版本。因为List<T>传入的_items是一个实现了IList<T>的数组,在编译器应该会选择这个版本的重载,而不会像上面那样去判断需要使用SortGenericArray还是SortObjectArray。)

Sort调用的IntrospectiveSort称之为“内省式排序”,貌似没见过这种排序方法,不过没关系,我们来看一下:

IntroSort(left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(keys.Length));

第三个参数是depthLimit,其值是Log2(Length)*2,顺带一提,这个FloorLog2的实现是这样的( 至于为什么没有使用Math类,原因不明):

        internal static int FloorLog2(int n)
        {
            int result = 0; 
            while (n >= 1)
            { 
                result++; 
                n = n / 2;
            } 
            return result;
        }

接下来就是重点了,请擦亮眼睛:

            private void IntroSort(int lo, int hi, int depthLimit)
            { 
                while (hi > lo) 
                {
                    int partitionSize = hi - lo + 1; 
                    if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold)
                    {
                        if (partitionSize == 1)
                        { 
                            return;
                        } 
                        if (partitionSize == 2) 
                        {
                            SwapIfGreaterWithItems(lo, hi); 
                            return;
                        }
                        if (partitionSize == 3)
                        { 
                            SwapIfGreaterWithItems(lo, hi-1);
                            SwapIfGreaterWithItems(lo, hi); 
                            SwapIfGreaterWithItems(hi-1, hi); 
                            return;
                        } 

                        InsertionSort(lo, hi);
                        return;
                    } 

                    if (depthLimit == 0) 
                    { 
                        Heapsort(lo, hi);
                        return; 
                    }
                    depthLimit--;

                    int p = PickPivotAndPartition(lo, hi); 
                    IntroSort(p + 1, hi, depthLimit);
                    hi = p - 1; 
                } 
            }

可以看出这个算法的核心还是快速排序,但是做了一点改进。

IntrosortSizeThreshold的取值是16,那么意味着:当前要排序的片段不超过16个时,使用插入排序;当元素个数超过16个时且depth为0时,改用堆排序完成这个片段。这样做的原因是:不当的枢轴选择,导致不当的分割,导致快速排序恶化为O(N^2)。其实这个算法也不复杂:当递归层次超过2Log(n)时,就认为快排有恶化的倾向,转向使用堆排序。当片段不超过16个元素,使用插入排序;此时每个序列有相当程序的排序,但尚未完全排序,这时使用插入排序,效率是非常高的。

OK,排序算法看完了,但是貌似跑题了,前面说的使用IComparable和IComparable<T>行为不一致的问题似乎还是没有得到解答。

导致越界的原因,是因为快速排序过程中有下面这个循环:

            while (left < right)
            { 
                while (comparer.Compare(keys[++left], pivot) < 0) ; 
                while (comparer.Compare(pivot, keys[--right]) < 0) ;

                if (left >= right)
                    break;

                Swap(keys, left, right); 
            }

如果我们的比较器对于相同的元素不能返回0,那么就会越出keys这个数组的边界(因为没有下标保护)。当这里出错时,Array类自然会返回一个IndexOutOfRange的错误,这个时候.NET就认为是比较器有问题,从而抛出最开始的那个错误。

那么为什么两种实现方式会有两种结果呢?在两者都出错的情况下,通过查看异常的堆栈,发现使用了两种不同的类:GenericArraySortHelper<T>和ArraySortHelper<T>,通过名字就可以知道,前者是实现了泛型的IComparable<T>接口时使用的,后者则是没有实现泛型接口时使用的。当不提供泛型接口时,.NET会使用Comparer类(注意这个类也有一个泛型类IComparer<T>),而这个类提供了一个Compare的方法:

        public int Compare(Object a, Object b) {
            if (a == b) return 0;
            if (a == null) return -1; 
            if (b == null) return 1;
            if (m_compareInfo != null) { 
                String sa = a as String; 
                String sb = b as String;
                if (sa != null && sb != null) 
                    return m_compareInfo.Compare(sa, sb);
            }

            IComparable ia = a as IComparable; 
            if (ia != null)
                return ia.CompareTo(b); 

            IComparable ib = b as IComparable;
            if (ib != null) 
                return -ib.CompareTo(a);

            throw new ArgumentException(Environment.GetResourceString("Argument_ImplementIComparable"));
        }

那么这里就可以看出与泛型接口的不同行为:

  • 当使用泛型接口时,.NET直接调用CompareTo方法,也就是我们自己实现的接口方法;
  • 当使用非泛型接口时,.NET首先进行引用判断,相同引用直接返回0。否则才使用我们实现的CompareTo方法。

但即使是这样,似乎也说明不了问题,从调试输出来看,并没有相同引用进行比较的过程。那么原因应该出自ArraySortHelper<T>这个类上。通过两个类的比较,总算发现了下面这个地方的行为稍有不同:

QQ截图20140112110308

 

ArraySortHelper<T>类的比较过程为:left vs 基准,基准 vs right,而GenericArraySortHelper<T>则都是以基准元素为“起始”元素对left和right进行比较。

由于之前实现的CompareTo方法有问题,而两种实现方式取基准元素的行为不一致,所以导致排序过程中元素的排序顺序也不一致,最终才发生一个出错一个死循环。

 

绕了半天终于解答了自己心中的疑虑。看来有时候实现错误的方法并不是坏事,如果我没有好玩实现一个错误的比较器,也不会查看这方面的源代码去了解排序的机制。

从上面这个“探秘”过程可以发现,实现一个正确的CompareTo方法是非常重要的,这也可能会是很多问题潜伏的地方:看似相同的实现方式,结果可能不一致;看似排序没有问题的调试,可能在运行时由于数据的不同而出错或排序错误。所以,我们的CompareTo方法要尽可能地动脑筋写,上面这种偷懒的方式显然是不恰当的。

回到开始的部分,List类提供了多种Sort方法重载,这主要是为了应对多种排序方式。比如实现IComparable<T>和IComparable接口只能实现一种排序方式,对于基本类型也只能实现升序排列。如果需要多种排序方式,最方便地就是使用Comparison<T>这个重载,这个重载接收一个委托,我们只需要写一个Lambda表达式即可实现排序:

            _outputList.Sort((x, y) =>
                {
                    if (x.OutputIdentity.Length == 0 && y.OutputIdentity.Length > 0) return 1;
                    if (x.OutputIdentity.Length > 0 && y.OutputIdentity.Length == 0) return -1;
                    if (x.OutputIdentity.Length == 0 && y.OutputIdentity.Length == 0) return x.UserIdentity.CompareTo(y.UserIdentity);

                    return x.OutputIdentity.CompareTo(y.OutputIdentity);
                });

这个比较器应该是一个比较完美的比较器,它不仅可以实现最开始需要的功能(OutputIdentity为空的行在最后面),而且将不为空的行按照起字母顺序排列,为空的行之间还可以进行第二关键字的排序。

 

最后关于基本类型的Sort过程,这个东东在ArrayHelpers模板类里(clr\src\vm\comarrayhelpers.h),实现就是一个快速排序算法。我看的这个头文件和cpp文件的版本是2.0的,不知道在4.5版本里M$有没有像不是基本类型那样使用了自省式排序,不过看MSDN上貌似是使用了的,说明微软在2.0版本之后还是做了改进的。

至于排序效率,基本类型显然是最快的,因为它不需要调用任何接口方法也不会生成任何比较器(在不提供比较器的情况下),直接使用比较运算符,其次人家是native的方法,貌似不会进行边界检查。

如果需要逆序排序,是先用默认的排再使用Reverse方法反过来,还是提供一个比较器呢?个人认为应该是提供一个比较器,因为Reverse方法的代码是这样的:

    static void Reverse(KIND array[], UINT32 index, UINT32 count) {
        LEAF_CONTRACT;

        _ASSERTE(array != NULL);
        if (count == 0) {
            return;
        }
        UINT32 i = index;
        UINT32 j = index + count - 1;
        while(i < j) {
            KIND temp = array[i];
            array[i] = array[j];
            array[j] = temp;
            i++;
            j--;
        }
    }

显然是O(n)的复杂度。但是你说比较器有额外的开销,说不定会比这个要慢?恩,这点我还没试过,不过乃自己可以试试。 ^_^

7条评论


  1. 楼主写这样的一篇技术博客大约要花多久时间呢?
    我自己的经验来看,光是写这文章至少要花3个小时吧,还不包括前期的发现问题、解决问题的过程

    Firefox 26.0 Firefox 26.0 Ubuntu x64 Ubuntu x64
    回复

    1. 写这种东西当然很费时间。
      首先想要深入一个问题的时候,本身就会花很多时间去看代码或写自己的程序去测试。
      然后写的过程中还有可能会产生新的问题,所以再去看再来写。
      后来还有可能发现原先写的有不对或需要补充(比如我这篇的蓝色部分),还得修改。
      像我这篇日志花了一个下午的时间研究+写完,晚上还花了不少时间进行修正和补充。

      Google Chrome 31.0.1650.63 Google Chrome 31.0.1650.63 Windows 7 x64 Edition Windows 7 x64 Edition
      回复

    2. Me too, 写技术博客真的好费时间

      Firefox 26.0 Firefox 26.0 Ubuntu x64 Ubuntu x64
      回复

  2. 我在博客里面回答了乃提出的问题~~

    Firefox 26.0 Firefox 26.0 Ubuntu x64 Ubuntu x64
    回复

  3. C++的std::sort的实现貌似是插入排序+introsort(快排+堆排)
    为了提高实用性,下了很大的功夫啊

    Google Chrome 30.0.1599.101 Google Chrome 30.0.1599.101 Windows 7 x64 Edition Windows 7 x64 Edition
    回复

    1. 现在的类库里面基本都是采用的这种算法(.NET在2.0和更早版本只使用了快排)。
      而且,.NET在对基础类型进行默认排序的时候直接是调用的C++的native代码。由此可见微软在性能上还是做了不少考虑的。
      但是如果基础类型不是默认排序的情况下,开销似乎要大得多(相较于C++的代码而言)。由于.NET不支持内联方法,所以其性能应该和非基础类型一样。。。

      Google Chrome 31.0.1650.63 Google Chrome 31.0.1650.63 Windows 7 x64 Edition Windows 7 x64 Edition
      回复

    2. 当然我上面的评论说C++的native代码比.NET的快,并不是说.NET实现的程序一定比C++的要慢。.NET的native代码是和平台相关的。
      在JIT编译器即时编译指令的时候,会根据所使用的处理器和系统平台生成对应的机器指令,在运行时效率通常会比非托管的程序高(毕竟使用非托管语言的时候,要假定CPU的指令集最小,而且大多是针对x86的,以兼容不同的平台;当然除非是指定了运行平台)。
      这点我觉得是托管语言的很大一个优势。

      Google Chrome 31.0.1650.63 Google Chrome 31.0.1650.63 Windows 7 x64 Edition Windows 7 x64 Edition
      回复

发表评论

电子邮件地址不会被公开。