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

Question

在.NET 4.0+中,类SortedSet<T>有一个名为的方法GetViewBetween(l, r),它返回树部件上的接口视图,其中包含指定的两个之间的所有值.鉴于它SortedSet<T>是作为红黑树实现的,我自然希望它能够及时运行O(log N).C++中的类似方法是std::set::lower_bound/upper_boundJava 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领域

UPDATE1:

在我的记忆中,BCL中的很多(可能是所有？)集合都有这个领域version.

首先,关于foreach:

根据这个msdn链接

foreach语句为数组或对象集合中的每个元素重复一组嵌入式语句.foreach语句用于迭代集合以获取所需信息,但不应用于更改集合的内容以避免不可预测的副作用.

在许多其他集合中,version受保护的数据在此期间不会被修改foreach

例如,HashTable's 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);
    }       
    ....
}

UPDATE2:

但是O(N)循环不仅version可以用于Count属性,也可以用于属性.

因为GetViewBetween的MSDN说:

此方法返回lowerValue和upperValue之间的元素范围视图,由comparer ....定义.您可以在视图和底层SortedSet(Of T)中进行更改.

因此,对于每次更新,它应该是同步count字段(键和值已经相同).确保Count正确无误

有两项政策可以实现目标:

1. 微软的
2. Mono的

First.MS,在他们的代码中,他们牺牲了GetViewBetween()性能并赢得了CountProperty的表现.

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

二,单声道.在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)操作!

Answer 2

万一像我这样的人在问题提出 10 年后回来。 https://github.com/dotnet/runtime/blob/fae7ee8e7e3aa7f86836318a10ed676641e813ad/src/libraries/System.Collections/src/System/Collections/Generic/SortedSet.TreeSubSet.cs#L38 这是 TreeSubSet 实现的链接，似乎对 VersionCheckImpl() 的调用已被删除。

所以我想现在你可以这样做：

SortedSet<int> ss = new();
ss.Add(1);
ss.Add(2);
//ss.Add(3);
ss.Add(4);
ss.Add(5);
ss.Add(6);
var four = ss.GetViewBetween(3, ss.Max()).First();

在 O(logn) 中