OrderBy and Top w LINQ z dobrą wydajnością

Question

Jaki jest dobry sposób na zdobycie 10 najlepszych rekordów z bardzo dużej kolekcji i skorzystanie z niestandardowej opcji OrderBy? Jeśli używam metody LINQ do Objects OrderBy, jest ona wolna i zajmuje dużo pamięci, ponieważ tworzy nową kolekcję z nowym zamówieniem. Chciałbym nową metodę z podpisu poniżej, że nie zmienić kolejność całą kolekcję i jest bardzo szybki:

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

próbowałem go napisać, ale to się bardzo skomplikowane i pomyślałem, że może być dowolny łatwiejszy sposób używając Aggregate lub czegoś takiego. Każda pomoc będzie doceniona.

Odpowiedź

Dzięki za pomoc. Skończyło się z poniższym kodzie:

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

Sposób Lista Extension SortedInsert następująco:

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

dla zainteresowanych miałem również metodę keySelector Extension przekonwertować do 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)); 
    } 
} 

Answer 1

Aggregate jest dobrym miejscem, aby rozpocząć:

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

Jeśli chcesz inny porównywarka można określić jeden w konstruktorze SortedList.

EDIT Jak wspomniano przez nikie, SortedList nie może zawierać podwójnych wartości. Można użyć standardowej listy wraz z BinarySearch aby osiągnąć ten sam efekt:

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

kolejny niestandardowy comparer (wraz z niestandardowy klucz doboru) może być używany jako parametr do BinarySearch.

Answer 2

myślę, co chcesz, to naprawdę selection algorithm. Nie wiem, że LINQ to najlepszy sposób na jego implementację, ponieważ wydaje mi się, że w zasadzie jest to sortowanie przez sortowanie. Powinieneś być w stanie to zrobić w O (kN), gdzie k jest "najwyższą" liczbą elementów poprzez iterowanie przez kolekcję, śledzenie minimalnego "górnego" elementu widocznego do tej pory i jeśli bieżący element jest większy niż to, zastępując ten element bieżącym elementem (i aktualizując nowy minimalny element). Jest to również oszczędność miejsca.

Po zakończeniu można przywrócić "najlepsze" elementy jako uporządkowaną kolekcję.

Uwaga: Zakładam LINQ do obiektów tutaj. Jeśli używasz LINQ do SQL, to odłożę po prostu odłożenie zamówienia/selekcji na serwer SQL i po prostu łańcuch metod odpowiednio, aby uzyskać zapytanie select top N ... from ... order by ....

Całkowicie nietestowana, nawet nie skompilowana. Używa ogólnej implementacji sterty Fibonacciego. Wkrótce opublikuję kod na moim blogu (http://farm-fresh-code.blogspot.com). Mam jednego, który się kręci (nie jestem pewien, czy to generyczny) w wyniku eksperymentów z priorytetowymi kolejkami, które robiłem. Zobacz wikipedia dla informacji i pseudokod do tego czasu.

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

Answer 3

Nie znam innego rozwiązania niż pisanie tej metody. Jednak ta metoda nie powinna być tak skomplikowana.

Musisz zachować posortowaną listę z 10 pierwszymi elementami i raz iterować przez kolekcję orinigalną.

Jeśli aktualny rekord podczas iteracji jest mniejszy niż ostatni z listy 10 najlepszych lub jeśli nie masz jeszcze 10 pierwszych rekordów, musisz dodać pozycję do tej listy. (I oczywiście, usuń ostatni element z listy 10 najlepszych, jeśli to konieczne.)

Answer 4

Można również zaimplementować algorytm sortowania typu dziel i rządź jak quicksort i przerwać, gdy tylko pojawią się pierwsze k posortowane elementy. Ale sugestia tvanfosson jest prawdopodobnie szybsza, jeśli k < < N