Подтвердить что ты не робот

Почему SortedSet <T>.GetViewBetween не O (log N)?

В .NET 4.0+ класс SortedSet<T> имеет метод под названием GetViewBetween(l, r), который возвращает вид интерфейса на части дерева, содержащей все значения между указанными двумя. Учитывая, что SortedSet<T> реализуется как красно-черное дерево, я, естественно, ожидаю, что он запустится в O(log N). Аналогичный метод в С++ - это 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) для разделения дерева на основе ключа, например С++ или Java? Это действительно полезно во многих ситуациях.
4b9b3361

ОТВЕТЫ

Ответ 1

о поле version

Update1:

В моей памяти много (возможно, все?) коллекций в BCL имеют поле version.

Во-первых, около foreach:

в соответствии с этим msdn link

Оператор 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.

Поскольку MSDN из GetViewBetween сказал:

Этот метод возвращает представление диапазона элементов, которые находятся между lowerValue и upperValue, как определено компаратором.... Вы можете вносить изменения как в представление, так и в базовый SortedSet (Of T).

Поэтому для каждого обновления необходимо синхронизировать поле Count (ключ и значение уже такие же). Чтобы убедиться в правильности Count

Для достижения цели были две политики:

  • от Microsoft
  • Моно

First.MS, в своем коде, жертвуют производительностью GetViewBetween() и выигрывают производительность Count Property.

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