为什么SortedSet<T>.GetViewBetween不是O(log )？
在.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秒内运行，而等效的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解压缩了dotPeek，下面是我得到的：
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++或C++？在很多情况下，这真的很有帮助。
回答 2
Stack Overflow用户
发布于 2012-03-30 03:44:30
关于version字段
UPDATE1：
在我的记忆中，有很多(也许全部？)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);
}
//....
}UPDATE2：
但是O(N)循环不仅适用于version，也适用于Count性质。
此方法返回由比较器定义的lowerValue和upperValue之间元素范围的视图.--您可以在视图和底层SortedSet(Of T)中进行更改。
因此，对于每次更新，它都应该同步count字段(键和值已经相同)。以确保Count是正确的
实现这一目标有两项政策：
- 微软的
- 莫诺氏
首先，MS在代码中牺牲了GetViewBetween()的性能，赢得了Count属性的性能。
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)操作！
Stack Overflow用户
发布于 2022-06-10 20:25:00
如果像我这样的人在问题被问了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)中
https://stackoverflow.com/questions/9850975
复制相似问题
腾讯云开发者
