Структуры данных, C #: ~ O (1) поиск с помощью клавиш диапазона?

Question

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

Набор данных (скажем, его CSV) имеет несколько предостережений. Вместо:

1,ABC
2,XYZ
3,LMN

Числа - это диапазоны (- «через», а не минус):

1-3,ABC     // 1, 2, and 3 = ABC
4-8,XYZ     // 4, 5, 6, 7, 8 = XYZ
11-11,LMN   // 11 = LMN

Все числа подписаны целыми числами. Ни один диапазон не перекрывается другими диапазонами. Есть некоторые пробелы; есть диапазоны, которые не определены в наборе данных (например, 9 и 10 в последнем фрагменте выше). `

Как я могу смоделировать этот набор данных в C #, чтобы у меня был самый производительный поиск, сохраняя при этом низкий объем занимаемой памяти?

Единственный вариант, который я придумал, - это чрезмерное потребление памяти. Допустим, мой набор данных:

1-2,ABC
4-6,XYZ

Затем я создаю Dictionary<int,string>(), ключ / значения которого:

1/ABC
2/ABC
4/XYZ
5/XYZ
6/XYZ

Теперь у меня есть поиск производительности хеш-функции, но в хэш-таблице хранится множество потерянного пространства.

Есть идеи? Может, просто использовать PLINQ и надеяться на хорошую производительность? ;)

Answer 1

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

Лучший вариант - использовать структуру данных, которая поддерживает некоторые варианты бинарного поиска (или другой метод поиска O (log N)). Вот ссылка на общий RangeDictionary для .NET , который использует OrderedList для внутреннего использования и имеет производительность O (log N).

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

Answer 2

Вы можете создать двунаправленный поиск:

Dictionary<int, int> keys;
Dictionary<int, string> values;

Затем сохранить данные следующим образом:

keys.Add(1, 1);
keys.Add(2, 1);
keys.Add(3, 1);
//...
keys.Add(11, 3);

values.Add(1, "ABC");
//...
values.Add(3, "LMN");

И затем просмотреть данные:

return values[keys[3]];  //returns "ABC"

Я не уверен, сколько памяти это сэкономит с помощью тривиальных строк, но как только вы выйдете за пределы "ABC", это должно помочь.

РЕДАКТИРОВАТЬ

После комментария Дана Тао ниже я вернулся и проверил, о чем он спрашивает.Следующий код:

var abc = "ABC";
var def = "ABC";
Console.WriteLine(ReferenceEquals(abc, def));

выведет «True» на консоль.Что означает, что компилятор или среда выполнения (пояснение?) Поддерживают ссылку на «ABC» и присваивают ее в качестве значения обеих переменных.

После прочтения еще некоторых строк Intern edЕсли вы используете строковые литералы для заполнения словаря или Intern вычисляемых строк, на самом деле для реализации моего предложения потребуется больше места, чем для исходного словаря.Если вы не используете Intern ed строк, то мое решение должно занимать меньше места.

FINAL EDIT

Если вы правильно обрабатываете строки, естьне должно быть избыточного использования памяти по сравнению с исходным Dictionary<int, string>, поскольку вы можете назначить их переменной, а затем назначить эту ссылку в качестве значения (или, если вам нужно, потому что вы можете Intern их)

Просто убедитесь, что ваш код назначения содержит промежуточную переменную:

while (thereAreStringsLeftToAssign)
{
    var theString = theStringToAssign;
    foreach (var i in range)
    {
        strings.Add(i, theString);
    }
}

Answer 3

Как отметил arootbeer в своем ответе , следующий код не создает несколько экземпляров строки "ABC"; скорее, он интернирует один экземпляр и назначает ссылку на этот экземпляр каждому KeyValuePair<int, string> в dictionary:

var dictionary = new Dictionary<int, string>();
dictionary[0] = "ABC";
dictionary[1] = "ABC";
dictionary[2] = "ABC";

// etc.

ОК, поэтому в случае строковых литералов вы используете только один экземпляр string на диапазон ключей. Существует ли сценарий, в котором этого не произойдет, то есть когда вы будете использовать отдельный экземпляр string для каждого ключа в пределах диапазона (это то, о чем вы, как я полагаю, беспокоитесь, когда говорите об этом " перерасход памяти ")?

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

Я рассуждаю так: вы хотите присвоить определенные значения различным диапазонам клавиш, верно? Таким образом, каждый раз, когда вы определяете подобие пары ключ-диапазон-значение, у вас есть одиночное значение и несколько клавиш . single - это то, что заставляет меня усомниться в том, что у вас когда-нибудь будет несколько экземпляров одной и той же строки, если только она не определена как значение для более чем одного диапазона.

Для иллюстрации: да, следующий код создаст две одинаковые строки:

string x = "ABC";

Console.Write("Type 'ABC' and press Enter: ");
string y = Console.ReadLine();

Console.WriteLine(Equals(x, y));
Console.WriteLine(ReferenceEquals(x, y));

Приведенная выше программа при условии, что пользователь следует инструкциям и набирает «ABC», выводит True, затем False. Так что вы можете подумать: «Ах, поэтому, когда строка предоставляется только во время выполнения, она не интернируется! Так что это может быть то, где мои значения могут быть продублированы!»

Но ... еще раз: Я так не думаю . Все это возвращается к тому факту, что вы будете назначать single диапазону клавиш. Итак, скажем, ваши значения получены из пользовательского ввода; тогда ваш код будет выглядеть примерно так:

var dictionary = new Dictionary<int, string>();

int start, count;
GetRange(out start, out count);
string value = GetValue();

foreach (int key in Enumerable.Range(start, count))
{
    // Look, you're using the same string instance to assign
    // to each key... how could it be otherwise?
    dictionary[key] = value;
}

---

Теперь, если вы на самом деле больше думаете о том, что Л.Бушкин упоминает в своем ответе - что у вас потенциально могут быть огромные диапазоны, что делает нецелесообразным определение KeyValuePair<int, string> для каждого ключа в пределах этот диапазон (например, если у вас есть диапазон 1-1000000) - тогда я бы согласился, что вам лучше иметь какую-то структуру данных, которая основывается на поиске бинарного поиска. Если это больше ваш сценарий, так и скажите, и я буду рад предложить больше идей на этот счет. (Или вы можете просто посмотреть на ссылку, которую уже опубликовал Л.Бушкин.)

Answer 4

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

Answer 5

arootbeer имеет хорошее решение, но вы можете найти путаницу в работе.

Другой вариант - использовать ссылочный тип вместо строки, чтобы указывать на ту же ссылку

class StringContainer { 
    public string Value { get; set; }
}

Dictionary<int, StringContainer> values;

var value1 = new StringContainer { Value = "ABC" };
values.Add(1, value1);
values.Add(2, value1);

Они оба будут указывать на один и тот же экземпляр StringContainer

РЕДАКТИРОВАТЬ: Спасибо за комментарии всех. Этот метод обрабатывает типы значений, отличные от string, поэтому он может быть полезен не только для данного примера. Кроме того, я понимаю, что строки не всегда ведут себя так, как вы ожидаете от ссылочных значений, но я могу ошибаться.