8

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

私がよく行っているソートされていないデータの挿入がかなり遅いことがわかりました。

で同様のことを行う方法はありますSortedDictionaryかSortedList?

4

1 に答える 1

14

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

バランスのとれた二分木は、問題を解決するのに最適なデータ構造です。対数の複雑さで次の操作を実行できます。

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

二分木で要素またはその最も近い下限を探すのは簡単です。

  1. キーを見つけるために、ツリーをルートから子に垂直に移動します。キー < ノードの場合は左の子に移動し、そうでない場合は右の子に移動します。
  2. 鍵を見つけたら、戻ってください
  3. キーが見つからない場合、最も近い左の親が探しているものになります (最も近い下限)
  4. 左の親がない場合は、最後にアクセスしたノードを取得します。これはツリー内の最小ノードです。

二分木を実装する方法を説明する記事はたくさんあります。それにもかかわらず、一種のハックを使用して .NET Framework コレクションを再利用します :)

SortedSet<T>では、赤黒木そのものを紹介します。これには欠点が 1 つあります。最も近いノードをすばやく見つける機能がありません。しかし、ツリーでの検索のアルゴリズムはわかっており (1. で説明)、SortedSet<T>.Containsメソッドで実装されています (一番下で逆コンパイル*)。これで、カスタム比較子を使用して、トラバーサル中にルートから最後にアクセスしたノードまでのすべてのノードをキャプチャできます。その後、上記のアルゴリズムを使用して、最も近い下限ノードを見つけることができます。

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

最も近いノードを見つけるのに、通常の検索以上の時間がかからないことがわかりますO(log N)。したがって、これが問題の最速の解決策です。このコレクションは、SortedList<K, V>最も近いものを見つけるのと同じくらい速くSortedSet<T>、さらに追加するのと同じくらい高速です。

どうSortedDictionary<K, V>ですか？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;
}
于 2012-07-27T21:45:58.913 に答える