LINQ en SortedList

Question

Soy un novato LINQ completo, así que no sé si mi LINQ no es correcto para lo que tengo que hacer o si mis expectativas de rendimiento son demasiado altos.

Tengo un SortedList de objetos, cerrado por int; SortedList en contraposición a SortedDictionary porque estaré pueblan la colección con los datos pre-ordenados. Mi tarea es encontrar la tecla exacta o, si no hay ninguna clave exacta, la que tiene el siguiente valor más alto. Si la búsqueda es demasiado alto para la lista (por ejemplo tecla más alta es de 100, pero la búsqueda de 105), el retorno nulo.

// The structure of this class is unimportant.  Just using
// it as an illustration.
public class CX
{
    public int KEY;
    public DateTime DT;
}

static CX getItem(int i, SortedList<int, CX> list)
{
    var items =
    (from kv in list
     where kv.Key >= i
     select kv.Key);

    if (items.Any())
    {
        return list[items.Min()];
    }

    return null;
}

Dada una lista de 50.000 registros, llamando getItem 500 veces tarda aproximadamente un segundo y medio. Llamándolo 50.000 veces toma más de 2 minutos. Esta actuación parece muy pobre. LINQ es mi mal? Estoy esperando demasiado? Debería estar rodando mi propia función de búsqueda binaria?

Answer 1

Escribir una búsqueda binaria por su cuenta puede ser duro.

Afortunadamente, Microsoft ya escribió una muy robusta uno: Array.BinarySearch<T>. Esta es, de hecho, el método que utiliza internamente SortedList<TKey, TValue>.IndexOfKey . El único problema es que se necesita un argumento T[], en lugar de cualquier IList<T> (como SortedList<TKey, TValue>.Keys).

Usted sabe lo que, sin embargo? Hay esta gran herramienta llamada Reflector que le permite mirar el código fuente .NET .. .

Hay que ver:. BinarySearch un método de extensión genérica sobre IList<T>, tomada directamente desde el código reflejado de aplicación Array.BinarySearch<T> de Microsoft

public static int BinarySearch<T>(this IList<T> list, int index, int length, T value, IComparer<T> comparer) {
    if (list == null)
        throw new ArgumentNullException("list");
    else if (index < 0 || length < 0)
        throw new ArgumentOutOfRangeException((index < 0) ? "index" : "length");
    else if (list.Count - index < length)
        throw new ArgumentException();

    int lower = index;
    int upper = (index + length) - 1;

    while (lower <= upper) {
        int adjustedIndex = lower + ((upper - lower) >> 1);
        int comparison = comparer.Compare(list[adjustedIndex], value);
        if (comparison == 0)
            return adjustedIndex;
        else if (comparison < 0)
            lower = adjustedIndex + 1;
        else
            upper = adjustedIndex - 1;
    }

    return ~lower;
}

public static int BinarySearch<T>(this IList<T> list, T value, IComparer<T> comparer) {
    return list.BinarySearch(0, list.Count, value, comparer);
}

public static int BinarySearch<T>(this IList<T> list, T value) where T : IComparable<T> {
    return list.BinarySearch(value, Comparer<T>.Default);
}

Esto le permitirá llamar list.Keys.BinarySearch y obtener el complemento bit a bit negativo del índice que desea en caso de que la tecla deseada no se encuentra (el siguiente es tomado básicamente recta de la respuesta de tzaman):

int index = list.Keys.BinarySearch(i);
if (index < 0)
    index = ~index;
var item = index < list.Count ? list[list.Keys[index]] : null;
return item;

Answer 2

En primer lugar, la consulta está siendo evaluado dos veces (una vez para Any, y una vez para Min). En segundo lugar, Min requiere que iterar sobre toda la lista, a pesar de que el hecho de que se trata de medios clasificadas que el primer elemento será el mínimo. Usted debe ser capaz de cambiar esta situación:

if (items.Any())
{
    return list[items.Min()];
}

A esto:

var default = 
    (from kv in list
     where kv.Key >= i
     select (int?)kv.Key).FirstOrDefault();

if(default != null) return list[default.Value];

return null;

Actualizar

Debido a que usted está seleccionando un tipo de valor, FirstOrDefault no devuelve un objeto anulable. He alterado su consulta a emitir el valor seleccionado a un int? lugar, permitiendo que el valor resultante a ser revisado para null. Yo estaría a favor de esto sobre el uso de ContainsKey, ya que sería volver true si la lista contiene un valor para 0. Por ejemplo, supongamos que tiene los siguientes valores

0 2 4 6 8

Si se va a pasar nada menos que o igual a 8, entonces se podrían obtener el valor correcto. Sin embargo, si tuviera que pasar en 9, se llega a 0 (default(int)), que es en la lista, pero no un resultado válido.

Answer 3

El uso de LINQ en un SortedList no le dará el beneficio de la especie.

Para un rendimiento óptimo, debe escribir su propia búsqueda binaria.

Answer 4

OK, sólo para dar a esto un poco más la visibilidad - aquí está una versión más concisa de la respuesta de Adam Robinson:

return list.FirstOrDefault(kv => kv.Key >= i).Value; 

La función FirstOrDefault tiene una sobrecarga que acepta un predicado, que selecciona el primer elemento que satisface una condición - que puede utilizar para obtener directamente el elemento que desee o null si no existe.

Answer 5

¿Por qué no usar el BinarySearch que se construye en la clase List?

var keys = list.Keys.ToList();
int index = keys.BinarySearch(i);
if (index < 0)
    index = ~index;
var item = index < keys.Count ? list[keys[index]] : null;
return item;

Si el destino de búsqueda no está en la lista, BinarySearch devuelve el complemento bit a bit del elemento inmediatamente superior; podemos utilizar eso para conseguir directamente lo que quiere mediante la re-complementando el resultado si es negativo. Si llega a ser igual a la Count, su clave de búsqueda era más grande que cualquier otra cosa en la lista.

Esto debería ser mucho más rápido que haciendo un where LINQ, puesto que ya está clasificada ... A medida que los comentarios han señalado, la llamada ToList obligará a una evaluación de toda la lista, así que esto es sólo es beneficioso si lo haces múltiples búsquedas sin alterar el SortedList subyacente, y te guarde la lista keys alrededor separado.

Answer 6

El uso de OrderedDictionary en PowerCollections puede obtener un enumerador que se inicia en el que se están buscando claves tiene que ser ... si no está ahí, obtendrá el siguiente nodo más cercano y puede entonces navegar hacia adelante / atrás de la de O (log N) tiempo por llamada nav.

Esto tiene la ventaja de no tener que escribir su propia búsqueda o incluso gestionar sus propias búsquedas en la parte superior de un SortedList.