Pourquoi SortedSet<T>.GetViewBetween n'est pas O(log N) ?

Question

Dans .NET 4.0+, une classe SortedSet<T> a une méthode appelée GetViewBetween(l, r) qui renvoie une vue d'interface sur une partie d'arbre contenant toutes les valeurs entre les deux spécifiées. Étant donné que SortedSet<T> est implémenté comme un arbre rouge-noir, je m'attends naturellement à ce qu'il s'exécute en O(log N) temps. La méthode similaire en C++ est std::set::lower_bound/upper_bound en Java, c'est TreeSet.headSet/tailSet et ils sont logarithmiques.

Or, ce n'est pas vrai. Le code suivant s'exécute en 32 sec, alors que l'équivalent O(log N) version de GetViewBetween permettrait à ce code de s'exécuter en 1 ou 2 secondes.

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

J'ai décompilé System.dll en utilisant dotPeek et voilà ce que j'ai obtenu :

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

Donc, FindRange est évidemment O(log N) mais après cela, nous appelons VersionCheckImpl ... qui effectue une traversée en temps linéaire du sous-arbre trouvé uniquement pour recompter ses nœuds !

1. Pourquoi auriez-vous besoin de faire cette traversée tout le temps ?
2. Pourquoi .NET ne contient pas de O(log N) méthode pour diviser un arbre en fonction de la clé, comme C++ ou Java ? C'est vraiment utile dans de nombreuses situations.

Answer 1

Sur le version champ

UPDATE1 :

De mémoire, beaucoup (peut-être toutes ?) les collections de la BCL ont le champ version .

D'abord, à propos foreach :

selon ce qui suit lien msdn

L'instruction foreach répète un groupe d'instructions intégrées pour chaque élément d'un tableau ou d'une collection d'objets. L'instruction foreach est utilisée pour itérer dans la collection afin d'obtenir les informations souhaitées, mais ne doit pas être utilisée pour modifier le contenu de la collection afin d'éviter des effets secondaires imprévisibles.

Dans de nombreuses autres collections, version est protégé, les données ne sont pas modifiées pendant le foreach

Par exemple, HashTable 's MoveNext() :

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

Mais dans le SortedSet<T> 's MoveNext() méthode :

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

UPDATE2

Mais la boucle O(N) n'est peut-être pas seulement pour version mais aussi pour le Count propriété.

Parce que le MSDN de GetViewBetween a dit :

Cette méthode renvoie une vue de la gamme d'éléments qui se situent entre la valeur inférieure et la valeur supérieure, comme défini par le comparateur ..... Vous pouvez apporter des modifications à la fois dans la vue et dans le SortedSet(Of T) sous-jacent. .

Donc, pour chaque mise à jour, il faudrait synchroniser le fichier count (la clé et la valeur sont déjà identiques). Pour s'assurer que le Count est correct

Il y avait deux politiques pour atteindre l'objectif :

1. Microsoft
2. Mono's

D'abord, les MS, dans leur code, ils sacrifient les GetViewBetween() et de remporter le Count la performance de la propriété.

VersionCheckImpl() est un moyen de synchroniser le Count propriété.

Deuxièmement, Mono. Dans le code de Mono, GetViewBetween() est plus rapide, mais dans leur GetCount() méthode :

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

C'est toujours une opération O(N) !

Answer 2

Au cas où quelqu'un d'autre comme moi reviendrait 10 ans après que la question ait été posée. https://github.com/dotnet/runtime/blob/fae7ee8e7e3aa7f86836318a10ed676641e813ad/src/libraries/System.Collections/src/System/Collections/Generic/SortedSet.TreeSubSet.cs#L38 Voici le lien vers l'implémentation de TreeSubSet, et il semble que l'appel à VersionCheckImpl() ait été supprimé.

Donc je suppose que maintenant tu peux faire :

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

en O(logn)