Cách lấy mục gần nhất với khóa của tôi từ SortedDictionary?

Question

Hiện tại tôi đang sử dụng tìm kiếm nhị phân trên SortedList<T,U> cho một số cụ thể và nếu nó không tồn tại, tôi sẽ thay thế khóa có giới hạn dưới gần nhất.

Tôi thấy rằng nó khá chậm trong inserting unsorted data mà tôi đang làm rất nhiều.

Có cách nào để thực hiện điều gì đó tương tự với SortedDictionary hay tôi chỉ nên gắn vào SortedList của mình?

Answer 1

SortedList<K, V> thực sự chậm khi chèn dữ liệu khi nó thay đổi <=N phần tử trong mảng nội bộ mỗi lần thêm phần tử mới. Độ phức tạp của việc bổ sung là O(N). Tuy nhiên nó hỗ trợ tìm kiếm nhị phân cho phép tìm phần tử chính xác hoặc hàng xóm của nó trong O(log N).

Cây nhị phân cân bằng là cấu trúc dữ liệu tốt nhất để giải quyết vấn đề của bạn. Bạn sẽ có thể thực hiện các tác sau w/logarit phức tạp:

1. Thêm mục trong O(log N) vs O(N) trong SortedList<K, V>
2. Remove mục trong mục O(log N)
3. Tìm kiếm hoặc nó gần nhất trong O(log N)

Tìm kiếm phần tử hoặc giới hạn dưới gần nhất trong cây nhị phân rất đơn giản:

1. Đi theo chiều dọc qua cây từ gốc sang con để tìm khóa của bạn. Nếu phím < nút, sau đó đi đến con trái, nếu không đến một trong những quyền.
2. Nếu bạn tìm thấy chìa khóa, trở
3. Nếu không tìm thấy chìa khóa, cha mẹ trái gần sẽ là một trong những bạn đang tìm kiếm (gần nhất thấp-bound)
4. Nếu không có cha mẹ bên trái, chỉ cần đi thăm cuối cùng nút, nó là nút tối thiểu trong cây.

Có nhiều bài viết mô tả cách triển khai cây nhị phân. Tuy nhiên tôi sẽ sử dụng lại bộ sưu tập .NET Framework bằng cách sử dụng một loại hack :)

Bây giờ, tôi sẽ giới thiệu cho bạn SortedSet<T> mà chính nó là cây đỏ đen. Nó có một nhược điểm, nó không có khả năng tìm thấy các nút gần nhất một cách nhanh chóng. Nhưng chúng ta biết thuật toán tìm kiếm trong cây (nó được mô tả trong 1.) và nó được thực hiện trong phương thức SortedSet<T>.Contains (được biên dịch ở phía dưới *). Bây giờ chúng ta có thể nắm bắt tất cả các nút từ gốc đến nút được truy cập cuối cùng trong quá trình truyền tải bằng cách sử dụng trình so sánh tùy chỉnh của chúng tôi. Sau đó chúng ta có thể tìm thấy khu vực gần nút thấp-bound sử dụng thuật toán trên:

public class LowerBoundSortedSet<T> : SortedSet<T> { 

    private ComparerDecorator<T> _comparerDecorator; 

    private class ComparerDecorator<T> : IComparer<T> { 

     private IComparer<T> _comparer; 

     public T LowerBound { get; private set; } 

     private bool _reset = true; 

     public void Reset() 
     { 
      _reset = true; 
     } 

     public ComparerDecorator(IComparer<T> comparer) 
     { 
      _comparer = comparer; 
     } 

     public int Compare(T x, T y) 
     { 
      int num = _comparer.Compare(x, y); 
      if (_reset) 
      { 
       LowerBound = y; 
      } 
      if (num >= 0) 
      { 
       LowerBound = y; 
       _reset = false; 
      } 
      return num; 
     } 
    } 

    public LowerBoundSortedSet() 
     : this(Comparer<T>.Default) {} 

    public LowerBoundSortedSet(IComparer<T> comparer) 
     : base(new ComparerDecorator<T>(comparer)) { 
     _comparerDecorator = (ComparerDecorator<T>)this.Comparer; 
    } 

    public T FindLowerBound(T key) 
    { 
     _comparerDecorator.Reset(); 
     this.Contains<T>(key); 
     return _comparerDecorator.LowerBound; 
    } 
} 

Bạn thấy rằng việc tìm kiếm nút gần mất không quá tìm kiếm thông thường, ví dụ: O(log N). Vì vậy, đây là giải pháp nhanh nhất cho vấn đề của bạn. Bộ sưu tập này nhanh như SortedList<K, V> trong việc tìm kiếm gần nhất và nhanh như SortedSet<T> ngoài ra.

Còn khoảng SortedDictionary<K, V> thì sao? Nó gần như giống như SortedSet<T> ngoại trừ một điều: mỗi khóa có một giá trị. Tôi hy vọng bạn sẽ có thể làm tương tự với SortedDictionary<K, V>.

* decompiled SortedSet<T>.Contains phương pháp:

public virtual bool Contains(T item) 
{ 
    return this.FindNode(item) != null; 
} 

internal virtual SortedSet<T>.Node FindNode(T item) 
{ 
    for (SortedSet<T>.Node node = this.root; node != null; { 
    int num; 
    node = num < 0 ? node.Left : node.Right; 
    } 
) 
    { 
    num = this.comparer.Compare(item, node.Item); 
    if (num == 0) 
     return node; 
    } 
    return (SortedSet<T>.Node) null; 
}