Есть ли структура данных, которая содержит наборы данных в .NET?

Question

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

Например, я бы использовал это так:

var data = new FancyDataStructure();

data.Add(new string[] {"Elizabeth", "Liz", "Betty"});
data.Add(new string[] {"Bob", "Robert", "Rob"});

string[] alternateNames1 = data["Betty"];
string[] alternateNames2 = data["Liz"]

В этом случае alternateNames1 будет массивом, содержащим «Лиз» и «Элизабет», а alternateNames2 будет массивом, содержащим «Элизабет» и «Бетти».

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

Обновление

Спасибо тем, кто написал обратно с предложениями. Многие люди предлагают использовать какую-то версию Dictionary<string, IEnumerable<string>>. В настоящее время я использую этот подход, но на самом деле он не соответствует требованию, не будучи ужасно сложным в обслуживании. Каждое значение в каждом списке должно быть способно функционировать как ключ к любому другому значению, когда-либо добавленному к нему в наборе.

Таким образом, учитывая следующее:

data.Add(new string[] {"Elizabeth", "Liz"}
data.Add(new string[] {"Liz", "Betty"}
alternates = data["Betty"];

Я бы ожидал, что теперь в альтернативах будут присутствовать "Элизабет" и "Лиз".

Похоже, мне просто нужно построить такую ​​структуру, которая бы соответствовала моим потребностям. Продолжайте воплощать идеи в жизнь!

Brian

Answer 1

Ваша проблема звучит так, как будто это действительно график проблема. Думайте об именах как об узлах, а членство в наборе - как ребра. С этой точки зрения вам нужна структура данных, которая хорошо обрабатывает разреженные графы, например, список смежностей . Это, конечно, похоже на то, что вы уже делаете с Dictionary<string, IEnumerable<string>>, но размышления об этом таким образом могут привести к некоторым полезным реализациям и алгоритмам.

Answer 2

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

Итерация и возможность Linq как бы встроены.

Может быть, излишне много вещей, но у меня есть несколько мест, где я хранил весь набор данных в одном столбце varbinary (max) в SQL.

Answer 3

System.Collections.Generic namespace и System.Collections загружаются с парными словарями KeyValue, отсортированными словарями, объектами List и многими другими.

System.Collections.Generic.Dictionary<int, string> dic = new Dictionary<int, string>();
        dic.Add(1, test);

или вложенный список в словаре

Dictionary<string, List<string>> dic = new Dictionary<string, List<string>>();
List<string> alternatives = new List<string>();
alternatives.Add("Brenda");
dic.Add("Betty", alternatives);

Answer 4

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

Это ваша структура

class FancyDataStructure
{
    private IDictionary<string, HashSet<string>> dictionary 
        = new Dictionary<string, HashSet<string>>();

    public void Add(params string[] names)
    {
        HashSet<string> set = new HashSet<string>(names);
        for (int i = 0; i < names.Length; i++)
        {
            if (!dictionary.ContainsKey(names[i]))
            {
                dictionary.Add(names[i], set);
            }
            else
            {
                HashSet<string> union = 
                new HashSet<string>(set.Union<string>(dictionary[names[i]]));
                set = union;
                foreach (string oldName in dictionary[names[i]])
                {
                    dictionary[oldName] = union;
                }
                for (int j = 0; j < i; j++)
                {
                    if (!dictionary.ContainsKey(names[j]))
                    {
                        dictionary.Add(names[j], union);
                    }
                }
            }
        }
    }

    public string[] this[string key]
    {
        get
        {
            List<string> result = dictionary[key].ToList<string>();
            result.Remove(key);
            return result.ToArray();
        }
    }
}

и вы можете использовать его, как это

    static void Main(string[] args)
    {

        FancyDataStructure data = new FancyDataStructure();

        data.Add("Elizabeth", "Liz");
        data.Add("Liz", "Betty");

        string[] alternates = data["Betty"];
        foreach (var item in alternates)
        {
            Console.WriteLine(item);
        }
    }

Answer 5

Или, поскольку List является ссылочным типом, вы можете сделать следующее ...

Dictionary<string, List<string>> dict = new ...

Действуйте следующим образом: -

Чтобы добавить одну ассоциацию (a = b) {разлагается из списка эквивалентностей}

Поиск a и b в словаре

Если ни один не существует

dict.Add(a, new List<string>(){a}); dict.Add(b, new List<string>(){b});

Если таковой существует, скажем,

var list = dict[a];
list.Add(b);
dict.Add(b, list);

Если оба существуют и списки совпадают (сравнение объектов), то все готово.

Если оба существуют и списки различаются:

var list1 = dict[a];
var list2 = dict[b];
list1.AddRange(list2);
dict.Remove(b);
dict.Add(b, list1);

Answer 6

Как насчет пары структур данных: Dictionary<string, Guid> и Dictionary<Guid, List<string>>

Чтобы добавить пару ключей (a, b) [вы можете разложить большее дополнение на пары (1 + 2, 2 + 3, ...], действуйте следующим образом: -

Поиск a и b в первом словаре.
Если ни один не существует, создайте новый Guid и добавьте (a, g) и (b, g) в первый словарь и (g, List {a}) и (g, List {b}) во второй словарь.

Если один существует, скажем, a, возьмите guid из него (g) и добавьте другой (b, g) в первый словарь и прикрепите b к концу списка, найденного в [g] во втором словаре.

Если оба существуют И у них одинаковый гид - ничего не делать.

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

Чтобы получить все связанные слова, найдите Guid в первом словаре и возьмите список из второго словаря.

Конечно, статически увеличивающееся длинное значение, вероятно, будет работать лучше, чем Guid.

Answer 7

Попробуйте использовать словарь, что-то вроде:

Dictionary<string, List<string>>

Итак, словарь строковых ключей со значениями List

Answer 8

У вас есть словарь, в котором несколько ключей отображаются на одно и то же значение. Нет встроенной структуры данных, которая поддерживает требуемую операцию, но ее легко представить в виде Dictionary{string, HashSet{string}} в .NET:

static void AddNames(Dictionary<string, HashSet<string>> map, params string[] names)
{
    for (int i = 0; i < names.Length; i++)
    {
        HashSet<string> value;
        if (!map.TryGetValue(names[i], out value))
        {
            value = new HashSet<string>();
            map.Add(names[i], value);
        }

        for (int j = 0; j < names.Length; j++)
        {
            value.Add(names[j]);
        }
    }
}

static void Main(string[] args)
{
    Dictionary<string, HashSet<string>> names = new Dictionary<string,HashSet<string>>();
    AddNames(names, "Chris", "Christopher");
    AddNames(names, "Christina", "Chrissy", "Chris");

    HashSet<string> relatedToChris = names["Chris"];                // gets "Chris", "Christina", "Chrissy", "Christopher";
    HashSet<string> namesRelatedToChristinia = names["Christina"];  // gets "Christina", "Chrissy", "Chris";
}

Вы можете представить свою структуру данных как ориентированный граф, в котором у каждого узла есть ребро, связанное со своим связанным именем. Поскольку существует n ^ 2 ребер, словарь требует O (n ^ 2) времени для вставки и памяти. Невозможно сократить время поиска чего-либо лучшего.

К счастью, поскольку он реализован в виде словаря, он выглядит как O (1). Удаляет O (m), где m - количество значений, связанных с ключом.

Answer 9

Я бы просто использовал тип Dictionary<string, IEnumerable<string>>.Чтобы построить эту структуру из списка списков, вы можете иметь такой код:

var alternateNames = new string[][] {
    new string[] { "Elizabeth", "Liz", "Betty" },
    new string[] { "Bob", "Robert", "Rob" }, };
var altNameLookup = 
    (
        from nameList in alternateNames
        from name in nameList
        select new { 
            Name = name, NameList = nameList.Except(new string[] { name } ) }
    ).ToDictionary(o => o.Name, o => o.NameList);

Answer 10

Я использую это:

• Универсальная библиотека коллекции C5 для C # и CLI .

Он имеет универсальный тип Set и реализует все прекрасные итераторы, .Contains, .Count и т. Д.