Partner China: прямая трасса от китайских производителей к российскому бизнесу 
Браво, граф Петр Толстой: о цене Макрона ломаного гроша не стоящего в 
Мiр театр, а люди в нём актёры 
И снова творческие японцы... 
Томас Крич — самый обаятельный маньяк США, которого не могут казнить 40 лет 
Грабли подоходного налога... 
Дом для понаехов 
ШОКОЛАДНОЕ ПЛАТЬЕ В СЛИВОЧНЫЙ ГОРОХ 
Солнечное затмение в Северной Америке Психологические консультации через интернет - это просто! Вы общаетесь с квалифицированным и опытным психологом не выходя из дома, по видеосвязи - Телеграму или Скайпу. Люди обращаются ко мне, чтобы понять самих себя и свое поведение, разобраться в том, что мешает им жить. Я не ставлю ...
Как мир перевернулся, или "В рот мне ноги, это же lower_bound!"
skiminog — 26.08.2010
Тут сегодня некто решил перевести на Хабре скучный пост с
перечислением фич нового контейнера SortedSet из .NET 4.0.
Увидел я его только к вечеру, поскольку весь день мотался по
городу. Пролистнул, ничего особенного вроде не обнаружил (в конце
концов, что я не знаю про их дерево и его внешний интерфейс?),
хотел было уже закрывать, как тут глаз зацепился за название метода
GetViewBetween.Видимо, когда я сразу после выхода .NET 4 просматривал спеки MSDN, я его как-то картинно и красиво
Ценная строчка в документации указала, что класс хранится в сборке System.dll. Лезем в папку с фреймворком, открываем сборку Рефлектором, прокручиваем до нужного класса и нужного метода. Далее - серия code snippet`ов: как я в поисках истинной реализации прыгал от метода к методу:
public
virtual
SortedSet<T> GetViewBetween(T lowerValue, T upperValue)
{
if (this.Comparer.Compare(lowerValue, upperValue) > 0)
{
throw new ArgumentException("lowerBound is greater than upperBound");
}
return new TreeSubSet<T>((SortedSet<T>) this, lowerValue, upperValue, true, true);
}
{
if (this.Comparer.Compare(lowerValue, upperValue) > 0)
{
throw new ArgumentException("lowerBound is greater than upperBound");
}
return new TreeSubSet<T>((SortedSet<T>) this, lowerValue, upperValue, true, true);
}
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;
base.root = this.underlying.FindRange(this.min, this.max, this.lBoundActive, this.uBoundActive);
base.count = 0;
base.version = -1;
this.VersionCheckImpl();
}
{
this.underlying = Underlying;
this.min = Min;
this.max = Max;
this.lBoundActive = lowerBoundActive;
this.uBoundActive = upperBoundActive;
base.root = this.underlying.FindRange(this.min, this.max, this.lBoundActive, this.uBoundActive);
base.count = 0;
base.version = -1;
this.VersionCheckImpl();
}
internal
Node<T> FindRange(T from, T to,
bool
lowerBoundActive, bool
upperBoundActive)
{
Node<T> root = this.root;
while (root != null)
{
if (lowerBoundActive && (this.comparer.Compare(from, root.Item) > 0))
{
root = root.Right;
}
else
{
if (upperBoundActive && (this.comparer.Compare(to, root.Item) < 0))
{
root = root.Left;
continue;
}
return root;
}
}
return null;
}
{
Node<T> root = this.root;
while (root != null)
{
if (lowerBoundActive && (this.comparer.Compare(from, root.Item) > 0))
{
root = root.Right;
}
else
{
if (upperBoundActive && (this.comparer.Compare(to, root.Item) < 0))
{
root = root.Left;
continue;
}
return root;
}
}
return null;
}
Все, приехали. Очевидный проход по дереву за O(H). Поскольку дерево у них там внутри сбалансированное (красно-черное, если конкретнее) - за O(log N).
Подводя итоги: неужели я таки дожил до этого священного дня, когда в стандартной библиотеке .NET появился lower_bound на set`ах? Учитывая, что BigInteger там тоже уже имеется, остается только пожелать для полного счастья next_permutation. Ну и какой-нибудь там nth_element на закуску.
Только вот ведь блин, нет этого .NET 4 нигде. Ни на одном контесте :(
Оставить комментарий
Популярные посты:
Архив записей в блогах:
оч интересно, а что бы вы сделали, если бы в ваш ресторан зашла сьемочная группа с сан книжками, переоделась бы в спец одежду и без лишних слов направилась на кухню... снимать оттуда репортаж? я передачу ту ни разу не видела (не могу смотреть наше говно тв), но может кто застал случаем. ...
Вчера, неожиданно, воскресенье мне сделало неимоверный подарок и в Москву приехали мои лучшие друзья Ира и Денис, из Энска, по делам, на пару дней. Они являются героями нескольких моих предыдущих историй, но сейчас для ...
А.И. Медведев: «С «Динамо» ситуация такая. За четыре сезона спонсоры ...
Результаты конкурса на самого активного комментатора за эту неделю уже известны. По традиции три самых активных комментатора будут уютно располагаться в моем верхнем посте ! Показана статистика с 2012/03/25 18:47 1 livejournal 553 (25.07%) 2 ...
