Обратный поиск во вложенном словаре - PullRequest
Новая
       53

Обратный поиск во вложенном словаре

3 голосов
/ 21 мая 2011 
Dictionary<string, Dictionary<string, ... >...> nestedDictionary;

Выше Dictionary имеет отношение one-to-many на каждом уровне сверху вниз.Добавить элемент довольно легко, так как у нас есть листовой объект, и мы начинаем снизу, создавая словари и добавляя каждый к соответствующему родительскому элементу ...

Моя проблема в том, когда я хочу найти элемент во внутренних словарях,Есть два варианта:

  1. Вложенный foreach, найти элемент, сделать снимок всех циклов в тот момент, когда мы нашли элемент, и выйти из всех циклов.Тогда мы знаем, что родословная элемента это string1-> string2 -> ...-> stringN.Проблемы с этим решением: A) Производительность B) Потокобезопасность (поскольку я хочу удалить элемент, родитель, если у него нет дочернего элемента, и его родитель, если у него нет дочернего элемента ...)
  2. Создание реверсапоиск словаря и индексация добавленных элементов.Что-то вроде Tuple для всех внешних словарей.Затем добавьте элемент в качестве ключа и все внешние родители в качестве Tuple членов.Проблема: A) Резервирование B) Поддержание синхронизированного обратного просмотра Dictionary с основным Dictionary.

Есть идеи для быстрого и поточно-ориентированного решения?

Ответы [ 2 ]

1 голос
/ 21 мая 2011

Хотя у меня мало непосредственного опыта работы с C5 библиотекой коллекций , похоже, вы могли бы использовать их TreeDictionary .Он поставляется с целым набором полезных методов для поиска, итерации и изменения дерева, и на удивление хорошо документирован.

Другой вариант - использовать библиотеку QuickGraph (которую вы можете найти в NuGet или в codeplex),Это включает в себя некоторые знания теории графов, но в остальном очень полезная библиотека.

Обе библиотеки требуют, чтобы вы обрабатывали параллелизм, как и стандартные коллекции BCL.

1 голос
/ 21 мая 2011

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

 Dictionary<string, Dictionary<string, ... >...> nestedDictionary;

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

Я собираюсь предположить, что вам нужны такие звонки: 

var dictionary = new ThreeLevelDictionary();
dictionary.Add(string1, string2, string3, value);
var value = dictionary[string1, string2, string3];
dictionary.Remove(string1, string2, string3);

И (критический вопрос) описываемый вами обратный поиск: 

var strings = dictionary.FindKeys(value);

Если это операции, которые вам нужно выполнить и выполнить быстро, то одна из структур данных, которую вы можете использовать, это Dictionary с клавишей Tuple: 

public class ThreeLevelDictionary<TValue> : Dictionary<Tuple<string, string, string>, TValue>
{
    public void Add(string s1, string s2, string s3, TValue value)
    {
        Add(Tuple.Create(s1, s2, s3), value);
    }

    public TValue this[string s1, string s2, string s3]
    {
        get { return this[Tuple.Create(s1, s2, s3)]; }
        set { value = this[Tuple.Create(s1, s2, s3)]; }
    }

    public void Remove(string s1, string s2, string s3)
    {
        Remove(Tuple.Create(s1, s2, s3);
    }

    public IEnumerable<string> FindKeys(TValue value)
    {
        foreach (var key in Keys)
        {
            if (EqualityComparer<TValue>.Default.Equals(this[key], value))
                return new string[] { key.Item1, key.Item2, key.Item3 };
        }
        throw new InvalidOperationException("missing value");
    }
}

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

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

...