Есть ли преимущества для основанных на Tuple или вложенных словарей?

Ответ 1

Разделимые ключевые слова со сцепленными ключами

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

• Это волшебство. В типе ключа ничего не сказано о том, как его построить или что он представляет.
• Если разделитель случайно появляется как одно из значений, ваш подход не работает.
• Преобразование в строки и сравнение этих строк, вероятно, будет (немного) медленнее, чем использование двух примитивных типов.

Вложенные словари

Это решает проблему с разделителем, но вводит некоторые новые проблемы:

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

Словарные словари

Из подходов, которые вы опубликовали, это, вероятно, лучший.

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

Ответ 2

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

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

Сохраните некоторые значения со словарем составных клавиш:

(male, baby, 1)
(male, baby, 2)
(male, baby, 3)
(male, young, 21)
(male, young, 22)
(male, young, 23)
(male, old, 91)
(male, old, 92)
(male, old, 93)
(female, baby, 1)
(female, baby, 2)
(female, baby, 3)
(female, young, 21)
(female, young, 22)
(female, young, 23)
(female, old, 91)
(female, old, 92)
(female, old, 93)

Теперь сохраним те же значения в словаре словарей:

male -> baby ->  1
                 2
                 3
        young -> 21
                 22
                 23
        old  ->  91
                 92
                 93
female -> baby ->1
                 2
                 3
        young -> 21
                 22
                 23
        old  ->  91
                 92
                 93

В комбинированном ключе я сохраняю копию "мужского" и "женского" 9 раз, в отличие от одной копии словаря словарей. Фактически, я сохранил 54 предмета против 26 предметов, получив в два раза больше памяти. Пример также помогает визуализировать разницу, видеть, сколько "пустого" пространства есть во втором примере по сравнению с первым, это все значения, которые нам не нужно было сохранять.

И для тех, которые еще не убеждены, вот пример теста:

    Dictionary<Tuple<int, int, int>, int> map1 = new Dictionary<Tuple<int, int, int>, int>();
    Dictionary<int, Dictionary<int, Dictionary<int, int>>> map2 = new Dictionary<int, Dictionary<int, Dictionary<int, int>>>();

    public void SizeTest()
    {
        for (int x = 0; x < 30; x++)
        {
            for (int y = 0; y < 100; y++)
            {
                for (int z = 0; z < 600; z++)
                {
                    addToMap1(x, y, z, 0);
                    addToMap2(x, y, z, 0);
                }
            }
        }
        int size1 = GetObjectSize(map1);
        int size2 = GetObjectSize(map2);

        Console.WriteLine(size1);
        Console.WriteLine(size2);
    }

    private void addToMap1(int x, int y, int z, int value)
    {
        map1.Add(new Tuple<int, int, int>(x, y, z), value);
    }

    private void addToMap2(int x, int y, int z, int value)
    {
        map2.GetOrAdd(x, _ => new Dictionary<int, Dictionary<int, int>>())
            .GetOrAdd(y, _ => new Dictionary<int, int>())
            .GetOrAdd(z, _ => value);
    }

    private int GetObjectSize(object TestObject)
    {
        BinaryFormatter bf = new BinaryFormatter();
        MemoryStream ms = new MemoryStream();
        byte[] Array;
        bf.Serialize(ms, TestObject);
        Array = ms.ToArray();
        return Array.Length;
    }

    public static TResult GetOrAdd<TKey, TResult>(this Dictionary<TKey, TResult> map, TKey key, Func<TKey, TResult> addIfMissing)
    {
        TResult result;
        if (!map.TryGetValue(key, out result))
        {
            result = addIfMissing(key);
            map[key] = result;
        }
        return result;
    }

Этот тест возвращает ~ 30 МБ против ~ 70 МБ в пользу словаря словарей.

Ответ 3

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

Они также страдают от читаемости - их сложно построить и вычеркнуть смысл из типов.

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

Ответ 4

Или следует ли сосредоточиться на том, какой метод обеспечивает самый чистый, самый простой в обслуживании код?

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

Выбор между кортежем и подходами, основанными на вложенных словарях, зависит от вашего контекста. Улучшить производительность? Или настроить для удобства чтения? Сначала я расскажу о последних.

С точки зрения удобства обслуживания,

• Его гораздо проще реализовать функциональность, которая выглядит следующим образом:

  var myDict = new Dictionary<Tuple<char, int>, MyClass>();
  

  чем

  var myDict = new Dictionary<char, Dictionary<int, MyClass>>();
  

  со стороны вызываемого лица. Во втором случае каждое дополнение, поиск, удаление и т.д. Требуют действия более чем на одном словаре.

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

С точки зрения эффективности лучший результат, который вы можете достичь, - это измерить его самостоятельно. Но есть несколько теоретических ограничений, которые вы можете рассмотреть заранее:

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

• В случае вложенного словаря каждое базовое действие, такое как сложение, обновление, поиск, удаление и т.д., должно выполняться в двух словарях. Теперь есть случай, когда вложенный словарьный подход может быть более быстрым, т.е. Когда просматриваемые данные отсутствуют, поскольку промежуточные словари могут обойти полное вычисление и сравнение хэш-кода, но с другой стороны, он должен быть приурочен к тому, чтобы быть уверенным. При наличии данных он должен быть медленнее, так как поиск должен выполняться дважды (или три раза в зависимости от вложенности).

• Что касается подхода с кортежем, то кортежи .NET не являются наиболее эффективными, когда они предназначены для использования в качестве ключей в наборах, поскольку его Equals и GetHashCode реализация вызывает бокс для типов значений.

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

Очень близкий вопрос: Кортежи (или массивы) в качестве словарных ключей на С#