优化OrderBy().First()

2018年4月2日

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].