在Dictionary中使用IEqualityComparer与HashCode和Equals（）的效率

问题描述 投票：17回答：4

我认为标题非常清楚。

我想知道在IEqualityComparer中使用Dictionary<K,V>时是否存在一定的效率开销，在提供一个时它是如何工作的？

谢谢

c# .net performance dictionary
4个回答
34
投票

它更快吗？

从gamedev的角度来看，如果你的键是一个值类型（struct，primitive，enum等），那么提供你自己的EqualityComparer<T>要快得多 - 因为EqualityComparer<T>.Default将这个值设置为值。

作为一个真实的例子，Managed DirectX广告牌样本的运行速度大约是C ++版本的30％;其他所有样品的运行率均在~90％左右。原因是广告牌使用默认比较器进行排序（因此被装箱），因为事实证明，每个帧周围都会复制4MB的数据。

它是如何工作的？

Dictionary<K,V>将通过默认构造函数向自己提供EqualityComparer<T>.Default。默认的相等比较器的作用是什么（基本上，注意发生了多少拳击）：

public void GetHashCode(T value)
{
   return ((object)value).GetHashCode();
}

public void Equals(T first, T second)
{
   return ((object)first).Equals((object)second);
}

我为什么要用它？

看到这种代码（尝试使用不区分大小写的键时）很常见：

var dict = new Dictionary<string, int>();
dict.Add(myParam.ToUpperInvariant(), fooParam);
// ...
var val = dict[myParam.ToUpperInvariant()];

这真的很浪费，最好在构造函数上使用StringComparer：

var dict = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase);

它更快（redux）？

在这种特定情况下，它要快得多，因为序数字符串比较是您可以做的最快的字符串比较类型。快速基准：

static void Main(string[] args)
{
    var d1 = new Dictionary<string, int>();
    var d2 = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase);

    d1.Add("FOO", 1);
    d2.Add("FOO", 1);

    Stopwatch s = new Stopwatch();
    s.Start();
    RunTest1(d1, "foo");
    s.Stop();
    Console.WriteLine("ToUpperInvariant: {0}", s.Elapsed);

    s.Reset();
    s.Start();
    RunTest2(d2, "foo");
    s.Stop();
    Console.WriteLine("OrdinalIgnoreCase: {0}", s.Elapsed);

    Console.ReadLine();
}

static void RunTest1(Dictionary<string, int> values, string val)
{
    for (var i = 0; i < 10000000; i++)
    {
        values[val.ToUpperInvariant()] = values[val.ToUpperInvariant()];
    }
}

static void RunTest2(Dictionary<string, int> values, string val)
{
    for (var i = 0; i < 10000000; i++)
    {
        values[val] = values[val];
    }
}

// ToUpperInvariant: 00:00:04.5084119
// OrdinalIgnoreCase: 00:00:02.1211549
// 2x faster.

预订

通过在结构上实现接口（例如IEquatable<T>）可以消除装箱开销。然而，在这些情况下发生拳击时有许多令人惊讶的规则，所以如果可能的话，我建议使用配对界面（例如在这种情况下为IEqualityComparer<T>）。

20
投票

Jonathan有一个great answer，指出如何使用正确的相等比较器改善性能，Jon在his great answer澄清Dictionary<K, V>总是使用IEqualityComparer<T>，这是EqualityComparer<T>.Default，除非你指定另一个。

我想谈的是当你使用默认的相等比较器时IEquatable<T>接口的作用。

当你调用EqualityComparer<T>.Default时，它会使用缓存的比较器（如果有的话）。如果这是您第一次使用该类型的默认相等比较器，它会调用一个名为CreateComparer的方法并将结果缓存以供以后使用。以下是.NET 4.5中CreateComparer的修剪和简化实现：

var t = (RuntimeType)typeof(T);

// If T is byte,
// return a ByteEqualityComparer.

// If T implements IEquatable<T>,
if (typeof(IEquatable<T>).IsAssignableFrom(t))
    return (EqualityComparer<T>)
           RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter(
               (RuntimeType)typeof(GenericEqualityComparer<int>), t);

// If T is a Nullable<U> where U implements IEquatable<U>,
// return a NullableEqualityComparer<U>

// If T is an int-based Enum,
// return an EnumEqualityComparer<T>

// Otherwise return an ObjectEqualityComparer<T>

但是对于实现IEquatable<T>的类型意味着什么？ 在这里，GenericEqualityComparer<T>的定义：

internal class GenericEqualityComparer<T> : EqualityComparer<T>
    where T: IEquatable<T>
// ...

魔法发生在泛型类型约束（where T : IEquatable<T>部分）中因为使用它不涉及拳击如果T是一个值类型，这里没有像(IEquatable<T>)T那样的演员，这是泛型的主要好处。

所以，假设我们想要一个将整数映射到字符串的字典。 如果我们使用默认构造函数初始化一个会发生什么？

var dict = new Dictionary<int, string>();
  • 我们知道字典使用EqualityComparer<T>.Default，除非我们指定另一个。
  • 我们知道EqualityComparer<int>.Default将检查int是否实现了IEquatable<int>。
  • 我们知道int（Int32）实施IEquatable<Int32>。

第一次调用EqualityComparer<T>.Default将创建并缓存一个通用的比较器，这可能需要一点点但是在初始化时，它是一个强类型的GenericEqualityComparer<T>并且使用它将不会导致装箱或不必要的开销。

所有后续调用EqualityComparer<T>.Default都将返回缓存的比较器，这意味着初始化的开销只对每种类型一次性。

那么这一切意味着什么呢？

  • 如果T没有实现IEquatable<T>或者它的IEquatable<T>实现没有按照你想要它做的那样，那么实现自定义相等比较器。 （即obj1.Equals(obj2)没有给你想要的结果。）

在Jonathan的回答中使用StringComparer是一个很好的例子，为什么你要指定一个自定义的相等比较器。

  • 如果T实现了IEquatable<T>并且IEquatable<T>的实现完成了你想要它做的事情，那么为了性能，不要实现自定义相等比较器。 （即obj1.Equals(obj2)为您提供所需的结果）。

在后一种情况下，请改用EqualityComparer<T>.Default。

8
投票

Dictionary<,>总是使用IEqualityComparer<TKey> - 如果你不通过它，它使用EqualityComparer<T>.Default。因此效率将取决于您的实施与EqualityComparer<T>.Default（仅代表Equals和GetHashCode）的效率。

0
投票

我制造一个相同的EqualityComparer ...关键部分wasGetHashCode面临巨大的麻烦，当针对object[]并且记录超过20k时生成重复密钥..以下是解决方案

public class ObJectArrayEqualityComparer : IEqualityComparer<object[]>
{ 
    public bool Equals(object[] x, object[] y)
    {
        if (x.Length != y.Length)
        {
            return false;
        }
        for (int i = 0; i < x.Length; i++)
        {
            var tempX = x[i];
            var tempY = y[i];
            if ((tempX==null || tempX ==DBNull.Value) 
                && (tempY == null || tempY == DBNull.Value))
            {
                return true;
            }

            if (!tempX.Equals(tempY) 
                && !System.Collections.StructuralComparisons.StructuralEqualityComparer.Equals(tempX, tempY))
            {
                return false;
            }
        }
        return true;
    }

    public int GetHashCode(object[] obj)
    {
        if (obj.Length == 1)
        {
            return obj[0].GetHashCode();
        }

        int result = 0;

        for (int i = 0; i < obj.Length; i++)
        {
            result = result + (obj[i].GetHashCode() * (65 + i));
        }

        return result;
    }
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.