Какова наилучшая структура данных для этой таблицы поиска в памяти?

Мне нужно сохранить таблицу поиска в качестве члена экземпляра в одном из моих классов. Таблица будет инициализирована при создании объекта. Каждая «строка» будет иметь 3 «столбца»:

StringKey (e.g., "car")
EnumKey (e.g., LookupKeys.Car)
Value (e.g, "Ths is a car.")

Я хочу выбрать структуру данных, которая обеспечит наилучшую производительность для выполнения поиска с помощью StringKey или EnumKey.

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

Я мог бы создать структуру Key/Value/Value вместо Key/Key/Value, но мне интересно, какое влияние это окажет на производительность.

Я думаю обо всем этом неправильно?


dictionary lookup data-structures
person Rob Sobers    schedule 13.03.2009    source источник

Ответы (5)


arrow_upward
4
arrow_downward

У вас есть две хэш-карты.

  • Один из StringKey в значение.

  • Один из EnumKey в значение.

Вам не нужно дублировать все экземпляры Value, эти объекты могут быть разделены между двумя хэш-картами.

Если элементов много, вы можете использовать две карты дерева вместо двух хэш-карт. Но основной принцип («Разделяйте ценности») применим к обеим структурам. Один набор значений с двумя картами.

person S.Lott    schedule 13.03.2009
comment
ОК, поэтому в моем примере экземпляры значений представляют собой просто строки. Я сделаю 2 словаря (один с StringKey, один с EnumKey), значения которых содержат одну и ту же ссылочную переменную строки. Это звучит правильно? - person Rob Sobers; 13.03.2009
comment
Точно. В Python это все, что нужно. В Java существует метод string.intern(), который гарантирует, что все строки, переданные методом intern(), будут сведены к общему пулу строк, что устраняет некоторую возможную избыточность. - person S.Lott; 13.03.2009
comment
Я использую C#... знаете ли вы, будет ли .NET копировать строку, когда я добавляю ее в каждый словарь? - person Rob Sobers; 14.03.2009
comment
Добавьте ссылку в каждый словарь. Строка существует один раз. Много ссылок на одну строку. - person S.Lott; 14.03.2009
comment
Понятно. Словари получают свои собственные ссылки на строку, но все они указывают на один и тот же строковый объект. строка s = Джо; dct1.Добавить (ключ, с); -- хотя передаваемый параметр называется s, dct1.Add получает собственную ссылку на joe. Спасибо! - person Rob Sobers; 14.03.2009

arrow_upward
5
arrow_downward

Ну... "Неправильно" - это грубо сказано. Я думаю, что, поскольку наиболее распространенным словарем является «один ключ к значению», и много усилий уходит на создание эффективных структур данных для этого (карты), часто лучше просто использовать два из них, разделяя память для значений, если вообще возможно.

person unwind    schedule 13.03.2009

arrow_upward
1
arrow_downward

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

OR

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

person Brad Barker    schedule 13.03.2009

arrow_upward
0
arrow_downward

Интерфейс LINQ ILookup(TKey, TElement) может помочь. Предполагая, что ваш словарь выглядит примерно так:

Dictionary<carKey, carValue> cars;

Вы можете использовать:

ILookUp<carValue, carKey> lookup = cars.ToLookup(x => x.Value, x => x.Key);

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

person Gordon Mackie JoanMiro    schedule 13.03.2009

arrow_upward
-1
arrow_downward

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

public Value getValue(String key)
{
    dictionary.get(key); // normal way
}

public Value getValue(Enum enumKey)
{
    String realKey = toKey(enumKey);
    getValue(realKey); // use String key
}

Вы могли бы реализовать в своем Enum метод toKey(), который возвращает их ключ String, или, возможно, иметь другой словарь, который сопоставляет значения Enum с аналогами String.

person Outlaw Programmer    schedule 13.03.2009