☰

なぜSortedSetなのか .GetViewBetween は O(log N) ではないですか? 質問する

tag-icon • tag-icon c# .net complexity-theory sortedset
なぜSortedSetなのか .GetViewBetween は O(log N) ではないですか? 質問する

.NET 4.0+ では、クラスにSortedSet<T>というメソッドがありGetViewBetween(l, r)、指定された 2 つの値の間にあるすべての値を含むツリー部分のインターフェイス ビューを返します。 がSortedSet<T>赤黒木として実装されていることを考えると、当然、O(log N)時間内に実行されることが予想されます。 C++ の同様のメソッドは でstd::set::lower_bound/upper_bound、Java では でありTreeSet.headSet/tailSet、これらは対数です。

しかし、それは真実ではありません。次のコードは 32 秒で実行されますが、同等のO(log N)バージョンではGetViewBetweenこのコードは 1 ～ 2 秒で実行されます。

var s = new SortedSet<int>();
int n = 100000;
var rand = new Random(1000000007);
int sum = 0;
for (int i = 0; i < n; ++i) {
    s.Add(rand.Next());
    if (rand.Next() % 2 == 0) {
        int l = rand.Next(int.MaxValue / 2 - 10);
        int r = l + rand.Next(int.MaxValue / 2 - 10);
        var t = s.GetViewBetween(l, r);
        sum += t.Min;
    }
}
Console.WriteLine(sum);

System.dllを逆コンパイルしましたドットピークそして私が得たものは次のとおりです:

public TreeSubSet(SortedSet<T> Underlying, T Min, T Max, bool lowerBoundActive, bool upperBoundActive)
    : base(Underlying.Comparer)
{
    this.underlying = Underlying;
    this.min = Min;
    this.max = Max;
    this.lBoundActive = lowerBoundActive;
    this.uBoundActive = upperBoundActive;
    this.root = this.underlying.FindRange(this.min, this.max, this.lBoundActive, this.uBoundActive);
    this.count = 0;
    this.version = -1;
    this.VersionCheckImpl();
}

internal SortedSet<T>.Node FindRange(T from, T to, bool lowerBoundActive, bool upperBoundActive)
{
  SortedSet<T>.Node node = this.root;
  while (node != null)
  {
    if (lowerBoundActive && this.comparer.Compare(from, node.Item) > 0)
    {
      node = node.Right;
    }
    else
    {
      if (!upperBoundActive || this.comparer.Compare(to, node.Item) >= 0)
        return node;
      node = node.Left;
    }
  }
  return (SortedSet<T>.Node) null;
}

private void VersionCheckImpl()
{
    if (this.version == this.underlying.version)
      return;
    this.root = this.underlying.FindRange(this.min, this.max, this.lBoundActive, this.uBoundActive);
    this.version = this.underlying.version;
    this.count = 0;
    base.InOrderTreeWalk((TreeWalkPredicate<T>) (n =>
    {
      SortedSet<T>.TreeSubSet temp_31 = this;
      int temp_34 = temp_31.count + 1;
      temp_31.count = temp_34;
      return true;
    }));
}

したがって、FindRangeは明らかに ですO(log N)が、その後、VersionCheckImpl... を呼び出します。これは、見つかったサブツリーのノードを再カウントするためだけに、線形時間でトラバーサルを実行します。

  1. なぜ常にそのトラバーサルを実行する必要があるのでしょうか?
  2. O(log N)なぜ.NETにはC++やJavaのようにキーに基づいてツリーを分割するメソッドが含まれていないのでしょうか？本当に多くの状況で役立ちます。

ベストアンサー1

versionフィールドについて

更新1:

私の記憶では、BCL の多くの (おそらくすべての?) コレクションにはフィールドがありますversion。

まず、についてforeach：

これによればmsdn リンク

foreach ステートメントは、配列またはオブジェクト コレクション内の各要素に対して、埋め込みステートメントのグループを繰り返します。 foreach ステートメントは、コレクションを反復処理して必要な情報を取得するために使用されますが、予期しない副作用を回避するために、コレクションの内容を変更するために使用しないでください。

他の多くのコレクションでは、versionデータは保護されており、foreach

たとえばHashTable：MoveNext()​

public virtual bool MoveNext()
{
    if (this.version != this.hashtable.version)
    {
        throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EnumFailedVersion"));
    }
    //..........
}

しかし、SortedSet<T>のMoveNext()方法では次のようになります。

public bool MoveNext()
{
    this.tree.VersionCheck();
    if (this.version != this.tree.version)
    {
        ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
    }       
    //....
}

更新2：

しかし、O(N) ループは、 だけでなくversion、 プロパティ に対しても有効である可能性がありますCount。

なぜならGetViewBetween の MSDN言った：

このメソッドは、比較子によって定義された lowerValue と upperValue の間にある要素の範囲のビューを返します。ビューと基になるSortedSet(Of T)の両方に変更を加えることができます。。

そのため、更新のたびにフィールドを同期する必要があります（キーと値は既に同じです）。正しいことcountを確認するにはCount

目標を達成するためのポリシーは 2 つありました。

  1. マイクロソフトの
  2. モノの

まず、MS は、そのコード内でGetViewBetween()のパフォーマンスを犠牲にして、Countプロパティのパフォーマンスを獲得します。

VersionCheckImpl()プロパティを同期する 1 つの方法ですCount。

2 番目は Mono です。Mono のコードではGetViewBetween()高速ですが、そのGetCount()方法では:

internal override int GetCount ()
{
    int count = 0;
    using (var e = set.tree.GetSuffixEnumerator (lower)) {
        while (e.MoveNext () && set.helper.Compare (upper, e.Current) >= 0)
            ++count;
    }
    return count;
}

常に O(N) 操作です。

おすすめ記事