c# - 为什么 SortedSet<T>.GetViewBetween 不是 O(log N)？

Question

在 .NET 4.0+ 中，类 SortedSet<T>有一个方法叫做 GetViewBetween(l, r) ，它返回树部分的接口(interface) View ，其中包含两个指定值之间的所有值。鉴于 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);

我使用 dotPeek 反编译了 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. 为什么 .NET 不包含 O(log N)基于键拆分树的方法，如 C++ 或 Java？它在很多情况下真的很有帮助。

Answer 1

关于 version领域

更新1:

在我的内存中，BCL 中的很多(也许是全部？)集合都有字段 version .

首先，关于foreach :

根据这个msdn link

The foreach statement repeats a group of embedded statements for each element in an array or an object collection. The foreach statement is used to iterate through the collection to get the desired information, but should not be used to change the contents of the collection to avoid unpredictable side effects.

在许多其他收藏中，version protected 数据在 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属性(property)。

因为 MSDN of GetViewBetween说:

This method returns a view of the range of elements that fall between lowerValue and upperValue, as defined by the comparer .... You can make changes in both the view and in the underlying SortedSet(Of T).

所以每次更新都应该同步count字段(键和值已经相同)。确保 Count是正确的

实现目标有两个策略:

1. 微软的
2. 单声道

首先，MS 在他们的代码中牺牲了 GetViewBetween()的表现并赢得Count属性的性能。

VersionCheckImpl()是同步 Count 的一种方法属性(property)。

其次，单声道。在单声道代码中，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) 操作!