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

Question

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

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

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

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

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

Answer 1

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

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

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

Answer 2

Похоже, у вас на самом деле есть более двух уровней 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 если производительность показывает, что это узкое место.

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