代码之家 › 专栏 › 技术社区 › DRBlaise

orderby和top-in-linq性能良好

sql-order-by linq-to-objects performance linq c#

DRBlaise · 技术社区 · 16 年前

从一个非常大的集合中获取前10条记录并使用自定义orderby的好方法是什么?如果我使用linq to objects orderby方法,它会很慢,占用大量内存,因为它使用新的顺序创建了一个完整的新集合。我想要一个新方法,下面的签名不会重新订购整个集合,而且速度非常快:

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

我试着写它,但它变得非常复杂,我想可能有任何更容易的方法使用聚合或其他东西。任何帮助都将不胜感激。

回答

谢谢你的帮助。最后我得到了下面的代码:

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));
}

排序插入的列表扩展方法如下:

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。

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));
    }
}

4 回复 | 直到 16 年前

MartinStettner 16 年前

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 .

编辑正如尼基提到的, 有序列表 不能包含双精度值。您可以将标准列表与 BinarySearch 为了达到同样的效果:

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;
});

同样,可以将自定义比较器(与自定义键选择一起)用作 二进制搜索 .

tvanfosson 16 年前

我想你真正想要的是 selection algorithm . 我不知道Linq是实现它的最佳方法,因为我认为它基本上是以排序作为选择的。您应该能够在o(kn)中做到这一点,其中k是通过迭代集合来获得的“top”项目数,跟踪到目前为止看到的最小“top”元素,如果当前元素大于该元素,则将该元素替换为当前元素(并更新新的最小元素)。这也是节省空间的。

完成后,可以将“top”元素作为有序集合返回。

注意 :我假设这里是Linq to对象。如果您使用的是LINQ to SQL,那么我只需将排序/选择延迟到SQL服务器,并简单地将方法适当地链接起来,以获得 select top N ... from ... order by ... 查询。

完全未测试,甚至未编译。使用通用斐波那契堆实现。我会把代码贴在我的博客上( http://farm-fresh-code.blogspot.com )不久的某个时候。由于我对优先级队列做了一些实验,我有一个挂在旁边(不确定它是否是通用的)。参见 wikipedia 获取信息和伪代码。

public static IEnumerable<TSource> OrderByTop<TSource, TKey>(
    IEnumerable<TSource> source,
    Func<TSource, TKey> keySelector,
    IComparer<TKey> comparer,
    int topCount)
{
    // allocate enough space to hold the number of elements (+1 as a new candidate is added)
    FibonacciHeap<TKey,TSource> top = new FibonacciHeap<TKey,TSource>( comparer );
    foreach (var candidate in source) // O(n)
    {
         TKey key = keySelector(candidate);
         TKey minimum = top.AccessMinimum();
         if (minimum == null || comparer.Compare( key, minimum.Key ) > 0) // O(1)
         {
             top.Insert( key, candidate ); // O(1)
             if (top.Count >= topCount)
             {
                 top.DeleteMinimum(); // O(logk)
             }
         }
    }
    return top.ToList().Reverse().Select( t.Value ); // O(k)   
}

treaschf 16 年前

除了写这个方法,我不知道其他的解决方案。然而,这种方法不应该那么复杂。

您需要维护一个带有前10个元素的排序列表,并在原始集合中迭代一次。

如果迭代期间的当前记录小于前10个列表中的最后一个记录,或者当您还没有前10个记录时,则必须将该项添加到此列表中。(当然,如果合适的话,从前10个列表中删除最后一项。)

Niki 16 年前

您还可以实现一个分而治之的排序算法,如Quicksort和Break,只要您有第一个K排序的元素。但如果K<<n,Tvanfosson的建议可能更快。