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

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

Например:

// 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, но пока ничего не понял. Возможно, я что-то делаю неправильно.

Ответы

Ответ 1

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

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

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

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

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

Ответ 2

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

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

Ответ 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];

Ответ 4

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

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

Ответ 5

Я бы сделал небольшой класс 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() или реализовать какой-то откат, если какое-либо значение уже находится в словаре.

Ответ 6

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

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

Ответ 7

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

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