优化OrderBy().First()

C# linq可以写这样的代码

var myFile = directory.GetFiles()
             .OrderByDescending(f => f.LastWriteTime)
             .First();

^[1]用来获取一个目录里最新修改的文件。

这个代码看起来效率不高，因为我们排序了整个列表，但只需取出第一个元素。所以计算复杂度是[latex]O(n \log( n))[/latex]。

经常听到linq擅长延迟计算，linq能不能遇到OrderBy().First()就不要执行快速排序，退化成找最小值的O(n)算法？下面研究这个问题。

小试身手

linq在需要迭代时才计算前面制定的操作，并可以智能合并。所以我的退化算法应该写在First()里。查看OrderBy()的返回类型，是IOrderedEnumerable<TElement>，所以要对IOrderedEnumerable<TElement>写一个扩展方法。

static class EnumerableExtensions
{
    public static TSource First<TSource>(this IOrderedEnumerable<TSource> source)
    {
        var type = source.GetType();
        if (type.FullName.StartsWith("System.Linq.OrderedEnumerable"))
        {
            //在.net core 2，这个字段是_source，但是reference source显示.net framework 4.7.1里这个字段是source。
            FieldInfo sourceField = type.GetField("_source", BindingFlags.NonPublic | BindingFlags.Instance);
            IEnumerable<TSource> _source = (IEnumerable<TSource>)sourceField.GetValue(source);

            FieldInfo keySelectorField = type.GetField("_keySelector", BindingFlags.NonPublic | BindingFlags.Instance);
            dynamic _keySelector = keySelectorField.GetValue(source);

            FieldInfo comparerField = type.GetField("_comparer", BindingFlags.NonPublic | BindingFlags.Instance);
            dynamic  comparer = comparerField.GetValue(source);

            FieldInfo descendingField = type.GetField("_descending", BindingFlags.NonPublic | BindingFlags.Instance);
            bool descending = (bool)descendingField.GetValue(source);

            dynamic largestKey = null;
            TSource largestItem = default(TSource);
            foreach (TSource item in _source)
            {
                dynamic key = _keySelector(item);
                if (largestKey == null)
                {
                    largestKey = key;
                    largestItem = item;
                }
                else if (comparer.Compare(key, largestKey) == (descending ? 1 : -1))
                {
                    largestKey = key;
                    largestItem = item;
                }
            }

            return largestItem;
        }
        else
            return ((IEnumerable<TSource>)source).First();
    }
}

这里用反射取出OrderedEnumerable的私有字段。_keySelector和comparer只能是dynamic类型，因为无法从当前上下文获得前一个linq操作的类型参数。由于dynamic类型的方法调用都是基于反射的，而反射比强类型方法调用慢数十倍，所以上面的代码运行速度反而比最简单的OrderBy().First()慢。

static void Main(string[] args)
{
    int[] arr = new int[10000000];
    var rand = new Random();
    for (int j = 0; j < arr.Length; j++)
    {
        arr[j] = rand.Next(arr.Length);
    }


    Stopwatch sw = new Stopwatch();
    sw.Start();
    var a = arr.OrderBy(element => element).First();
    sw.Stop();
    Console.WriteLine($"优化的算法耗时{sw.ElapsedMilliseconds}ms: {a}");

    sw.Restart();
    var b = ((IEnumerable<int>)arr.OrderBy(element => element)).First();
    sw.Stop();
    Console.WriteLine($"原始算法耗时{sw.ElapsedMilliseconds}ms: {b}");
}

返璞归真

难道就没有更好的方法了吗？转念一想，这就是个min、max操作。添加

sw.Restart();
var c = arr.Min();
sw.Stop();
Console.WriteLine($"min算法耗时{sw.ElapsedMilliseconds}ms: {b}");

到主程序

速度不用想肯定是最快的，因为是O(n)复杂度，也没有耗时的反射操作。

本文一开始提出的获取文件夹内最近修改文件的问题，用min/max来解决就是

var directory = new DirectoryInfo("C:\\MyDirectory");
var directories = directory.GetDirectories();
var mostRecentWriteTime = directories.Max(d => d.LastWriteTime);
var mostRecentPlayFolder = directories.First(d => d.LastAccessTime == mostRecentWriteTime);

为了避免重复计算和重复迭代，代码不得不写成四行，看起来不如一开始的写法那么高端。

这次经验再次证明了一件事：往往类库自带的方法就可以解决问题，不需要自己费时费力地去抽象、包装、添加额外的复杂度。我见过太多时候，软件工程师们添加自己的方法，而不知道或不使用类库的类似方法，这导致经验不可移植，即具有正宗.NET经验的人难以接手这个项目，以及熟悉项目那套API的人难以编写其他（开源）.NET项目。

参考资料

1. Scott Ivey. How to find the most recent file in a directory using .NET, and without looping?. . 2009-07-24 [2018-04-02].↑