OrderBy y Top in LINQ con buen rendimiento

Question

¿Cuál es una buena forma de obtener los 10 registros principales de una colección muy grande y utilizar un pedido personalizado? Si utilizo el método LINQ to Objects OrderBy, es lento y requiere mucha memoria porque crea una nueva colección completa con el nuevo pedido. Me gustaría tener un nuevo método con la firma abajo que no volver a ordenar toda la colección y es muy rápido:

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

Traté de escribir, pero se puso muy complicado y pensé que podría haber alguna manera más fácil usando Agregado o algo. Cualquier ayuda sería apreciada.

respuesta

Gracias por la ayuda. Terminé con el código de abajo:

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

El método de la lista Extensión SortedInsert sigue:

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

Para aquellos interesados ​​También tuve método keySelector extensión para convertir a 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 es un buen lugar para comenzar 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; 
}); 

Si desea un comparador diferente, puede especificar uno en el constructor de la SortedList.

EDIT Según lo mencionado por nikie, SortedList no puede contener valores dobles. Puede utilizar una lista estándar junto con BinarySearch para lograr el mismo efecto:

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

Una vez más un comparador personalizado (junto con una selección de claves personalizado) puede ser utilizado como parámetro para BinarySearch.

Answer 2

Creo que lo que quiere es realmente un selection algorithm. No sé si LINQ es la mejor manera de implementar uno, ya que creo que básicamente termina como selección por clasificación. Debería poder hacer esto en O (kN), donde k es el número "superior" de elementos al recorrer la colección, hacer un seguimiento del elemento "superior" mínimo visto hasta el momento y si el elemento actual es más grande que eso, reemplazando ese elemento con el elemento actual (y actualizando el nuevo elemento mínimo). Esto también es eficiente en el uso del espacio.

Cuando haya terminado, puede devolver los elementos "superiores" como una colección ordenada.

Nota: Asumo LINQ to Objects aquí. Si está utilizando LINQ to SQL, entonces diferiría simplemente aplazar el pedido/selección al servidor SQL y simplemente encadenar los métodos de manera apropiada para obtener una consulta select top N ... from ... order by ....

Completamente no probado, ni siquiera compilado. Utiliza una implementación genérica de Fibonacci Heap. Voy a publicar el código en mi blog (http://farm-fresh-code.blogspot.com) pronto. Tengo uno dando vueltas (no estoy seguro si es genérico) como resultado de algunos experimentos con colas de prioridad que estaba haciendo. Consulte wikipedia para obtener información y pseudocódigo hasta entonces.

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

No conozco otra solución que escribir este método. Sin embargo, este método no debería ser tan complicado.

Debe mantener una lista ordenada con los 10 elementos principales y recorrer la colección orinigal una vez.

Si el registro actual durante la iteración es más pequeño que el último de la lista de los 10 primeros, o si aún no tiene sus primeros 10 registros, debe agregar el elemento a esta lista. (Y, por supuesto, elimine el último elemento de la lista de los 10 principales, cuando corresponda).)

Answer 4

También podría implementar un algoritmo de clasificación de dividir y vencer como quicksort y romper tan pronto como tenga los primeros k elementos clasificados. Pero la sugerencia de tvanfosson es probablemente más rápida si k < < N