21

我一直在寻找一种方法来存储和检索 C# 的通用 Dictionary 类提供的多个键上的值。

在网络上搜索（以及 SO 本身）向我展示了几个选项：

基于元组的字典

.NET 4.0 使支持泛型 Tuple<,> 类变得容易。这意味着您可以使用任意元组制作字典，即

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

嵌套字典

我了解到您还可以在字典中嵌套字典，这使得访问存储的结果类似于访问 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]

是否有任何情况使这些方法中的一种优于另一种？他们会有相似的表演时间吗？还是应该关注哪种方法提供最干净、最容易维护的代码？

想法？

4

4 回答 4

17

分隔连接键字典

我会避免这种方法的原因至少有三个：

  • 这是魔术。键的类型中没有任何内容可以告诉您如何构造它或它代表什么。
  • 如果分隔符意外地作为值之一出现，您的方法将失败。
  • 转换为字符串，以及这些字符串的比较可能（稍微）比使用两种原始类型慢。

嵌套字典

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

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

基于元组的字典

在您发布的方法中，这可能是最好的。

但是您可以更进一步，struct为您的密钥创建一个命名的不可变对象。这将使您的字典更易于使用，因为键的部分可以具有有用的名称。

于 2012-08-10T20:46:44.880 回答
7

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

除非您的重点是编写噩梦般的、令人生畏的代码，否则您应该避免使用字符串定界和连接方法，这是不言而喻的邪恶。

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

从可维护性的角度来看，

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

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

    比

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

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

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

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

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

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

  • 关于元组方法，.NET 元组在用作集合中的键时并不是性能最高的，因为它的Equals实现GetHashCode会导致值类型的装箱。

总的来说，我发现很少需要嵌套字典方法。赔率是一个人不想要它。我更喜欢基于元组的方法，但是您应该编写一个具有更好实现的自己的元组，在这种情况下char，int我更喜欢将其设为（不可变）结构。

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

于 2014-01-13T12:13:08.900 回答
5

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

例如，假设我需要一个具有（男/女）、（婴儿/年轻/老人）、（年龄）复合键的字典。

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

(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;
    }

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

于 2015-07-21T19:32:15.030 回答
2

您描述的所有选项都非常相似 - 至于性能，您需要针对您的特定使用场景测试每个选项，但对于小型集合，它们不太可能有太大差异。

它们也都受到可读性的影响——很难构造它们并从类型中梳理出含义。

相反，最好创建一个直接描述数据的类型——好的命名有很长的路要走。

于 2012-08-10T20:47:45.850 回答