Почему SortedSet <T>.GetViewBetween не является O (log N)? - PullRequest
Новая
       40

Почему SortedSet <T>.GetViewBetween не является O (log N)?

65 голосов
/ 24 марта 2012

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

  1. Зачем вам все время делать этот обход?
  2. Почему .NET не содержит O(log N) метода для разбиения дерева на основе ключей, такого как C ++ или Java? Это действительно полезно во многих ситуациях.

1 Ответ

19 голосов
/ 30 марта 2012

о version поле

Update1:

В моей памяти у многих (может быть, всех?) Коллекций в BCL есть поле version.

Сначала о foreach:

в соответствии с этой ссылкой MSDN

Оператор 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 правильный

Существовали две политики для достижения цели:

  1. от Microsoft
  2. Моно

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

...