Объект словаря, который использует диапазоны значений для ключей
У меня есть потребность вида специализированного словаря. Мой вариант использования - это: пользователь хочет определить диапазоны значений (диапазон мог быть единственной точкой также), и присвойте значение конкретному диапазону. Мы тогда хотим выполнить поиск с помощью единственного значения в качестве ключа. Если это единственное значение произойдет в одном из диапазонов тогда, то мы возвратим значение, связанное с диапазоном.
Например:
// 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 и перегрузиться, Равняется () и GetHashCode () на Интервале, но напрасно до сих пор. Может случиться так, что я делаю что-то не так все же.
7 ответов
Словарь не является соответствующей структурой данных для операций, которые вы описываете.
Если интервалы необходимы для никогда не перекрываются, вы можете просто построить отсортированный список интервалов и бинарный поиск.
Если интервалы могут перекрываться, то у вас есть более сложная проблема для решения. Чтобы решить эту проблему эффективно, вы захотите построить интервал дерева:
http://en.wikipedia.org/wiki/interval_tree
Это хорошо известная структура данных. См. «Введение в алгоритмы» или любое другое достойное основание для студентов в структурах данных.
Это только для работы, когда интервалы не перекрываются. И ваша главная проблема, кажется, преобразует из одного (ключа) значения на интервал.
Я бы написал обертку вокруг сортиста. SORTEDLIST.KEYS.INDEXOF () найдет вам индекс, который можно использовать для проверки, если интервал действителен, а затем используйте его.
Я бы сделал немного интервального класса, который бы что-то подобное:
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 () или реализуйте какой-то откат, если какое-либо значение уже в словаре.
Это не совсем то, что вы хотите, но я думаю, что это может быть ближе всего, что вы можете ожидать.
Вы можете конечно делать лучше, чем это (я пью раньше?). Но вы должны признать, что это приятно и просто.
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];
Вы можете ознакомиться с расстройствами PowerCollions, которые были найдены в CodePlex , в котором есть коллекция, которая может сделать то, что вы ищете.
Надеюсь, это поможет, С уважением, Том.
Вы можете найти ароматизацию Java C # интервального дерева в открытой геопространственной библиотеки . Для решения вашей проблемы нужны незначительные настройки, и она также может действительно использовать некоторые C #
Это открытый источник, но я не знаю, по какой лицензии.
Знакомы ли вы с ошибкой exec в двойных кавычках? (для Runtime.exec или ProcessBuilder )
Можно попытаться:
Runtime.getRuntime().exec(new String[] {
"\"C:/Program Files/MySQL/MySQL Server 5.0/bin/mysqldump\"",
"-h",
hostName+user+databaseName});
Просто убедитесь, что ни один из параметров не содержит двойных кавычек (в то время как не , начинающихся с двойных кавычек)
(см. ошибка 6511002 )
Любой параметр, например:
mykey="my value with space"
будет изменен внутренне (с помощью реализации getRuntime () ) на
"mykey="myvalue with space""
. Если это так, необходимо маркировать аргумент:
{"mykey=\"my\"" , "\"value with space\""}
Если программа зависит от System.gc (), следует либо переосмыслить дизайн, либо перейти на другой язык программирования.
Сбор мусора может быть реализован по-разному на каждой виртуальной машине, и только солнечная виртуальная машина поставляется с несколькими различными реализациями.
Было бы интересно узнать, каким образом ваша программа полагается на System.gc (). Если это для финализаторов, они приходят со своими проблемами и должны использоваться только для помощи в отладке.
-121--4548548-Я решил аналогичную проблему, обеспечив непрерывность сбора, когда интервалы никогда не перекрываются и никогда не имеют зазоров между ними. Каждый интервал определяется как нижняя граница, и любое значение лежит в этом интервале, если оно равно или больше этой границы и меньше нижней границы следующего интервала. Все, что находится ниже самой нижней границы, является ячейкой особого случая.
Это несколько упрощает проблему. Мы также затем оптимизировали поиск ключа путем реализации двоичного выделения. Я не могу поделиться кодом, к сожалению.