具有Linq性能优势的Quicksort传递T []与IEnumerable <T>

Question

为了好玩,我用Linq在C#中构建了一个quicksort实现:

public static IEnumerable<T> quicksort<T>(IEnumerable<T> input) where T : IComparable<T>{
    if (input.Count() <= 1) return input;
    var pivot = input.FirstOrDefault();
    var lesser = quicksort(input.Skip(1).Where(i => i.CompareTo(pivot) <= 0));
    var greater = quicksort(input.Where(i => i.CompareTo(pivot) > 0));
    return lesser.Append(pivot).Concat(greater);
}

它在大约13秒内对10000个随机整数进行排序.

将其更改为使用int []而不是List会使性能提高约700倍!对相同的10000个随机整数进行排序只需要21ms.

public static T[] quicksortArray<T>(T[] input) where T : IComparable<T>{
    if (input.Count() <= 1) return input;
    var pivot = input.FirstOrDefault();
    var lesser = quicksortArray(input.Skip(1).Where(i => i.CompareTo(pivot) <= 0).ToArray());
    var greater = quicksortArray(input.Where(i => i.CompareTo(pivot) > 0).ToArray());
    return lesser.Append(pivot).Concat(greater).ToArray();
}

只是看看我会假设的代码会有更差的性能.我假设.ToArray()会在内存中创建一个额外的数组并复制所有整数.我认为传递数组与传递列表应该大约需要同一时间.

那么这个巨大的性能差异来自哪里呢？

Answer 1

这就是为什么你应该非常小心IEnumerable多次迭代.

第一次打电话给quicksort你,比方说 List.它再调用quicksort两次,在每种情况下,IEnumerable您传入的代表一个查询将跳过第一个项目,然后在每个项目之后执行比较.然后你把该查询,并将它传递两个更多的实例quicksort,但使查询不仅跳过第一个项目,并在其后每一项比较,但随后跳过该查询的结果的第一项,然后经过每一个项目比较是某事.这意味着,当您最终达到某个值时,您将获得一个表示log(n)跳过的查询,并将序列中的每个项目与值log(n)次进行比较.

在你的第二个实现你不是在传递查询到quicksort,你正在评估这些查询自己的价值观和传递的价值观来运作,然后可以使用这些值的两倍,而不是多次连续执行一个极其复杂的查询.