基于元组或嵌套字典有益处吗？

Question

我一直在寻找一种方法来存储和检索超过C#的通用Dictionary类提供的单个键的值.

在网上搜索(以及SO本身)向我展示了几个选项:

基于元组的词典

.NET 4.0可以轻松支持通用的Tuple <,>类.这意味着您可以使用任意元组创建一个Dictionary,即

• var myDict = new Dictionary<Tuple<Char, Int>, MyClass>();

嵌套字典

我了解到你也可以在Dictionaries中嵌套Dictionaries,这使得访问存储的结果类似于访问N维数组.例如:

Dictionary<int, Dictionary<int, Dictionary<Char, MyClass>>>

然后可以通过以下方式获得: MyClass foo = MyData[8][3]['W'];

定界连锁键词典

但是,虽然两者都适用于复杂数据和自定义类,但我想知道它们是否总是必要的.至少对于原始数据,看起来将键与分隔符连接起来同样有效.

//keys are char + int
Dictionary<string, MyClass> myDict = New Dictionary<string, Myclass>();
String input = myChar + "|" + myInt
MyClass foo = myDict[input]

是否存在使这些方法中的一种优于另一种方案的情景？他们会有类似的表演时间吗？或者重点应该放在哪种方法提供最干净,最容易维护的代码上？

思考？

Answer 1

定界连锁键词典

至少有三个原因可以避免这种方法:

• 这很神奇.键的类型中没有任何内容可以告诉您如何构造它或它代表什么.
• 如果分隔符意外地显示为其中一个值,则您的方法将失败.
• 转换为字符串,并且这些字符串的比较可能(稍微)慢于使用两种基本类型.

嵌套字典

这解决了分隔符的问题,但引入了一些新问题:

• 插入新值很困难,因为对于每个嵌套级别,您必须检查该键是否已存在.如果没有,您需要创建一个新字典作为值.这使得使用字典更加困难.
• 将会有进一步的内存和性能开销.

基于元组的词典

在你发布的方法中,这可能是最好的.

但是你可以更进一步,struct为你的密钥创建一个名为immutable 的东西.这将使您的字典更易于使用,因为密钥的各个部分可以具有有用的名称.

Answer 2

或者应该关注哪种方法提供最干净、最容易维护的代码？

除非你的重点是编写可怕的、令人生畏的代码，否则你应该避免使用字符串分隔和连接方法，这是不言而喻的邪恶。

在基于元组和嵌套字典的方法之间进行选择取决于您的上下文。调整性能？或者调整可读性？我先说后者。

从可维护性的角度来看，

• 实现如下功能要容易得多：

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

  比

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

  从被叫方。在第二种情况下，每次添加、查找、删除等都需要对多个字典进行操作。

• 此外，如果您的复合键将来需要一个更多（或更少）的字段，您将需要在第二种情况（嵌套字典）中大量更改代码，因为您必须添加更多嵌套字典和后续检查。

从性能的角度来看，您可以得出的最佳结论是自己进行测量。但是，您可以事先考虑一些理论限制：

• 在嵌套字典的情况下，为每个键（外部和内部）拥有一个额外的字典将有一些内存开销（比创建元组所具有的更多）。

• 在嵌套字典的情况下，添加、更新、查找、删除等每个基本操作都需要在两个字典中执行。现在有一种情况，嵌套字典方法可以更快，即，当正在查找的数据不存在时，因为中间字典可以绕过完整的哈希码计算和比较，但是应该再次确定时间。在存在数据的情况下，它应该更慢，因为查找应该执行两次（或三次，取决于嵌套）。

• 关于元组的方法，.NET元组是不是最高效的，当他们命中注定要被用作自钥匙套Equals和GetHashCode实施的原因拳击值类型。

总的来说，我发现很少需要嵌套字典方法。很可能有人不想要它。我宁愿基于元组的方法，但你应该写一个具有更好的实现自己的元组，并在此一例char和int钥匙，我更喜欢使其成为一个（immutable）的结构。

一个非常相关的问题：元组（或数组）作为 C# 中的字典键

Answer 3

我想补充上面的答案，在某些情况下（取决于数据的分布方式），嵌套字典在内存占用方面比复合键字典好得多（这反过来可能会导致更好的性能总体）。这样做的原因是嵌套可以省去为键保存重复值的需要，这在大型字典中会使额外字典的占用空间可以忽略不计。

例如，假设我需要一个复合键为 (male/female),(baby/young/old),(age) 的字典。

让我们用复合键字典保存一些值：

(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 个项目 vs 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;
    }

此测试返回 ~30MB 与 ~70MB 以支持字典。