c# - values - Un objeto de diccionario que usa rangos de valores para claves

keyvaluepair

Question

Necesito una especie de diccionario especializado. Mi caso de uso es este: el usuario quiere especificar rangos de valores (el rango también podría ser un punto) y asignar un valor a un rango particular. Luego queremos realizar una búsqueda utilizando un solo valor como clave. Si este valor único ocurre dentro de uno de los rangos, entonces devolveremos el valor asociado al rango.

Por ejemplo:

// represents the keyed value
struct Interval
{
    public int Min;
    public int Max;
}

// some code elsewhere in the program
var dictionary = new Dictionary<Interval, double>();
dictionary.Add(new Interval { Min = 0, Max = 10 }, 9.0);
var result = dictionary[1];
if (result == 9.0) JumpForJoy();

Esto es obviamente solo un código para ilustrar lo que estoy buscando. ¿Alguien sabe de un algoritmo para implementar tal cosa? Si es así, ¿podrían señalarme hacia él, por favor?

Ya he intentado implementar un objeto IEqualityComparer personalizado y sobrecargar Equals () y GetHashCode () en Intervalo, pero en vano hasta ahora. Sin embargo, es posible que yo esté haciendo algo mal.

Answer 1

Esto solo va a funcionar cuando los intervalos no se superponen. Y su problema principal parece ser la conversión de un único valor (clave) a un intervalo.

Escribiría un borrador sobre SortedList. SortedList.Keys.IndexOf () encontraría un índice que se puede usar para verificar si el intervalo es válido y luego usarlo.

Answer 2

Haría una pequeña clase de Interval, que sería algo como eso:

public class Interval
{
    public int Start {get; set;}
    public int End {get; set;}
    public int Step {get; set;}
    public double Value {get; set;}

    public WriteToDictionary(Dictionary<int, double> dict)
    {
        for(int i = Start; i < End; i += Step)
        {
            dict.Add(i, Value);
        }
    }
}

De modo que aún puede realizar una búsqueda normal dentro de su diccionario. Quizás también deba realizar algunas comprobaciones antes de llamar a Add() o implementar algún tipo de reversión si algún valor ya está dentro del diccionario.

Answer 3

He resuelto un problema similar al asegurar que la colección es contigua donde los intervalos nunca se superponen y nunca tienen espacios entre ellos. Cada intervalo se define como un límite inferior y cualquier valor se encuentra en ese intervalo si es igual o mayor que ese límite y menor que el límite inferior del siguiente intervalo. Cualquier cosa debajo del límite más bajo es un contenedor de casos especiales.

Esto simplifica un poco el problema. También optimizamos las búsquedas de claves implementando un corte binario. No puedo compartir el código, desafortunadamente.

Answer 4

Puedes ver las colecciones de poder que se encuentran en Codeplex y que tienen una colección que puede hacer lo que estás buscando.

Espero que esto ayude, Saludos, Tom.

Answer 5

Un diccionario no es la estructura de datos adecuada para las operaciones que está describiendo.

Si los intervalos son necesarios para que nunca se superpongan, puede crear una lista ordenada de intervalos y buscarlos binariamente.

Si los intervalos pueden superponerse, entonces tiene un problema más difícil de resolver. Para resolver ese problema de manera eficiente, querrá construir un árbol de intervalos:

http://en.wikipedia.org/wiki/Interval_tree

Esta es una estructura de datos conocida. Consulte "Introducción a los algoritmos" o cualquier otro texto decente de pregrado en estructuras de datos.

Answer 6

Esto no es exactamente lo que quieres, pero creo que puede ser lo más cercano que puedas esperar.

Por supuesto, puede hacerlo mejor que esto (¿Estaba bebiendo antes?). Pero debes admitir que es bueno y simple.

var map = new Dictionary<Func<double, bool>, double>()
{
    { d => d >= 0.0 && d <= 10.0, 9.0 }
};

var key = map.Keys.Single(test => test(1.0))
var value = map[key];

Answer 7

Puede encontrar una implementación C # con sabor a Java de un árbol de intervalos en la Biblioteca geoespacial abierta . Necesita algunos ajustes menores para resolver su problema y también podría usar algo de C # -ificación.

Es de código abierto pero no sé bajo qué licencia.