Hello World
Spiga

数组排序方法的性能比较(3):LINQ排序实现分析

2010-01-27 00:02 by 老赵, 9099 visits

上次我们分析了Array.Sort<T>方法的实现方式,并了解到类库会为一些特例而使用高性能的排序方式——int数组便是这样一例,因此从测试结果上来看其性能特别高。不过从数据上看,即便是在普通的情况下,Array.Sort<T>的性能也比LINQ排序要高。不过也有朋友从测试中得出的结论正好相反,这又是为什么呢?那么现在,我们再来分析一下LINQ排序的实现方式吧,希望这样可以了解到两者性能差别的秘密。

只可惜,LINQ排序的代码在System.Core.dll程序集中,微软没有发布这部分源代码,我们只得使用.NET Reflector来一探究竟了。

LINQ排序接口的定义、使用及扩展

所谓LINQ排序,便是使用定义在System.Linq.Enumerable类中的几个扩展方法,它们是:

public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(
    this IEnumerable<TSource> source, Func<TSource, TKey> keySelector);

public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(
    this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer);

public static IOrderedEnumerable<TSource> OrderByDescending<TSource, TKey>(
    this IEnumerable<TSource> source, Func<TSource, TKey> keySelector);

public static IOrderedEnumerable<TSource> OrderByDescending<TSource, TKey>(
    this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer);

为了使用时的方便,我往往会补充一些额外的接口,例如:

public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(
    this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, bool decending)
{
    return decending ?
        source.OrderByDescending(keySelector) :
        source.OrderBy(keySelector);
}

这样在使用时,便可以使用一个布尔值来表示排序的方向(升序或是降序)而不需要从两个方法之间“手动”选择一个。此外,构造一个IComparer<TKey>类型也实在有些麻烦,于是我按照Array.Sort<T>的做法重新继续扩展了一个使用委托对象作为“比较器”的接口:

public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(
    this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Comparison<TKey> compare, bool decending)
{
    return decending ?
        source.OrderByDescending(keySelector, new FunctorComparer<TKey>(compare)) :
        source.OrderBy(keySelector, new FunctorComparer<TKey>(compare));
}

至于FunctorComparer类的实现,由于过于简单就省略了吧,贴出来也只是占用地方而已。有了这个接口,在排序的时候我们就可以这样使用了:

employee.OrderBy(p => p.Manager, (m1, m2) => ... /* 比较逻辑 */, false);

不过,无论是哪个接口、重载还是扩展,它的(除this外)的第一个参数便是keySelector,它的含义便是选择(select)出排序的“依据”。这个参数不可省略(除非您提供扩展),因此即便是int数组这样的类型,需要排序时也必须指定“自己”为排序依据:

intArray.OrderBy(i => i);

这也是LINQ排序和Array.Sort<T>的本质区别之一。

OrderedEnumerable的实现

无论是哪个接口,最终创建的都是OrderedEnumerable<TElement, TKey>类型,例如:

public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(
    this IEnumerable<TSource> source, Func<TSource, TKey> keySelector)
{
    return new OrderedEnumerable<TSource, TKey>(source, keySelector, null, false);
}

OrderedEnumerable<TElement, TKey>的含义是“根据TKey排序TElement序列的结果”,它的构造函数仅仅是保留传入的参数:

internal OrderedEnumerable(
    IEnumerable<TElement> source, Func<TElement, TKey> keySelector, IComparer<TKey> comparer, bool descending)
{
    // 省略参数校验

    base.source = source;
    this.parent = null;
    this.keySelector = keySelector;
    this.comparer = (comparer != null) ? comparer : ((IComparer<TKey>) Comparer<TKey>.Default);
    this.descending = descending;
}

可见,如果您没有提供比较器,类库会自动选用Comparer<TKey>.Default进行比较。这个类会尽可能地寻找可用的比较方式,在“万不得已”的情况下只得跑出异常。如果您对它的实现感兴趣可以自行阅读代码——甚至无需使用.NET Reflector。

事实上,在OrderedEnumerable<TElement, TKey>中并没有提供排序等关键性功能,它只是override了基类的GetEnumerableSorter方法,用于提供一个“排序器”。它的基类是OrderdEnumerable<TElement>,其含义是“排序TElement序列的结果”,它并不涉及到“排序方式”,而只是提供了一个抽象方法用于获得一个“排序器”——没错,这就是它的子类,如OrderedEnumerable<TElement, TKey>的职责了(还记得TKey的含义吗:“根据TKey进行排序”)。

不过,事实上除了OrderdEnumerable<TElement, TKey>以外也没有其他子类了,由于这些都是internal类型,因此我认为这样有些“过渡设计”。根据我们昨天“人肉反编译”的结果,可以得到OrderedEnumerable<TElement>的完整实现:

internal abstract class OrderedEnumerable<TElement> : IEnumerable<TElement>...
{
    internal IEnumerable<TElement> source;

    internal abstract EnumerableSorter<TElement> GetEnumerableSorter(EnumerableSorter<TElement> next);

    public IEnumerator<TElement> GetEnumerator()
    {
        var buffer = new Buffer<TElement>(this.source);
        if (buffer.count <= 0) yield break;

        var sorter = this.GetEnumerableSorter(null);
        var map = sorter.Sort(buffer.items, buffer.count);

        for (var i = 0; i < buffer.count; i++)
        {
            yield return buffer.items[map[i]];
        }
    }

    ...
}

与我们平时接触到的排序算法不同,EnumerableSorter的Sort方法并不改变原数组,它只是生成根据buffer.items数组生成一个排序之后的“下标序列”——即map数组。当外部需要输出排序后的序列时,OrderedEnumerable<TElement>才会根据map中的下标顺序,依次输出buffer.items数组中的元素。

请注意,到目前为止我们还是没有接触到最终的排序实现。换句话说,现在我们还是不清楚LINQ排序性能高(或低)的关键。

排序实现:EnumerableSorter

LINQ排序的实现关键还是在于EnumerableSorter<TElement>,我们且看其Sort代码:

internal abstract class EnumerableSorter<TElement>
{
    internal abstract int CompareKeys(int index1, int index2);
    internal abstract void ComputeKeys(TElement[] elements, int count);

    private void QuickSort(int[] map, int left, int right)
    {
        ...
    }

    internal int[] Sort(TElement[] elements, int count)
    {
        this.ComputeKeys(elements, count);

        int[] map = new int[count];
        for (int i = 0; i < count; i++)
        {
            map[i] = i;
        }

        this.QuickSort(map, 0, count - 1);
        return map;
    }
}

从之前的分析中得知,Sort方法的作用是返回一个排好序的下标数组。它会调用ComputeKeys抽象方法“事先”进行Key(也就是排序依据)的计算。然后再使用快速排序来排序map数组。在QuickSort中,它使用CompareKeys方法来获得“两个下标”所对应的元素的先后顺序。仅此而已,没什么特别的。甚至我在这里都不打算分析ComputeKeys和CompareKeys两个方法的实现,因为他们实在过于直接:前者会把source序列中的元素依次调用keySelector委托,以此获得一个与source对应的TKey数组,而后者便是根据传入的下标来比较TKey数组中对应的两个元素的大小。

不过,我还是强烈建议您阅读一下EnumerableSorter<TElement>及其子类EnumerableSorter<TElement, TKey>的实现,以此了解LINQ to Object是如何优雅地支持以下表达式的:

var sorted = from p in people
             orderby p.Age
             orderby p.ID descending
             select p;

这个表达式的含义是“将Person序列首先根据Age属性进行升序排列,如果Age相同则再根据ID降序排”——类库在实现时使用了类似于“职责链模式”的做法,颇为美观。

LINQ排序与Array.Sort<T>的性能比较

如果您仔细阅读EnuerableSorter的QuickSort方法,会发现它使用的快速排序算法并不“标准”。快速排序的性能关键之一是选择合适的pivot元素,但是QuickSort方法总是选择最中间的元素——(left + right) / 2。此外,它也没有在元素小于一定阈值时使用更高效的插入排序。因此,从理论上来说,QuickSort方法使用的快速排序算法,其性能不如Array.Sort<T>。

不过,根据姜敏兄的测试结果,LINQ排序的性能超过Array.Sort<T>,这又是怎么回事呢?事实上,虽然姜兄的这个测试存在很大的问题(代码写错了),最后得到的结论“性能高低和元素类型有关”的结论也不确切,但是它也的确能体现一些问题。这个问题事实上已经由Ivony...老大解释过了,不过为了信息完整思维连贯,我在这里再进行详细说明一下。

从理论上来说,Array.Sort<T>和LINQ排序的时间复杂度是相同的,因此性能“似乎不会有太大不同”,但是从实验结果上看差距还是十分明显的。因为从实际上看,Array.Sort<T>对于特殊类型有特殊处理,此外LINQ排序会有复制元素的开销,因此我之前我认为“找不到LINQ排序的性能有优势的理由”。可惜这句话已经站不住脚了,我们来观察一下两种排序方式在实现上的主要区别:

  • Array.Sort<T>:使用IComparer<T>对象比较两个元素的大小。
  • LINQ排序:首先根据keySelector获得TKey序列,然后在排序时使用IComparer<TKey>比较两个TKey元素的大小。

那么,以此您是否可以判断出以下两个排序方法的性能高低?

public class Person
{
    public int Age { get; set; }
}

public class PersonComparer : IComparer<Person>
{
    public int Compare(Person x, Person y)
    {
        return x.Age - y.Age;
    }
}
Person[] people = ...

var byLinq = people.OrderBy(p => p.Age).ToList();
var byArray = Array.Sort(people, new PersonComparer());

在实际测试之前我无法做出判断,因为它们其实各有千秋:

  • Array.Sort<T>:虽然不需要进行额外的元素复制,但是调用PersonComparer.Compare方法的开销较大——访问Age属性相当于调用get_Age方法(如果没有内联的话——不过从实际结果看的确被内联了)。
  • LINQ排序:虽然需要进行额外的元素复制,而且需要事先计算出排序用的键值(Age属性),但是在排序时只需直接比较int即可,效率较高。

这其实也就是某些测试中发现LINQ排序性能较高的“秘密”。为什么同样排序Person序列时,我的测试(http://gist.github.com/282796)表明Array.Sort<T>较快,而其他一些朋友却得到LINQ排序较快的结果呢?这是因为我的Person类直接使用了公开字段而不是属性,这样避免了方法调用的开销(因为有内联,这点应该不是问题)。此外,另一些朋友的PersonComparer在比较两个int时使用了x.Age.CompareTo方法——这又比直接进行int减法要慢上一些了。

那么,还有影响两者性能的因素吗?我们有办法提高数组排序的性能吗?毕竟很多时候我们需要直接排序,而不是生成新的序列。下次我们再来讨论这些问题吧。

相关文章

Creative Commons License

本文基于署名 2.5 中国大陆许可协议发布,欢迎转载,演绎或用于商业目的,但是必须保留本文的署名赵劼(包含链接),具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言

Add your comment

25 条回复

  1. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2010-01-27 00:41:00

    有些细节描述好像不太对。一般调用getter都是被内联掉了的。CLRv2对小的、直线型、非虚方法会很“照顾”,如果是在循环中调用这样的方法会更加“照顾”。而自动生成的getter里就是一个成员变量访问+一个返回,除非作为某个基类型的虚属性的override实现,或者被打上了noinline标记,不然肯定是被内联的。

    using System;
    using System.Runtime.CompilerServices;
    
    namespace TestCLRv2JITInlinePropertyAccess {
        public class Person {
            public int _age;
    
            public int Age {
                get { return _age; }
                set { _age = value; }
            }
        }
    
        static class Program {
            [MethodImpl(MethodImplOptions.NoInlining)]
            static int Foo(Person p) {
                return p.Age;
            }
    
            [MethodImpl(MethodImplOptions.NoInlining)]
            static int Bar(Person p) {
                return p._age;
            }
    
            static void Main(string[] args) {
                var p = new Person();
                Console.WriteLine(p.Age);
                Foo(p);
                Bar(p);
            }
        }
    }


    这里的Foo和Bar分别是:
    Normal JIT generated code
    TestCLRv2JITInlinePropertyAccess.Program.Foo(TestCLRv2JITInlinePropertyAccess.Person)
    Begin 00c200c0, size 8
    00C200C0 55               push        ebp
    00C200C1 8BEC             mov         ebp,esp
    00C200C3 8B4104           mov         eax,dword ptr [ecx+4]
    00C200C6 5D               pop         ebp
    00C200C7 C3               ret
    
    Normal JIT generated code
    TestCLRv2JITInlinePropertyAccess.Program.Bar(TestCLRv2JITInlinePropertyAccess.Person)
    Begin 00c200e0, size 8
    00C200E0 55               push        ebp
    00C200E1 8BEC             mov         ebp,esp
    00C200E3 8B4104           mov         eax,dword ptr [ecx+4]
    00C200E6 5D               pop         ebp
    00C200E7 C3               ret

    是一样的对吧?

  2. Leon Weng
    *.*.*.*
    链接

    Leon Weng 2010-01-27 00:54:00

    老赵最近关注性能了 以前也做过不少测试 List<T> HashTable 等等 感觉各有有点吧 用的地方不一样 跟string 和 stringBuilder类似 ,最近想采用asp.net mvc和Linq 进行开发,老赵有推荐的demo或者开源代码么,我在codeplex上找了几个,感觉不太合适。

  3. 老赵
    admin
    链接

    老赵 2010-01-27 00:56:00

    @RednaxelaFX
    但实际测试Age是属性还是字段对性能有明显影响的说。
    不知道是不是记错了,明天我试验一下吧。

  4. 老赵
    admin
    链接

    老赵 2010-01-27 00:57:00

    @Leon Weng
    性能测试其实也不好说,比如现在这个明显是分情况有不同说法的。
    如果int或Person类随便选一个,就算两个都选也不一定能得到正确结果的……

  5. Leon Weng
    *.*.*.*
    链接

    Leon Weng 2010-01-27 01:01:00

    哎 写错了应该是string的"+"和"apend()"

  6. Leon Weng
    *.*.*.*
    链接

    Leon Weng 2010-01-27 01:07:00

    测试图个真实 公开字段用的频率远没有属性高吧

  7. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2010-01-27 01:26:00

    Int32.CompareTo()倒是确实比直接减一下“慢一些”

    using System;
    using System.Runtime.CompilerServices;
    
    namespace TestCLRv2JITInlinePropertyAccess {
        public class Person {
            public int _age;
    
            public int Age {
                get { return _age; }
                set { _age = value; }
            }
        }
    
        static class Program {
            [MethodImpl(MethodImplOptions.NoInlining)]
            static int Compare1(Person p1, Person p2) {
                return p1.Age.CompareTo(p2.Age);
            }
    
            [MethodImpl(MethodImplOptions.NoInlining)]
            static int Compare2(Person p1, Person p2) {
                if (p1.Age < p2.Age) return -1;
                if (p1.Age > p2.Age) return 1;
                return 0;
            }
    
            [MethodImpl(MethodImplOptions.NoInlining)]
            static int Compare3(Person p1, Person p2) {
                return p1.Age - p2.Age;
            }
    
            static void Main(string[] args) {
                var p = new Person();
                Console.WriteLine(p.Age);
                Compare1(p, p);
                Compare2(p, p);
                Compare3(p, p);
            }
        }
    }


    其中的Compare1,2,3分别是:
    Normal JIT generated code
    TestCLRv2JITInlinePropertyAccess.Program.Compare1(TestCLRv2JITInlinePropertyAccess.Person, TestCLRv2JITInlinePropertyAccess.Person)
    Begin 00430118, size 2e
    00430118 55               push        ebp
    00430119 8BEC             mov         ebp,esp
    0043011B 50               push        eax
    0043011C 33C0             xor         eax,eax
    0043011E 8945FC           mov         dword ptr [ebp-4],eax
    00430121 8B4104           mov         eax,dword ptr [ecx+4]
    00430124 8945FC           mov         dword ptr [ebp-4],eax
    00430127 8B5204           mov         edx,dword ptr [edx+4]
    0043012A 3955FC           cmp         dword ptr [ebp-4],edx
    0043012D 7D05             jge         00430134
    0043012F 83C8FF           or          eax,0FFFFFFFFh
    00430132 EB0E             jmp         00430142
    00430134 3955FC           cmp         dword ptr [ebp-4],edx
    00430137 7E07             jle         00430140
    00430139 B801000000       mov         eax,1
    0043013E EB02             jmp         00430142
    00430140 33C0             xor         eax,eax
    00430142 8BE5             mov         esp,ebp
    00430144 5D               pop         ebp
    00430145 C3               ret
    
    Normal JIT generated code
    TestCLRv2JITInlinePropertyAccess.Program.Compare2(TestCLRv2JITInlinePropertyAccess.Person, TestCLRv2JITInlinePropertyAccess.Person)
    Begin 00430158, size 23
    00430158 55               push        ebp
    00430159 8BEC             mov         ebp,esp
    0043015B 8B4104           mov         eax,dword ptr [ecx+4]
    0043015E 3B4204           cmp         eax,dword ptr [edx+4]
    00430161 7D05             jge         00430168
    00430163 83C8FF           or          eax,0FFFFFFFFh
    00430166 5D               pop         ebp
    00430167 C3               ret
    00430168 8B4104           mov         eax,dword ptr [ecx+4]
    0043016B 3B4204           cmp         eax,dword ptr [edx+4]
    0043016E 7E07             jle         00430177
    00430170 B801000000       mov         eax,1
    00430175 5D               pop         ebp
    00430176 C3               ret
    00430177 33C0             xor         eax,eax
    00430179 5D               pop         ebp
    0043017A C3               ret
    
    Normal JIT generated code
    TestCLRv2JITInlinePropertyAccess.Program.Compare3(TestCLRv2JITInlinePropertyAccess.Person, TestCLRv2JITInlinePropertyAccess.Person)
    Begin 00430190, size b
    00430190 55               push        ebp
    00430191 8BEC             mov         ebp,esp
    00430193 8B4104           mov         eax,dword ptr [ecx+4]
    00430196 2B4204           sub         eax,dword ptr [edx+4]
    00430199 5D               pop         ebp
    0043019A C3               ret

    Compare2()是我手动把Int32.CompareTo()内联到Compare1()的版本。试了会儿没能把两个版本调到完全一样……CLRv2的内联器看来还有点不顺,生成了少量无意义的代码。Anyway,可以看到这三个版本里get_Age()都是被内联了的,但要把比较值映射到-1、0、1上要比直接减多干点活儿。
    不过这个差异到底在测试中占了多少分量我没把握……

  8. 蛙蛙王子
    *.*.*.*
    链接

    蛙蛙王子 2010-01-27 01:42:00

    我访问博客园这么慢呀怎么,热了。
    RednaxelaFX的每个评论都很猛呀

  9. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2010-01-27 01:59:00

    蛙蛙王子:
    我访问博客园这么慢呀怎么,热了。
    RednaxelaFX的每个评论都很猛呀


    我只是贴了JIT后的机器码及其汇编而已……没技术含量的。要得到同样的信息很简单:
    1、打开VS2008,建一个C#的命令行应用工程;
    2、复制上面的代码;
    3、确认在主菜单的Tools -> Options... -> Debugging -> Suppress JIT optimization on module load (Managed only)前的勾是去掉的;
    4、在project的属性里,把Debug -> Enable unmanaged code debugging前的勾打上;
    5、在要分析的方法的开始处设断点;
    6、按F5或者那个绿色箭头执行程序,到断点之后,在Immediate Window里输入.load sos
    7、在Registers窗口里复制下EIP的值,然后在Immediate Window输入!u 01B70129 (!u后的数字替换为EIP的实际值);
    8、应该能看到那个方法的机器码与汇编了。

    只是机械性的完成了这些步骤而已……真正有技术含量的是后续的分析。这个还是交给老赵了,我提供炮弹。阅读别人的评测与分析后的好习惯是自己也动手做一做,看看能否得到一致的、可重复的结果。

  10. 幸存者
    *.*.*.*
    链接

    幸存者 2010-01-27 02:12:00

    我调试的结果和RednaxelaFX一样,属性被内联了。
    并且我在老赵给出的测试代码中新加了一个完全用属性的Person类,测试结果也表明用属性和用字段进行linq排序的性能没有明显的区别,完全可以忽略它们之间的性能差别。

  11. 蛙蛙王子
    *.*.*.*
    链接

    蛙蛙王子 2010-01-27 02:13:00

    恩,谢谢,我会在vs里加载sos和执行!u,就是还不太会看,呵呵。
    看个IL还凑合,汇编看不懂ing。
    最近老赵更新了很多,还没来得及细看,抽空补补。
    看你的评论很长知识呀。

  12. 幸存者
    *.*.*.*
    链接

    幸存者 2010-01-27 02:20:00

    蛙蛙王子:
    恩,谢谢,我会在vs里加载sos和执行!u,就是还不太会看,呵呵。
    看个IL还凑合,汇编看不懂ing。
    最近老赵更新了很多,还没来得及细看,抽空补补。
    看你的评论很长知识呀。


    就目前讨论的问题来说,完全没必要看懂汇编语言。只要能明白属性在JIT时被内联了就行。
    有两点都可以证明这个结论:1,访问属性和访问字段的方法JIT后的汇编完全一样;2,按理说访问属性其实是方法调用,但是汇编中没出现call指令,那么合理的解释应该是被调方法体已经内联进了调用方法体中。

  13. 姜敏
    *.*.*.*
    链接

    姜敏 2010-01-27 08:43:00

    嗯,等我有时间后,再慢慢看,一次性能测试跟着老赵学了不少东西,不错.

  14. Ivony...
    *.*.*.*
    链接

    Ivony... 2010-01-27 09:27:00

    其实我想也是会被内联的,但事实上倒确实是测出了性能差距,不过我现在更倾向于认为这是正常的结果扰动。当然,也可能有不明因素影响.
    多次测试后,发现这个结果似乎站不住脚。

    不过从理论上来说,只要GetKey足够复杂,序列足够大,KeySelector模式就能体现出可以观察的优势,我做检讨去了。。。T-T

  15. 韦恩卑鄙 alias:v-zhewg
    *.*.*.*
    链接

    韦恩卑鄙 alias:v-zhewg 2010-01-27 09:44:00

    @Ivony...
    我来看热闹

  16. 老赵
    admin
    链接

    老赵 2010-01-27 09:56:00

    原来还是会被内联的呀?我去修改一下原文咯。
    还好我文章里的“道理”还是没错,万幸……

  17. 幸存者
    *.*.*.*
    链接

    幸存者 2010-01-27 10:17:00

    @Ivony...
    我唯一想到的keySelector的优势或许是keySelector的执行密度比较高,locality相对较好,大概也更有利于分支预测。
    至于GetKey的开销,我觉得对linq和Array.Sort应该都是一样的。

  18. 老赵
    admin
    链接

    老赵 2010-01-27 10:23:00

    @幸存者
    keySelcter方式的优势,在于首先选出每个元素的Key,它们一般就是些int之类的简单值,比较起来性能高。
    也就是说,LINQ排序的话GetKey调用N次(N是元素个数),如果是Array.Sort的话,每次比较的时候都会GetKey,这样自然调用超过大大超过N次,比如K * N * log(N)。
    这就是两者性能有差异的主要地方(之一?)。

  19. 老赵
    admin
    链接

    老赵 2010-01-27 10:50:00

    @Jeffrey Zhao:
    原来还是会被内联的呀?我去修改一下原文咯。
    还好我文章里的“道理”还是没错,万幸……


    的确性能没啥差距,估计被内联了……

  20. 幸存者
    *.*.*.*
    链接

    幸存者 2010-01-27 10:52:00

    @Jeffrey Zhao
    有道理,这一点我倒是没想到。
    我只想到两种排序方式都要对每个元素作GetKey,不过忽略了Array.Sort调用GetKey的次数等于比较次数,呵呵。

  21. Ivony...
    *.*.*.*
    链接

    Ivony... 2010-01-27 10:59:00

    幸存者:
    @Jeffrey Zhao
    有道理,这一点我倒是没想到。
    我只想到两种排序方式都要对每个元素作GetKey,不过忽略了Array.Sort调用GetKey的次数等于比较次数,呵呵。




    是比较次数 * 2(要获取两个Key才能比较),而比较次数应该是必然大于N-1的(无论什么算法)。


    所以只要GetKey足够复杂,就一定有性能优势。

  22. tianxd
    *.*.*.*
    链接

    tianxd 2010-02-10 23:28:00

    * Array.Sort<T>:虽然不需要进行额外的元素复制,但是调用PersonComparer.Compare方法的开销较大——访问Age属性相当于调用get_Age方法(如果没有内联的话——不过从实际结果看的确被内联了)。
    * LINQ排序:虽然需要进行额外的元素复制,而且需要事先计算出排序用的键值(Age属性),但是在排序时只需直接比较int即可,效率较高。


    Linq在排序是需要调用CompareKeys,如下:
    internal override int CompareKeys(int index1, int index2)
    {
    int num = this.comparer.Compare(this.keys[index1], this.keys[index2]);
    if (num == 0)
    {
    if (this.next == null)
    {
    return (index1 - index2);
    }
    return this.next.CompareKeys(index1, index2);
    }
    if (!this.descending)
    {
    return num;
    }
    return -num;
    }
    其中this.comparer.Compare会最终调用到GenericComparer<int>.Compare,所以想问问:linq排序中【只需直接比较int即可,效率较高】的结论怎么解释呢?

  23. 老赵
    admin
    链接

    老赵 2010-02-10 23:49:00

    @tianxd
    比较两个int的时候无论是Array.Sort还是LINQ Sort都会用到GenericComparer<int>.Compare,不过Array.Sort需要算上get_Age的开销,而LINQ Sort不需要。
    文章里其实已经说了,要不再看看?

  24. tianxd
    *.*.*.*
    链接

    tianxd 2010-02-11 10:03:00

    @Jeffrey Zhao
    嗯,Array在Sort的时候访问get_Age次数多,Linq在Sort之前已经get_Age(就一次)了所以Sort就不需要了,不过他们都被内敛了影响大吗?
    而PersonComparer比较使用x.Age - y.Age,Linq用int.ComapreTo,应该这个对效率影响相对较大


  25. 老赵
    admin
    链接

    老赵 2010-12-06 20:52:49

    @tianxd

    兄弟没仔细看文章啊,或者你做下实验也就知道了。

发表回复

登录 / 登录并记住我 ,登陆后便可删除或修改已发表的评论 (请注意保留评论内容)

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

评论内容(大于5个字符):

  1. Your Name yyyy-MM-dd HH:mm:ss

使用Live Messenger联系我