c# - 具有元组键的字典比嵌套字典慢。为什么？

Question

我测试了使用 (int, int, string) 元组作为键在字典中检索、更新和删除值的速度与使用嵌套字典的相同事物:Dictionary>> 的速度。

我的测试显示元组字典要慢很多(检索 58%，更新 69%，删除 200%)。我原本没想到。嵌套字典需要做更多的查找，那么为什么元组字典要慢得多？

我的测试代码:

    public static object TupleDic_RemoveValue(object[] param)
    {
        var dic = param[0] as Dictionary<(int did, int eid, string name), string>;
        var keysToRetrieve = param[2] as List<(int did, int eid, string name)>;

        foreach (var key in keysToRetrieve)
        {
            dic.Remove(key);
        }

        return dic;

    }


    public static object NestedDic_RemoveValue(object[] param)
    {
        var dic = param[1] as Dictionary<int, Dictionary<int, Dictionary<string, string>>>;
        var keysToRetrieve = param[2] as List<(int did, int eid, string name)>;


        foreach (var key in keysToRetrieve)
        {
            if (dic.TryGetValue(key.did, out var elementMap) && elementMap.TryGetValue(key.eid, out var propertyMap))
                propertyMap.Remove(key.name);
        }

        return dic;

    }

关于测试的额外信息: 该词典总共包含 10 000 个词条。键递增:([0-100],[0-100],"Property[0-100]")。 在一次测试中检索 100 个键(其中 10% 不在字典中)，更新 100 个值(其中 10% 是新的)或删除 100 个键(其中 10% 不在字典中)和)。检索、更新和删除是 3 个独立的测试。每个测试执行 1000 次。我比较了平均执行时间和中位数执行时间。

Answer 1

在 Dictionary 中查找靠两件事。第一个是项目的哈希码，用于将项目分成桶。两个不同 键可以有相同 哈希码，所以一旦找到潜在的匹配项，Equals针对每个项目(使用该哈希码)调用，直到找到完全匹配项。

ValueTuple的哈希码实现(对于 arity-2+ *)传递了 Equality Comparer.Default<T>.GetHashCode 的结果对于内部方法的元组中的每个项目 ValueTuple.CombineHashCodes ，它又调用 System.Numerics.Hashing.HashHelpers.Combine .元组中的项目越多，对 Combine 的嵌套调用就越多方法。将其与正常的 int 进行比较的 GetHashCode它只是直接返回值。

我觉得你的后一个例子会更快。正如评论中所指出的那样，您还削减了必要的数据以搜索更小的分区。每次查找都必须调用 GetHashCode找到潜在的匹配项后，Equals .在我看来，第一种情况下哈希冲突的可能性更高，这意味着对 Equals 的更多调用(在这种情况下，它只是为元组中的每个项目调用 EqualityComparer<T>.Default.Equals)。

最后，它归结为分析(更确切地说，正确地分析—— Release模式、jitting 调用、足够的迭代等)以及您的特定用例。

如果性能真的在您的用例中很重要(例如，在紧密循环中查找)，也许最好使用您自己的类型和哈希码/等于实现而不是 ValueTuple秒。但同样，它归结为分析。

* 请注意，1 元元组有一种特殊情况。

HashHelpers.Combine

ValueTuple

Int32.GetHashCode