Pourquoi SortedSet .GetViewBetween n’est pas O (log N)?

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

Cependant, ce n’est pas vrai. Le code suivant s’exécute en 32 secondes, alors que la version équivalente O(log N) de GetViewBetween rendrait ce code s’exécuter en 1-2 secondes.

 var s = new SortedSet(); 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 voici ce que j’ai:

 public TreeSubSet(SortedSet 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.Node FindRange(T from, T to, bool lowerBoundActive, bool upperBoundActive) { SortedSet.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.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) (n => { SortedSet.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 ensuite nous appelons VersionCheckImpl … qui effectue un parcours 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 méthode O(log N) pour fractionner une arborescence basée sur des clés, comme C ++ ou Java? C’est vraiment utile dans beaucoup de situations.

à propos du champ version

UPDATE1:

Dans ma mémoire, beaucoup de collections (peut-être toutes?) De BCL ont la version terrain.

Tout d’abord, à propos de foreach :

selon ce lien msdn

L’instruction foreach répète un groupe d’instructions incorporées pour chaque élément d’un tableau ou d’une collection d’objects. L’instruction foreach est utilisée pour parcourir 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, la version est protégée, les données ne sont pas modifiées lors de la foreach

Par exemple, MoveNext() :

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

Mais dans la méthode MoveNext() SortedSet :

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

UPDATE2:

Mais la boucle O (N) ne concerne peut-être pas uniquement la version mais aussi la propriété Count .

Parce que le MSDN de GetViewBetween dit:

Cette méthode renvoie une vue de la plage d’éléments compris entre lowerValue et upperValue, tels que définis 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 faut synchroniser le champ count (la clé et la valeur sont déjà identiques). Pour vous assurer que le Count est correct

Il y avait deux politiques pour atteindre la cible:

  1. Microsoft’s
  2. Mono’s

First.MS, dans leur code, sacrifient les GetViewBetween() et gagne les performances de la propriété Count .

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

Deuxièmement, Mono. En code mono, GetViewBetween() est plus rapide, mais dans leur méthode 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; } 

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