In .NET 4.0+, una claseSortedSet<T> tiene un método llamadoGetViewBetween(l, r), que devuelve una vista de interfaz en una parte del árbol que contiene todos los valores entre los dos especificados. Dado queSortedSet<T> se implementa como un árbol rojo-negro, naturalmente espero que se ejecute enO(log N) hora. El método similar en C ++ esstd::set::lower_bound/upper_bound, en Java esTreeSet.headSet/tailSet, y son logarítmicos.

Sin embargo, eso no es cierto. El siguiente código se ejecuta en 32 segundos, mientras que el equivalenteO(log N) versión deGetViewBetween haría que este código se ejecutara en 1-2 segundos.

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);

Descompilé System.dll usando dotPeek y esto es lo que obtuve:

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;
    }));
}

Entonces,FindRange es obviamenteO(log N), pero después de eso llamamosVersionCheckImpl ... que hace un recorrido en tiempo lineal del subárbol encontrado solo para volver a contar sus nodos!

¿Por qué necesitarías hacer ese recorrido todo el tiempo?Por qué .NET no contiene unaO(log N) método para dividir un árbol basado en la clave, como C ++ o Java? EsDe Verda útil en muchas situaciones.