Hiệu quả của việc sử dụng IEqualityComparer trong Dictionary vs HashCode và Equals()

Question

Tiêu đề khá rõ ràng.

Tôi đã tự hỏi liệu có một chi phí hiệu quả nhất định khi sử dụng IEqualityComparer trong một Dictionary<K,V> làm thế nào nó hoạt động khi cung cấp?

Cảm ơn

Answer 1

Có nhanh hơn không?

Xuất thân từ một góc độ gamedev, nếu chìa khóa của bạn là một loại giá trị (struct, nguyên thủy, enum, vv) cung cấp riêng EqualityComparer<T> của bạn là đáng kể nhanh hơn - do thực tế các EqualityComparer<T>.Default hộp giá trị.

Ví dụ thực tế, mẫu bảng quảng cáo Managed DirectX được sử dụng để chạy ở ~ 30% tốc độ của phiên bản C++; nơi tất cả các mẫu khác đang chạy ở ~ 90%. Lý do cho điều này là các biển quảng cáo đã được sắp xếp bằng cách sử dụng bộ so sánh mặc định (và do đó được đóng hộp), vì nó chỉ ra 4MB dữ liệu đã được sao chép xung quanh mỗi khung nhờ vào điều này.

Cách hoạt động?

Dictionary<K,V> sẽ tự cung cấp EqualityComparer<T>.Default cho chính nó thông qua hàm tạo mặc định. Có gì comparer bình đẳng mặc định làm là (về cơ bản, chú ý bao nhiêu đấm bốc xảy ra):

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

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

Tại sao tôi sẽ không bao giờ sử dụng nó?

Đó là khá phổ biến để xem loại mã (khi cố gắng để có case-insensitive phím):

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

Đây thực sự là lãng phí, nó là tốt hơn để chỉ cần sử dụng một StringComparer trên constructor:

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

Có nhanh hơn (redux) không?

Trong trường hợp cụ thể này, nó nhanh hơn rất nhiều, vì so sánh chuỗi thứ tự là loại so sánh chuỗi nhanh nhất bạn có thể thực hiện. Một điểm chuẩn nhanh:

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. 

Đặt

Có thể để loại bỏ các chi phí đấm bốc bằng cách thực hiện một giao diện trên một cấu trúc (như IEquatable<T>). Tuy nhiên, có nhiều quy tắc đáng ngạc nhiên khi xảy ra sự kiện boxing trong những trường hợp này nên tôi khuyên bạn nên sử dụng giao diện được ghép nối (ví dụ: IEqualityComparer<T> trong trường hợp này) nếu có thể.

Answer 2

Dictionary<,>luôn sử dụng một IEqualityComparer<TKey> - nếu bạn không vượt qua một, nó sử dụng EqualityComparer<T>.Default. Vì vậy, hiệu quả sẽ phụ thuộc vào mức độ hiệu quả của việc triển khai của bạn được so sánh với EqualityComparer<T>.Default (chỉ ủy quyền cho Equals và GetHashCode).

Answer 3

Jonathan có great answer mà chỉ ra như thế nào, bằng cách sử dụng comparer quyền bình đẳng cải thiện hiệu suất và Jon làm rõ trong his great answer rằng Dictionary<K, V> luôn luôn sử dụng một IEqualityComparer<T> đó là EqualityComparer<T>.Default trừ khi bạn chỉ định khác.

Điều tôi muốn chạm vào là vai trò của giao diện IEquatable<T> khi bạn sử dụng trình so sánh bình đẳng mặc định.

Khi bạn gọi số EqualityComparer<T>.Default, nó sử dụng bộ so sánh được lưu trong bộ nhớ cache nếu có. Nếu đây là lần đầu tiên bạn sử dụng trình so sánh bình đẳng mặc định cho loại đó, nó gọi phương thức có tên là CreateComparer và lưu trữ kết quả để sử dụng sau này. Dưới đây là tỉa và đơn giản hóa việc thực hiện CreateComparer trong .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> 

Nhưng có nghĩa gì đối với các loại mà thực hiện IEquatable<T>?
Ở đây, định nghĩa của GenericEqualityComparer<T>:

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

Sự kỳ diệu sẽ xảy ra trong các loại hạn chế generic (where T : IEquatable<T> phần) vì sử dụng nó không liên quan đến quyền anh nếu T là một loại giá trị, không đúc như (IEquatable<T>)T đang xảy ra ở đây, đó là lợi ích chính của generics.

Vì vậy, giả sử chúng ta muốn một từ điển ánh xạ các số nguyên thành chuỗi.
Điều gì sẽ xảy ra nếu chúng ta khởi tạo một bằng cách sử dụng hàm tạo mặc định?

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

• Chúng ta biết rằng một cuốn từ điển sử dụng EqualityComparer<T>.Default trừ khi chúng tôi chỉ định khác.
• Chúng tôi biết rằng EqualityComparer<int>.Default sẽ kiểm tra xem int có thực hiện IEquatable<int> hay không.
• Chúng tôi biết rằng int (Int32) triển khai IEquatable<Int32>.

cuộc gọi đầu tiên để EqualityComparer<T>.Default sẽ tạo ra và bộ nhớ cache một Comparer chung chung mà có thể mất một chút nhưng khi khởi tạo, đó là một mạnh mẽ gõ GenericEqualityComparer<T> và sử dụng nó sẽ không gây đấm bốc hay overhead không cần thiết nào.

Và tất cả các cuộc gọi tiếp theo đến EqualityComparer<T>.Default sẽ trả về bộ so sánh được lưu trong bộ nhớ cache, có nghĩa là phí khởi tạo chỉ là một lần cho mỗi loại.

---

Vậy điều đó có nghĩa là gì?

• Do thực hiện một bình đẳng comparer tùy chỉnh nếu T không thực hiện IEquatable<T>hay thực hiện của IEquatable<T> không làm những gì bạn muốn nó làm.
  (ví dụ: obj1.Equals(obj2) không cung cấp cho bạn kết quả mong muốn.)

Sử dụng StringComparer trong câu trả lời của Jonathan là một ví dụ tuyệt vời tại sao bạn sẽ chỉ định trình so sánh bình đẳng tùy chỉnh.

• Đừng thực hiện một comparer bình đẳng tùy chỉnh vì lợi ích của hiệu suất nếu T thực hiện IEquatable<T>và thi hành IEquatable<T> làm những gì bạn muốn nó làm.
  (ví dụ: obj1.Equals(obj2) cung cấp cho bạn kết quả mong muốn).

Trong trường hợp thứ hai, sử dụng EqualityComparer<T>.Default thay thế.

Answer 4

tôi phải đối mặt với rắc rối lớn để thực hiện một giống EqualityComparer ... phần quan trọng là GetHashCode được tạo khóa trùng lặp khi nhắm mục tiêu object[] và các hồ sơ có nhiều thì 20k .. dưới đây là giải pháp

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; 
    } 
}