LINQ中的OrderBy和Top具有良好的性能 [英] OrderBy and Top in LINQ with good performance

问题描述

从大型馆藏中获取前10条记录并使用自定义OrderBy的好方法是什么?如果我使用LINQ to Objects OrderBy方法，它会很慢并且会占用大量内存，因为它会使用新订单创建一个完整的新集合.我想要一种带有以下签名的新方法，该方法不会重新排序整个集合，而且速度非常快:

What is a good way to get the top 10 records from a very large collection and use a custom OrderBy? If I use the LINQ to Objects OrderBy method it is slow and takes a lot of memory because it creates an entire new collection with the new order. I would like a new method with the signature below that does not re-order the entire collection and is very fast:

public static IEnumerable<TSource> OrderByTop<TSource, TKey>(
    IEnumerable<TSource> source,
    Func<TSource, TKey> keySelector,
    IComparer<TKey> comparer,
    int topCount)

我尝试编写它，但是它变得非常复杂，我认为使用Aggregate或其他方法可能会更简单.任何帮助将不胜感激.

I tried to write it but it got very complicated and I thought there might be any easier way using Aggregate or something. Any help would be appreciated.

答案

感谢您的帮助.我结束了下面的代码:

Thanks for the help. I ended up with the code below:

public static List<TSource> OrderByTop<TSource, TKey>(
    this IEnumerable<TSource> source,
    Func<TSource, TKey> keySelector,
    IComparer<TKey> comparer,
    int topCount)
{
    var itemComparer = keySelector.ToIComparer(comparer);
    return source.Aggregate(
        new List<TSource>(topCount),
        (List<TSource> list, TSource item) =>
            list.SortedInsert(item, itemComparer, topCount));
}

列表扩展方法SortedInsert如下:

The List Extension method SortedInsert follows:

public static List<T> SortedInsert<T>(
    this List<T> list,
    T item,
    IComparer<T> comparer,
    int maxLength)
{
    if (list.Count == maxLength)
        if (comparer.Compare(item, list[maxLength - 1]) >= 0)
            return list;
        else
            list.RemoveAt(maxLength - 1);
    int insertIndex = list.BinarySearch(item, comparer);
    if (insertIndex < 0)
        insertIndex = ~insertIndex;
    list.Insert(insertIndex, item);
    return list;
}

对于那些感兴趣的人，我也有keySelector扩展方法可以转换为IComparer.

For those interested I also had keySelector Extension method to convert to IComparer.

public static IComparer<TSource> ToIComparer<TSource, TKey>(
    this Func<TSource, TKey> keySelector,
    IComparer<TKey> comparer)
{
    return new KeySelectorToIComparerConverter<TSource, TKey>(
        keySelector,
        comparer);
}
private class KeySelectorToIComparerConverter<TSource, TKey>
    : IComparer<TSource>
{
    private readonly IComparer<TKey> comparer;
    private readonly Func<TSource, TKey> keySelector;
    public KeySelectorToIComparerConverter(
        Func<TSource, TKey> keySelector,
        IComparer<TKey> comparer)
    {
        this.comparer = comparer;
        this.keySelector = keySelector;
    }
    public int Compare(TSource x, TSource y)
    {
        return comparer.Compare(keySelector(x), keySelector(y));
    }
}

推荐答案

Aggregate是一个很好的起点:

SortedList<TKey, TSource> resultlist = new SortedList<TKey, TSource>();
MyBigList.Aggregate(resultlist, (aktlist,entry) => {
   aktlist.Add(entry.Key, entry);
   if (aktlist.Count > 10) aktlist.RemoveAt(10);
   return aktlist;
});

如果要使用其他比较器，则可以在SortedList的构造函数中指定一个.

If you want a different comparer, you can specify one in the constructor of the SortedList.

编辑如nikie所述，SortedList不能包含双精度值.您可以将标准列表与BinarySearch一起使用以达到相同的效果:

EDIT As mentioned by nikie, SortedListcannot contain double values. You can use a standard list together with BinarySearch to achieve the same effect:

List<TSource> resultlist = new List<TSource>();
MyBigList.Aggregate(resultlist, (aktlist, entry) => {
   int index = aktlist.BinarySearch(entry);
   if (index < 0) index = ~index;
   if (index < 10) aktlist.Insert(index, entry);
   if (aktlist.Count > 10) aktlist.RemoveAt(10);
   return aktlist;
});

再次使用自定义比较器(以及自定义键选择)作为BinarySearch的参数.

Again a custom comparer (together with a custom key selection) can be used as parameter to BinarySearch.

这篇关于LINQ中的OrderBy和Top具有良好的性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！