c# - ¿Por qué SortedSet<T>.GetViewBetween no es O(log N)?

.net complexity-theory

Question

En .NET 4.0+, una clase SortedSet<T> tiene un método llamado GetViewBetween(l, r) , que devuelve una vista de interfaz en una parte de árbol que contiene todos los valores entre los dos especificados. Dado que SortedSet<T> se implementa como un árbol rojo-negro, naturalmente espero que se ejecute en el tiempo O(log N) . El método similar en C ++ es std::set::lower_bound/upper_bound , en Java es TreeSet.headSet/tailSet , y son logarítmicos.

Sin embargo, eso no es verdad. El siguiente código se ejecuta en 32 segundos, mientras que la versión equivalente de O(log N) de GetViewBetween haría que este código se ejecute 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 obviamente O(log N) , pero después de eso llamamos a VersionCheckImpl ... que hace un recorrido en tiempo lineal del subárbol encontrado solo para contar sus nodos.

1. ¿Por qué tendrías que hacer ese recorrido todo el tiempo?
2. ¿Por qué .NET no contiene un método O(log N) para dividir un árbol basado en la clave, como C ++ o Java? Es realmente útil en muchas situaciones.

Answer 1

sobre el campo de version

ACTUALIZACIÓN1:

En mi memoria, muchas (tal vez ¿todas?) Colecciones en BCL tienen la version campo.

Primero, sobre foreach :

de acuerdo con este enlace msdn

La instrucción foreach repite un grupo de instrucciones incrustadas para cada elemento en una matriz o colección de objetos. La instrucción foreach se usa para recorrer la colección para obtener la información deseada, pero no debe usarse para cambiar los contenidos de la colección y evitar efectos secundarios impredecibles.

En muchas otras colecciones, la version está protegida, los datos no se modifican durante el foreach

Por ejemplo, MoveNext() HashTable MoveNext() :

public virtual bool MoveNext()
{
    if (this.version != this.hashtable.version)
    {
        throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EnumFailedVersion"));
    }
    ..........
}

Pero en el en el SortedSet<T> MoveNext() SortedSet<T> :

public bool MoveNext()
{
    this.tree.VersionCheck();
    if (this.version != this.tree.version)
    {
        ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
    }       
    ....
}

ACTUALIZACIÓN2:

Pero el bucle O (N) tal vez no solo sea para la version sino también para la propiedad Count .

Porque el MSDN de GetViewBetween decía:

Este método devuelve una vista del rango de elementos que se encuentran entre lowerValue y upperValue, tal como lo define el comparador ... Puede hacer cambios tanto en la vista como en el SortedSet subyacente (Of T) .

Por lo tanto, para cada actualización, debe sincronizar el campo de count (la clave y el valor ya son los mismos). Para asegurarse de que el Count sea ​​correcto

Hubo dos políticas para alcanzar el objetivo:

1. Microsoft
2. Mono

First.MS, en su código, sacrifican el GetViewBetween() y ganan el rendimiento de Count Property.

VersionCheckImpl() es una forma de sincronizar la propiedad Count .

Segundo, Mono. En el código mono, GetViewBetween() es más rápido, pero en su método 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;
}

¡Siempre es una operación O (N)!