Thời gian chạy cao cho từ điển.Thêm một số lượng lớn các mục

Question

Tôi có C# -Ứng dụng lưu trữ dữ liệu từ một TextFile trong một đối tượng từ điển. Số lượng dữ liệu được lưu trữ có thể khá lớn, vì vậy phải mất rất nhiều thời gian chèn các mục nhập. Với nhiều mục trong từ điển nó thậm chí còn tồi tệ hơn, vì việc thay đổi kích thước của mảng nội bộ, lưu trữ dữ liệu cho từ điển. Vì vậy, tôi đã khởi tạo từ điển với số lượng các mục sẽ được thêm vào, nhưng điều này không ảnh hưởng đến tốc độ.

Đây là chức năng của tôi:

private Dictionary<IdPair, Edge> AddEdgesToExistingNodes(HashSet<NodeConnection> connections) 
{ 
    Dictionary<IdPair, Edge> resultSet = new Dictionary<IdPair, Edge>(connections.Count); 

    foreach (NodeConnection con in connections) 
    { 
    ... 
    resultSet.Add(nodeIdPair, newEdge); 
    } 

    return resultSet; 
} 

Trong các thử nghiệm của tôi, tôi chèn ~ 300k các mặt hàng. Tôi đã kiểm tra thời gian chạy với ANTS Performance Profiler và thấy rằng thời gian trung bình cho resultSet.Add (...) không thay đổi khi tôi khởi tạo từ điển với kích thước cần thiết. Nó giống như khi tôi khởi tạo từ điển với từ điển mới(); (trung bình khoảng 0.256 ms cho mỗi Add). Điều này chắc chắn là do số lượng dữ liệu trong Từ điển (ALTHOUGH Tôi đã khởi tạo nó với kích thước mong muốn). Đối với các mục 20k đầu tiên, thời gian trung bình cho Thêm là 0,03 ms cho mỗi mục.

Bất kỳ ý tưởng nào, cách làm cho hoạt động bổ sung nhanh hơn?

Cảm ơn trước, Frank

Đây là tôi IdPair-Struct:

public struct IdPair 
{ 
    public int id1; 
    public int id2; 

    public IdPair(int oneId, int anotherId) 
    { 
    if (oneId > anotherId) 
    { 
     id1 = anotherId; 
     id2 = oneId; 
    } 
    else if (anotherId > oneId) 
    { 
     id1 = oneId; 
     id2 = anotherId; 
    } 
    else 
     throw new ArgumentException("The two Ids of the IdPair can't have the same value."); 
    } 
} 

Answer 1

Vì bạn có một cấu trúc, bạn sẽ có được thực hiện mặc định của Equals() và GetHashCode(). Như những người khác đã chỉ ra, điều này không hiệu quả lắm vì nó sử dụng sự phản chiếu, nhưng tôi không nghĩ sự phản chiếu là vấn đề.

Đoán của tôi là mã băm của bạn được phân phối không đồng đều theo mặc định GetHashCode(), có thể xảy ra, ví dụ, nếu thực hiện mặc định trả về một XOR đơn giản của tất cả các thành viên (trong trường hợp đó băm (a, b) = = băm (b, a)). Tôi không thể tìm thấy bất kỳ tài liệu nào về cách ValueType.GetHashCode() được triển khai, nhưng hãy thử thêm

có thể tốt hơn.

Answer 2

IdPair là một struct, và bạn chưa ghi đè Equals hoặc GetHashCode. Điều này có nghĩa là việc thực hiện mặc định các phương thức đó sẽ được sử dụng.

Đối với các loại giá trị, việc triển khai mặc định Equals và GetHashCode sử dụng phản ánh, điều này có khả năng dẫn đến hiệu suất kém. Hãy thử cung cấp các phương pháp thực hiện của riêng bạn và xem điều đó có hữu ích không.

thực hiện đề nghị của tôi, nó có thể không được chính xác những gì bạn cần/muốn:

public struct IdPair : IEquatable<IdPair> 
{ 
    // ... 

    public override bool Equals(object obj) 
    { 
     if (obj is IdPair) 
      return Equals((IdPair)obj); 

     return false; 
    } 

    public bool Equals(IdPair other) 
    { 
     return id1.Equals(other.id1) 
      && id2.Equals(other.id2); 
    } 

    public override int GetHashCode() 
    { 
     unchecked 
     { 
      int hash = 269; 
      hash = (hash * 19) + id1.GetHashCode(); 
      hash = (hash * 19) + id2.GetHashCode(); 
      return hash; 
     } 
    } 
}