为什么 SortedSet < T > . GetViewbetween 不是 O (logN) ？

进去。NET 4.0 + 中，类 SortedSet<T>有一个名为 GetViewBetween(l, r)的方法，该方法返回树部分的接口视图，该视图包含两个指定值之间的所有值。鉴于 SortedSet<T>是以红黑树的形式实现的，我自然希望它在 O(log N)时间内运行。C + + 中类似的方法是 std::set::lower_bound/upper_bound，Java 中是 TreeSet.headSet/tailSet，它们是对数的。

然而，事实并非如此。下面的代码运行时间为32秒，而相当于 GetViewBetween的 O(log N)版本的代码运行时间为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... ... 它对找到的子树进行线性时间遍历，只是为了重新计算它的节点！

为什么要一直做这个遍历呢？
为什么。NET 不包含一个 O(log N)方法，用于基于键分割树，如 C + + 或 Java？真的在很多情况下都很有用。

6489

小开

最佳答案

关于 `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性质。

因为之间的 MSDN说:

此方法返回由比较器... 定义的、介于 lowerValue 和 upperValue 之间的元素范围的视图。可以在视图和基础 SortedSet (Of T)中进行更改.

因此，对于每次更新，应该同步 count字段(键和值已经相同)。确保 Count是正确的

实现这一目标有两项政策:

微软的
单核细胞增多症

首先，MS 的，在他们的代码，他们牺牲的 GetViewBetween()的性能和赢得的 Count属性的性能。

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

第二，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)操作！

为什么 SortedSet < T > . GetViewbetween 不是 O (logN) ？

关于 version字段

更新1:

首先，关于 foreach:

更新2:

关于 `version`字段

首先，关于 `foreach`: