在Dictionary中使用IEqualityComparer与HashCode和Equals()的效率

Question

我认为标题非常清楚.

我在想,如果有使用的时候是有一定效率的开销IEqualityComparer在Dictionary<K,V>提供一个当这是如何工作的？

谢谢

Answer 1

它更快吗？

从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>在这种情况下),如果可能的话.

Answer 2

Jonathan有一个很好的答案,指出如何使用正确的相等比较器改善性能,Jon在他的好答案中澄清,除非你指定另一个,否则Dictionary<K, V>总是使用.IEqualityComparer<T>EqualityComparer<T>.Default

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

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

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)给你想要的结果.)

使用StringComparer在乔纳森的回答是一个很好的例子,为什么你会指定自定义相等比较.

• 如果T实现IEquatable<T> 和实现执行IEquatable<T>您希望它执行的操作,则不要为了性能而实现自定义相等比较器.
  (即obj1.Equals(obj2)给你想要的结果).

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

Answer 3

Dictionary<,> 总是使用IEqualityComparer<TKey>- 如果你没有通过,它会使用EqualityComparer<T>.Default.因此,效率将取决于您的实现与之比较的效率EqualityComparer<T>.Default(仅代表Equals和GetHashCode).