OrderBy e Top in LINQ con buone prestazioni

Question

cosa è un buon modo per ottenere i primi 10 record da una collezione molto grande e utilizzare un costume OrderBy? Se utilizzo il metodo LINQ to Objects OrderBy, è lento e richiede molta memoria perché crea un'intera nuova raccolta con il nuovo ordine. Vorrei un nuovo metodo con la firma in basso che non riordinare l'intera collezione ed è molto veloce:

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

ho cercato di scriverlo, ma ha ottenuto molto complicato e ho pensato che ci potrebbe essere un modo più facile usando Aggregate o qualcosa del genere. Qualsiasi aiuto sarebbe apprezzato.

risposta

Grazie per l'aiuto. Ho finito con il codice qui sotto:

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

Il metodo List Extension SortedInsert segue:

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

Per chi fosse interessato ho anche avuto modo keySelector estensione di convertirsi 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 è un buon punto di partenza con:

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

Se si desidera un operatore di confronto diverso, è possibile specificare uno nel costruttore della SortedList.

MODIFICA Come accennato da Nikki, SortedList non può contenere valori doppi. È possibile utilizzare un elenco standard con BinarySearch per ottenere lo stesso effetto:

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

Anche in questo caso un operatore di confronto personalizzato (insieme ad una selezione chiave personalizzato) può essere utilizzato come parametro per BinarySearch.

Answer 2

Penso che quello che vuoi sia davvero un selection algorithm. Non so che LINQ sia il modo migliore per implementare uno poiché penso che fondamentalmente finisca come selezione tramite l'ordinamento. Dovresti essere in grado di farlo in O (kN), dove k è il numero di "top" di elementi scorrendo la raccolta, tenendo traccia del minimo elemento di "top" visto finora e se l'elemento corrente è più grande di che, sostituendo quell'elemento con l'elemento corrente (e aggiornando il nuovo elemento minimo). Anche questo è efficiente nello spazio.

Al termine è possibile restituire gli elementi "top" come un insieme ordinato.

Nota: Sto assumendo LINQ per gli oggetti qui. Se si utilizza LINQ to SQL, quindi mi rimetto semplicemente rinviare l'ordinamento/selezione al server SQL e semplicemente catena metodi in modo appropriato per ottenere una query select top N ... from ... order by ....

Completamente testato, nemmeno compilato. Utilizza un'implementazione generica di heap di Fibonacci. Pubblicherò il codice sul mio blog (http://farm-fresh-code.blogspot.com) a breve. Ne ho uno in giro (non so se è generico) come risultato di alcuni esperimenti con code di priorità che stavo facendo. Vedere wikipedia per informazioni e pseudocodice fino ad allora.

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

Non conosco un'altra soluzione rispetto alla scrittura di questo metodo. Tuttavia questo metodo non dovrebbe essere così complicato.

è necessario mantenere un elenco ordinato con i primi 10 elementi, e scorrere l'insieme orinigal una volta.

Se il record corrente durante l'iterazione è inferiore a quello dell'ultimo elenco 10 o quando non si hanno ancora i primi 10 record, è necessario aggiungere l'elemento a questo elenco. (E, naturalmente, rimuovere l'ultimo elemento dalla lista dei primi 10, quando appropriato.)

Answer 4

Si potrebbe anche implementare un algoritmo di ordinamento divide e conquista come quicksort e interrompere non appena si hanno i primi k elementi ordinati. Ma il suggerimento di tvanfosson è probabilmente più veloce se k < < N