En C#, ¿hay algún tipo de SortedList <double> que permita consultas rápidas (con LINQ) para el valor más cercano?

Question

Estoy buscando una estructura que contenga un conjunto ordenado de valores dobles. Deseo consultar este conjunto para encontrar el valor más cercano a un valor de referencia específico.

He consultado el SortedList<double, double>, y me ha ido bastante bien. Sin embargo, dado que no necesito pares clave/valor explícitos. esto parece ser excesivo para mí, y me pregunto si podría hacerlo más rápido.

Condiciones:

• La estructura se inicializa sólo una vez, y que nunca cambian (sin inserto/eliminaciones)
• La cantidad de valores es en el rango de 100K.
• La estructura se consulta a menudo con nuevas referencias, que deben ejecutar rápido.
• Por simplicidad y velocidad, el valor del conjunto justo por debajo de la referencia se puede devolver, no en realidad el valor más cercano
• Quiero usar LINQ para la consulta, si es posible, por simplicidad de código.
• No quiero utilizar código de terceros si es posible. .NET 3.5 está disponible.
• velocidad es más importand de huella de memoria

Actualmente utilizo el siguiente código, donde SortedValues es el ya mencionado SortedList

IEnumerable<double> nearest = from item in SortedValues.Keys 
            where item <= suggestion 
            select item; 
    return nearest.ElementAt(nearest.Count() - 1); 

¿Puedo hacer más rápido?

Además, no estoy 100% seguro, si este código es realmente seguro. IEnumerable, el tipo de devolución de mi consulta ya no está ordenada por definición. Sin embargo, una prueba de Unidad con una gran base de datos de prueba ha demostrado que es en la práctica, por lo que esto funciona para mí. ¿Tiene pistas sobre este aspecto?

P.S. Sé que hay muchas preguntas similares, pero ninguna realmente responde a mis necesidades específicas. Especialmente está este C# Data Structure Like Dictionary But Without A Value, pero el interlocutor solo quiere verificar la existencia y no encontrar nada.

Answer 1

La forma en que lo hace es increíblemente lento, ya que debe buscar desde el principio de la lista cada vez que ofrece un rendimiento O (n).

Una mejor manera es poner los elementos en una lista y luego sort en la lista. Usted dice que no necesita cambiar los contenidos una vez inicializados, por lo que ordenarlos una vez es suficiente.

Luego puede usar List<T>.BinarySearch para encontrar elementos o para encontrar el punto de inserción de un elemento si no existe en la lista.

A partir de los documentos:

Valor de retorno

El índice basado en cero del elemento en el List<T> ordenados, si el artículo se encuentra; de lo contrario, un número negativo que es el complemento bit a bit del índice del siguiente elemento que es más grande que el elemento o, si no hay un elemento más grande, el complemento en bits de Count.

Una vez que tenga el punto de inserción, debe verificar los elementos de cada lado para ver cuál está más cerca.

Answer 2

Puede que no te sea útil en este momento, pero .Net 4 tiene una clase SortedSet en el BCL.

Answer 3

creo que puede ser más elegante de la siguiente manera: En caso de que los artículos no están ordenados:

double nearest = values.OrderBy(x => x.Key).Last(x => x.Key <= requestedValue); 

En caso de que se ordenan los elementos, es posible omitir la llamada OrdenarPor ...