OrderBy и Top в LINQ с хорошей производительностью - PullRequest
Новая
       44

OrderBy и Top в LINQ с хорошей производительностью

12 голосов
/ 16 января 2010

Какой хороший способ получить 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)

Я пытался написать это, но это стало очень сложным, и я подумал, что может быть более простой способ использовать Aggregate или что-то в этом роде. Любая помощь будет оценена.

Ответ

Спасибо за помощь. Я закончил с кодом ниже: 

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 следует: 

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 Extension для преобразования в 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 ]

8 голосов
/ 16 января 2010

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.

РЕДАКТИРОВАТЬ Как упоминалось nikie, 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;
});

Опять-таки, в качестве параметра для BinarySearch может использоваться пользовательский компаратор (вместе с выбором пользовательской клавиши).

3 голосов
/ 16 января 2010

Я думаю, что вы действительно хотите алгоритм выбора . Я не знаю, что LINQ - лучший способ реализовать его, так как я думаю, что он в основном заканчивается сортировкой. Вы должны быть в состоянии сделать это в O (kN), где k - это «верхнее» количество элементов, перебирая коллекцию, отслеживая минимальный «верхний» элемент, видимый до сих пор, и если текущий элемент больше чем что, заменяя этот элемент текущим элементом (и обновляя новый минимальный элемент). Это также экономит место.

Когда вы закончите, вы можете вернуть "верхние" элементы в виде упорядоченной коллекции.

Примечание : Я предполагаю, что LINQ to Objects здесь. Если вы используете LINQ to SQL, то я бы просто отложил упорядочение / выбор до SQL-сервера и просто связал методы соответствующим образом, чтобы получить запрос select top N ... from ... order by ....

Полностью не проверено, даже не скомпилировано. Использует универсальную реализацию кучи Фибоначчи. Я опубликую код в своем блоге (http://farm -fresh-code.blogspot.com ) в ближайшее время. У меня есть один зависший (не уверен, что он общий) результат некоторых экспериментов с приоритетными очередями, которые я проводил. См. Википедия для информации и псевдокод до тех пор. 

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)   
}
2 голосов
/ 16 января 2010

Я не знаю другого решения, кроме написания этого метода. Однако этот метод не должен быть таким сложным.

Вам нужно сохранить отсортированный список с 10 верхними элементами и выполнить итерацию по оригинальной коллекции один раз.

Если текущая запись во время итерации меньше, чем последняя из списка 10 лучших, или если у вас еще нет первых 10 записей, необходимо добавить элемент в этот список. (И, конечно, при необходимости удалите последний элемент из списка 10 лучших).

1 голос
/ 16 января 2010

Вы также можете реализовать алгоритм сортировки «разделяй и властвуй», такой как быстрая сортировка и разбиение, как только вы получите первые k отсортированных элементов. Но предложение tvanfosson, вероятно, быстрее, если k << N </p>

...