Объект словаря, который использует диапазоны значений для ключей

Question

Мне нужен своего рода специализированный словарь. Мой пример использования таков: пользователь хочет указать диапазоны значений (диапазон также может быть отдельной точкой) и назначить значение определенному диапазону. Затем мы хотим выполнить поиск, используя одно значение в качестве ключа. Если это единственное значение встречается в одном из диапазонов, мы вернем значение, связанное с диапазоном.

Например:

// 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();

Это, очевидно, просто некоторый код для иллюстрации того, что я ищу. Кто-нибудь знает алгоритм для реализации такой вещи? Если так, то могут ли они указать мне на это, пожалуйста?

Я уже пытался реализовать пользовательский объект IEqualityComparer и перегрузить Equals () и GetHashCode () на Interval, но пока безрезультатно. Возможно, я что-то не так делаю.

Answer 1

Словарь не соответствует структуре данных для описываемых вами операций.

Если интервалы требуются, чтобы никогда не перекрываться, то вы можете просто создать отсортированный список интервалов и выполнить его двоичный поиск.

Если интервалы могут перекрываться, вам придется решать более сложную задачу. Чтобы эффективно решить эту проблему, вам нужно построить дерево интервалов:

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

Это хорошо известная структура данных. См. «Введение в алгоритмы» или любой другой достойный текст студентов о структурах данных.

Answer 2

Это будет работать только тогда, когда интервалы не перекрываются. И ваша основная проблема, кажется, заключается в преобразовании одного (ключевого) значения в интервал.

Я бы написал обертку вокруг SortedList. SortedList.Keys.IndexOf () найдет вам индекс, который можно использовать для проверки правильности интервала, а затем использовать его.

Answer 3

Это не совсем то, что вы хотите, но я думаю, что это может быть ближе всего вы можете ожидать.

Вы, конечно, можете сделать лучше, чем это (я пил раньше?). Но ты должен признать, что это красиво и просто.

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 4

Я решил похожую проблему, убедившись, что коллекция является смежной, где интервалы никогда не перекрываются и никогда не имеют промежутков между ними. Каждый интервал определяется как нижняя граница, и любое значение лежит в этом интервале, если оно равно или превышает эту границу и меньше, чем нижняя граница следующего интервала. Все, что ниже нижней границы, является специальным случаем.

Это несколько упрощает проблему. Затем мы также оптимизировали поиск по ключевым словам, внедрив двоичную отбивку. К сожалению, я не могу поделиться кодом.

Answer 5

В Открытой геопространственной библиотеке можно найти реализацию C # дерева интервалов со вкусом Java. Для решения вашей проблемы требуются незначительные изменения, а также может действительно использоваться некоторая C # -дификация.

Это с открытым исходным кодом, но я не знаю, по какой лицензии.

Answer 6

Я бы сделал небольшой класс Interval, который бы что-то вроде этого:

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

Так что вы все еще можете нормально искать в своем словаре. Возможно, вам также следует выполнить некоторые проверки перед вызовом Add() или реализовать какой-то откат, если какое-либо значение уже есть в словаре.

Answer 7

Вы можете проверить коллекции электропитания, найденные здесь на codeplex , у которого есть коллекция, которая может сделать то, что вы ищете.

Надеюсь, это поможет, С наилучшими пожеланиями, Том.