SortedDictionaryから私のキーに最も近いアイテムを取得するには？

Question

現在、特定の数字に対してSortedList<T,U>を超えるバイナリ検索を使用しています。存在しない場合は、代わりに最も近い下限のキー項目を取得します。

多くのことをやっているのは、inserting unsorted dataではかなり遅いことがわかりました。

SortedDictionaryと似たような処理をする方法はありますか、それともSortedListに固執すべきですか？

Answer 1

SortedList<K, V>は、新しい要素が追加されるたびに<=N要素を内部配列にシフトするため、データを挿入するときに実際には遅くなります。追加の複雑さはO(N)です。それにもかかわらず、それはO(log N)の正確な要素またはその近隣を見つけることを可能にするバイナリ検索をサポートします。

バランスのとれたバイナリツリーは、問題を解決するのに最適なデータ構造です。 あなたは対数複雑/ wの次の操作を行うことがことができるようになります。

1. O(log N)
2. 検索項目またはO(log N)
で最も近い内の項目を削除し SortedList<K, V>
3. にO(log N)対O(N)にアイテムを追加します

要素またはその最も近い下限をバイナリツリーで検索するのは単純です：

1. キーを見つけるためにルートから子へのツリーを縦方向に移動します。キー<の場合は左に、そうでない場合は右に移動します。あなたが鍵を見つけた場合は
2. 、返す
3. 鍵が見つからない場合は、最寄りの左の親は、あなたが探しているものになります（最寄りの下限）は、左の親がない場合
4. 、ちょうど訪問した最後を取りますノードでは、ツリー内の最小ノードです。

バイナリツリーの実装方法については、多くの記事があります。それにもかかわらず、私は一種のハックを使って.NET Frameworkコレクションを再利用しようとしています:)

今、私はあなたにSortedSet<T>を提示するつもりです。それ自体は赤黒の木です。 1つの欠点があります。最も近いノードをすばやく見つける機能はありません。しかし、私たちは木での検索のアルゴリズムを知っています（1で説明しています）。SortedSet<T>.Containsの方法で実装されています。今度は、カスタム比較者を使用して、トラバーサル中にルートから最後に訪問したノードまでのすべてのノードを取得できます。あなたが最も近いノードを見つけること、すなわちO(log 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; 
    } 
} 

：その後、私たちは、上記のアルゴリズムを使用して、最寄りの下限ノードを見つけることができます。したがって、これはあなたの問題に対する最速の解決策です。このコレクションは、SortedList<K, V>と同じくらい早く、最も近いもので、SortedSet<T>と同じくらい速いです。

SortedDictionary<K, V>について1つのことを除いて、ほとんどの場合、SortedSet<T>と同じです。各キーには値があります。私はあなたがSortedDictionary<K, V>と同じことをすることができることを願っています。

*逆コンパイルSortedSet<T>.Contains方法：

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