Эффективность использования IEqualityComparer в словаре против HashCode и Equals()
Название довольно ясно, я думаю.
Мне было интересно, если есть определенные издержки эффективности при использовании IEqualityComparer в Dictionary<K,V> как все это работает при предоставлении одного?
Спасибо
4 ответа
Это быстрее?
Исходя из перспективы gamedev, если ваш ключ является типом значения (struct, primitive, enum и т. Д.), Предоставляющим ваш собственный EqualityComparer<T> значительно быстрее - из-за того, что EqualityComparer<T>.Default коробки значение.
В качестве примера можно привести образец рекламного щита Managed DirectX, работавший со скоростью ~30% от скорости версии C++; где все остальные образцы работали на ~90%. Причиной этого было то, что рекламные щиты сортировались с использованием компаратора по умолчанию (и, следовательно, упаковывались), так как оказалось, что благодаря этому 4МБ данных копировалось вокруг каждого кадра.
Как это работает?
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> в этом случае) если вообще возможно.
У Джонатана отличный ответ, который указывает на то, как использование правильного средства сравнения равенств повышает производительность, и в своем великолепном ответе Джон разъясняет, что 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проверит, реализует ли intIEquatable<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 вместо.
Dictionary<,> всегда использует IEqualityComparer<TKey> - если вы не пропустите один, он использует EqualityComparer<T>.Default, Таким образом, эффективность будет зависеть от эффективности вашей реализации по сравнению с EqualityComparer<T>.Default (который просто делегирует Equals а также GetHashCode).
Я столкнулся с огромной проблемой, чтобы сделать идентичный EqualityComparer... критический раздел былGetHashCode который генерировал дубликат ключа при нацеливании object[] а записи больше 20к.. ниже решение
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;
}
}