Эффективность использования IEqualityComparer в словаре vs HashCode и Equals()

Ответ 1

Быстрее?

Исходя из перспективы gamedev, если ваш ключ - тип значения (struct, primitive, enum и т.д.), обеспечивающий ваш собственный EqualityComparer<T> значительно быстрее - из-за того, что значение EqualityComparer<T>.Default содержит значение.

Как пример в реальном мире, образец Billboard Managed DirectX, используемый для запуска на ~ 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);

Является ли это быстрее (сокращение)?

В этом конкретном сценарии это происходит намного быстрее, потому что сопоставление порядковых строк - это самый быстрый тип сравнения строк, который вы можете сделать. Быстрый тест:

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> в этом случае), если это вообще возможно.

Ответ 2

Джонатан имеет отличный ответ, который указывает, как с помощью правильного сравнения сравнений производительность улучшается, а Джон уточняет в его отличный ответ, что 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> part), потому что использование этого не связано с боксом, если 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.

Ответ 3

Dictionary<,> всегда использует IEqualityComparer<TKey> - если вы его не передаете, он использует EqualityComparer<T>.Default. Таким образом, эффективность будет зависеть от того, насколько эффективна ваша реализация по сравнению с EqualityComparer<T>.Default (которая просто делегирует Equals и GetHashCode).