字典与元组键比嵌套字典慢.为什么？

Question

我已经测试了使用(int,int,string)元组作为键来检索,更新和删除字典中的值的速度,而不是使用嵌套的Dictionary: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],"属性[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对元组中每个项目的调用).

最后归结为分析(更确切地说,正确分析 - 发布模式,调用调用,足够的迭代等)以及您的特定用例.

如果性能在您的用例中非常重要(例如,在紧密循环中查找),也许最好使用您自己的类型和哈希代码/等于实现而不是ValueTuples.但同样,它归结为剖析.

*请注意,1-arity元组有一个特殊情况.

HashHelpers.Combine

ValueTuple

Int32.GetHashCode