Re[3]: [CodeJam] UpperBound/LowerBound - оно чего вообще делает?
От: Evgeny.Panasyuk Россия  
Дата: 19.07.16 19:23
Оценка: 44 (1) +2
Здравствуйте, Sinix, Вы писали:

EP>>В STL используются "left-closed, right open" диапазоны. То есть два итератора (индекса) first, second задают диапазон [tt][first, second

S>Дак выяснили, обсудили и закрыли тему уже
S>У нас проблема в следующем: проект не на плюсах, целевая аудитория привыкла, что API проектируется так, чтобы его было удобно использовать без чтения документации.

Читать придётся при любом интерфейсе бинарного поиска. Использовать его не приходя в сознание не получится.
Вот например List<T>.BinarySearch:

https://msdn.microsoft.com/ru-ru/library/w4e7fxsh(v=vs.110).aspx
The zero-based index of item in the sorted List<T>, if item is found; otherwise, a negative number that is the bitwise complement of the index of the next element that is larger than item or, if there is no larger element, the bitwise complement of Count.
...
If the List<T> contains more than one element with the same value, the method returns only one of the occurrences, and it might return any one of the occurrences, not necessarily the first one.

Это как-нибудь можно было вывести без чтения документации?

S>С этой точки зрения lower и upper bounds у нас вышли фейлом, но все прочие варианты, судя по обсуждению, заметно хуже.


Безотносительно языков, partition_point, lower_bound и upper_bound имеют лучший интерфейс и чёткую семантику бинарного поиска.
Без всякой мути а-ля "it might return any one of the occurrences, not necessarily the first one", подобное кстати есть и в C'ишном bsearch — то есть на них даже пример с поиском бажной ревизии нормально не реализуем.

S>И в итоге выбор у нас получается такой: или вот такой вот компромисс, или вообще убирать методы. Т.е. вот такой вот компромисс


Убрать полезные методы только потому что есть те кто не читает документацию?
Re[9]: [CodeJam] UpperBound/LowerBound - оно чего вообще делает?
От: Lexey Россия  
Дата: 23.04.16 22:21
Оценка: 34 (1) +1
Здравствуйте, Sinix, Вы писали:

L>>FindNotLess/FindGreater/FindEqualRange/FindToWhere?

L>>или
L>>LocateNotLess/LocateGreater/LocateEqualRange/LocateFalse

S>Не, эт не совсем то что надо получается. Название должно отражать "что метод делает" в смысле "какие проблемы он решает", т.е. подсказывать подразумеваемые сценарии использования. Весь фреймворк на этом построен — 99% кода не требуют чтения документации, она и так есть — в самом коде.


Так они и отражают. Решаемые низкоуровневые проблемы: поиск не меньшего/поиск большего/поиск эквивалентных/поиск места смены значения предиката на false. Это ведь строительные блоки, на которых потом строятся более высокоуровневые решения.

S>А если под "что метод делает" понимать "что у метода внутри", то получается вот что: Ну ок, я ставлю библиотеку и автодополнением студии пишу вот такой вот код:

S>
S>var something = collection.LocateNotLess(someValue); // huh?
S>

S>и чего с этим делать дальше?

А что делать с Array.BinarySearch? Или со string.Join или IEnumerable.Join?

S>Ну, в смысле как мне обозвать something?


indexOfNotLess или indexOfGreaterOrEqual. Это если ты не знаешь, зачем тебе реально это значения. А если знаешь, то оно будет иметь название по смыслу, а не по названию метода.

S>Как узнать, какой у него тип, если код читается без подсказок студии?


Никак. Ровно как никак его не узнать у пачки других методов или свойств.

S>Откуда мне узнать, что рядом есть похожие методы, которые могут решить мою проблему лучше?


В данном случае, нужно понимать, каким низкоуровневым алгоритмом можно решать высокоуровневую задачу. Под него находится конкретный метод, реализующий алгоритм. А не наоборот.

S>Получается, что код точно хуже оригинала с LowerBound (это как раз несложно, сложно сделать лучше )


Ну да, хуже тем, что теряется уже устаканенное в мире C++ название алгоритма.

S>Конкретно для нашей ситуации api должен подсказывать как минимум вот это:

S>* пара NotLess + Greater эффективно заменяется EqualRange.

Только в частном случае вызова с одним и тем же value.
Человеку, который понимает, что такое эквивалентность (по отношению к ордерингу) и так будет ясно, что Equal — это то, что между NotLess и Greater. Остальным весьма сложно будет объяснить, что такое EqualRange.

S>* ToWhere — решает ту же проблему, что и Greater, только использует предикат вместо значения.


Это да. Одно можно выразить через другое, слегка поизвращавшись с компараторами/предикатами.

S>Хороший дизайн отражает подобные моменты в именах, обычный — прячет в документации


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

S>На эти грабли в фреймворке натолкнулись в версии 1.0. Вот шикарные выдержки из FDG:


Читал.

S>У нас конечно проблемы "промахнулись, но поправить нельзя" нет, но хочется сразу сделать всё круто


Нереально, ИМХО. Все равно нужно сначала что-то сделать, дать это что-то помучать целевой аудитории, а потом учесть фидбэк. А у нас тут дискуссия на двоих пока получается.

L>>Пока оставил как есть. Только поменял названия параметров from/to и добавил твои примеры и один свой в тесты.

S>Принято Раз лучше сделать не получется, то хоть ухудшать не будем

ОК.
"Будь достоин победы" (c) 8th Wizard's rule.
Re: [CodeJam] UpperBound/LowerBound - оно чего вообще делает?
От: Lexey Россия  
Дата: 18.04.16 20:31
Оценка: 69 (1)
Здравствуйте, Sinix, Вы писали:

S>Можно пример реального юз-кейза для этой штуки?


Всякая математика, требующая многократных поисков в списке/массиве. У меня в одном из проектов используется для поиска пересечений кластеров на плоскости.
Ну и, в Google Code Jam иногда бывает полезно.

S>Как я понял, ищется индекс вставки для элемента в отсортированном списке, так?


LowerBound — да.

S>Тогда:

S>0. Комментарии
S>

S>// Returns the minimum index i in the range [0, list.Count — 1] such that list[i] > value — Upper
S>// Returns the minimum index i in the range [0, list.Count — 1] such that list[i] >= value — Lower

S>Вот фиг из них поймёшь, что имеется в виду. IndexOfFirstGreaterBy/IndexOfFirstGreaterByOrEqual тогда уж

Это стандартные названия этих алгоритмов из STL.

S>1. Проблема с именем, будет путаница с Array.GetUpperBound()


Маловероятно. Array.GetUpperBound() редко используется.

S>2. Путаница с параметром to. В дотнете принято делать пару startIndex + count (сколько элементов просматривать). Аля BinarySearch() / CopyTo() / Substring().


В данном случае это не удобно по 2-м причинам:
1) В оригинале эти алгоритмы работают с итераторами. В таком виде они понятны всем, кто их видел в STLе.
2) Непонятно, что возвращать в случае отсутствия требуемого элемента. -1 — криво, ибо придется всегда отдельно отрабатывать. А to = start + count прекрасно укладывается в общую арифметику индексов.

S>Ок, допустим неудобно настолько, что мы забиваем на least surprise. Зачем тогда to может быть равен count? это ж индекс типа. Я вот про это:

S>

S>        private static void ValidateIndicesRange(int from, int to, int count)
S>        {
S>            ...
S>            Code.AssertArgument(to <= count, nameof(to),
S>                "The {0} index should not exceed the {1}", nameof(to), nameof(count));
S>            ...
S>        }
S>


По факту это не индекс. Это верхняя граница диапазона индексов. То, что в STL зовется end.
to мне самому не очень нравится, но ничего лучше не придумалось. Можно, попробовать в upto переименовать, но не уверен, что будет лучше.
Или можно сделать begin/end, как в STLe.

S>3. Проблема с возвращаемым значением. Непонятно, найдено ли точное совпадение, или просто все предыдущие оказались меньше.


Это by design. Если хочется точное совпадение, то делается ровно одно дополнительное сравнение
на list[result] == value

S>4. Выдаёт рандом на неотсортированных списках. Вот это для меня самый главный WTF.


Это бинарный поиск, так что было бы странно, если бы он работал на неотсортированных списках.

S>И собственно вопрос: чем плох стандартный BinarySearch? С учётом стандартного трюка

S>
S>var index = Array.BinarySearch(data.BinarySearch(2);
S>if (index < 0)
S>{
S>  var insertIndex = ~index;
S>  ...
S>}
S>


Тем, что:
1) Только для массивов.
2) Нет аналога UpperBound и EqualRange.

S>UPD и тот же вопрос — для EqualRange. Как часто нам нужен диапазон с-по для одного значения, не для valueFrom-valueTo?


Редко, но бывает. Когда нужно выбрать все значения с заданным "ключем". И, имея Lower/Upper, логично его тоже реализовать по аналогии с STL.

S>UPD2 и для PartitionPoint — тож. Очень неочевидно, что у нас 4 метода по сути делают одно и то же, только с слегка разным поведением при сравнении.


Ну, вот из-за "слегка" разного поведения их и получается 4.
"Будь достоин победы" (c) 8th Wizard's rule.
Re[3]: [CodeJam] UpperBound/LowerBound - оно чего вообще делает?
От: Lexey Россия  
Дата: 22.04.16 21:04
Оценка: 69 (1)
Здравствуйте, Sinix, Вы писали:

S>1.

S>Для *Bound нужно написать примеры использования, лучше всего оформлять их в виде тестов.
S>Почему это важно:
S>В дотнете API стараются оформлять так, чтобы его можно было использовать без чтения документации. Любой другой вариант резко уменьшает число пользователей, отсылки к STL тут не помогут, т.к. у подавляющего большинства дотнетчиков опыта работы с c++ — мизер.

ОК. Примеры добавлю в тесты.

S>* BinarySearchLower/BinarySearchUpper? Практически идеал, т.к. ещё и показывает, что нам нужно отсортировать список перед использованием.


Хороший вариант, ИМХО.

S>2.

S>Если мы решаем не трогать имена методов, то у нас такая ситуация: вперемешку с обычными бери-и-пользуйся методами лежат методы, которые надо изучать перед тем, как использовать. Как минимум из-за необходимости сортировать данные и неочевидной пары up-to.

S>Решить легко: вытаскиваем все *Bound-методы в отдельный тип, скажем, в BinarySearchExtenstions — вуаля.


Тоже вариант.

S>3.

S>Мне отчаянно не нравится пара up-to. Её или переименовать в startIndex+endIndex и сделать endIndex < count, или поменять на традиционный дотнетовский startIndex + count.
S>Чтобы принять решение надо бы написать реальный пример использования с этими параметрами и посмотреть, что будет лучше. Возьмёшься? Я могу придумать только такие, где вариант с startIndex + count выигрывает.

Вот тебе пример реального использования:
    //(1)
    var vBegin = verticals.LowerBound(horizontal.Begin, (x, v) => Comparer<double>.Default.Compare(x.Key, v));
    if (vBegin == verticalsCount)
    {
        continue;
    }

    //(2)
    var vEnd = verticals.UpperBound(horizontal.End, vBegin, verticalsCount, (x, v) => Comparer<double>.Default.Compare(x.Key, v));

    //(3)
    for (var vIndex = vBegin; vIndex < vEnd; ++vIndex)


В приниципе, можно тут передавать count вместо endIndex, но, тогда придется перед (2) добавить вычисления нужного count (тогда как endIndex мы и так уже знаем). Плюс, в самой реализации делать обратное преобразование.
Хотя, тут пример не самый удачный, ибо взят еще с той версии, когда не было перегрузки, принимающей только start без end'а.
С другой стороны, в нем видно, что может понадобиться сравнивать результат с endIndex (как в (1)), соответственно, если передавать count, то в итоге получится, что нужно работать с двумя сущностями (и count и endIndex), а не с одной (endIndex).
В общем, КМК, вариант с endIndex более консистентен.
Впрочем, если у нас будут удобные диапазоны, то можно сделать 2 варианта:
1) с start и count;
2) с диапазоном

S>4.

S>Возвращаемое значение.
S>Или оставляем как есть, или, если значение не найдено, возвращаем bitwise complement к индексу, как это делает BinarySearch. Второй вариант явно не подходит для UpperBound, там по определению не может быть "не найдено". Оставляем как есть?

Тут я бы предпочел не менять. Ибо результаты lower/upper, как правило, далее используется в последующих вызовах lower/upper (как в (2)) или цикле (как в (3)). И проверки на дополнения и их снятие тут будут выглядеть лишними.

S>5.

S>Тип параметра. В идеале, надо бы сделать IReadOnlyList, но там столько возни, что я бы отложил до лучших времён.
S>Пример возни см в DictionaryExtensions.GetValueOrDefault. По три перегрузки на каждый метод — нафиг-нафиг.

Угу, кто-то (rameel, вроде) это уже предлагал. Идея хорошая, но с перегрузками будет морока.

S>P.S.

S>С DisjointSets давай разберёмся после того, как добьём Lower/UpperBound()

ОК.
"Будь достоин победы" (c) 8th Wizard's rule.
Re[7]: [CodeJam] UpperBound/LowerBound - оно чего вообще делает?
От: Lexey Россия  
Дата: 23.04.16 20:03
Оценка: 38 (1)
Здравствуйте, Sinix, Вы писали:

L>>IndexFrom/IndexTo мне не нравятся.


S>Не вопрос — с тебя любой сценарий использования, в котором вылезают косяки моего предложения Ну, или любой другой вариант, который все 4 метода покрывает.


Один я тебе привел уже — нахождение позиции для вставки. Все 4 не осилю. PartitionPoint вообще не разу не использовал, а EqualRange когда-то совсем давно и только на плюсах.

S>* EqualRange -> IndexesFromTo, напрашиваются две перегрузки, с одним value и с парой valueFrom + valueTo — про это спрашивал в стартовом посте. Решилось


Название просто ужасно. Перегрузка с парой — это просто Lower и Upper, вызванные последовательно. Не вижу смысла ее добавлять. Плюс, у исходного EqualRange смысл в нахождении диапазона, содержащего значения, эквивалентные данному. А тут уже будет нечто иное, то есть, это даже не перегрузка.

S>* PartitionPoint -> IndexFromWhere (и IndexToWhere парой напрашивается).


IndexToWhere более-менее, но IndexFromWhere явно будет лишним.

S>Но можем попробовать варианты FindFrom/FindTo/FindFromTo/FindFromWhere соответственно. Или любой другой.


FindNotLess/FindGreater/FindEqualRange/FindToWhere?
или
LocateNotLess/LocateGreater/LocateEqualRange/LocateFalse

S>Будет что-то лучше — выберем его, без вопросов. Главное чтоб аргументация была по реальным примерам, а не про вкус фломастеров, как я вначале делал.


Вкус фломастеров тоже не на ровном месте формируется, а под воздействием реальных примеров (из других областей).
Так что, тут не все так очевидно.

L>>За ними теряется реальный смысл того, как именно делается поиск.

L>>Плюс, у LowerBound есть еще один классический сценаций использования — определение позиции вставки нового элемента, чтобы не нарушить порядок сортировки:
S>Ну, имя "LowerBound" оба этих момента документирует не лучше.

Для тех, кто про него никогда не слышал, — да. Но, тому, кто не по наслышке знаком с этим алгоритмом по STL, сразу будет ясно, о чем речь. Это серьезный плюс, ИМХО.

S>Да ещё и конфликтует с Array.GetLowerBound(). Наличие двух одинаковых методов, которые делают принципиально разные вещи — эт ппц. Периодически приходится чинить легаси-код с подобными косяками, единственное желание — найти автора, нанять обратно и спихнуть этот код ему


Ты много раз видел использование Array.GetLowerBound? Я вот даже и не помню, чтобы он мне вообще был нужен с дремучих времен OLEшных массивов.

L>>Предложения: или оставить названия as is (только параметры переименовать в startIndex/endIndex) или

L>>переименовать методы в IndexOfEqualOrGreater и IndexOfGreater.
S>Не, IndexOf — эт всегда линейный поиск, с O(n), т.е. ради компромисса мы код не улучшим, а ухудшим.

ОК, значит этот вариант отбрасываем. Хотя, по мне это выглядит как вредная привычка, а не свойство префикса IndexOf (который по сути не говорит ничего кроме того, что ищем индекс).

S>Итого: или оставляем как есть, или подбираем аналог четвёрке IndexFrom/IndexTo/IndexesFromTo/IndexFromWhere, чтоб он всех устраивал. Решение за тобой как за owner-ом


Пока оставил как есть. Только поменял названия параметров from/to и добавил твои примеры и один свой в тесты.

S>2all: а предлагайте тож варианты. А то я сейчас на себя одеяло перетяну в разгаре обсуждения, в итоге все недовольны будут.


+1
"Будь достоин победы" (c) 8th Wizard's rule.
Re[3]: [CodeJam] UpperBound/LowerBound - оно чего вообще делает?
От: Lexey Россия  
Дата: 19.04.16 21:14
Оценка: 23 (1)
S>Ага, тогда так (плиз, прочитать целиком, потом отвечать):

Прочитал. Отвечать пока не готов (времени нет, увы). Ближе к выходным, наверное, доберусь.
Было бы инетересно еще послушать мнение Евгения. Поскольку он тоже был заинтересован в этих алгоритмах.
"Будь достоин победы" (c) 8th Wizard's rule.
Re[4]: [CodeJam] UpperBound/LowerBound - оно чего вообще делает?
От: Sinix  
Дата: 23.04.16 07:51
Оценка: 14 (1)
Здравствуйте, Lexey, Вы писали:

L>Здравствуйте, Sinix, Вы писали:


Огромное спасибо за пример. Теперь показываю, как работает магия с

Framework Design Principle: Frameworks must be designed starting from a set of usage scenarios and code samples implementing these scenarios.



1. Код надо сделать 100% компилирующимся, пусть даже он пока не делает ничего полезного. Для нашего случая:
        private static void Sample1()
        {
            var verticals = new List<KeyValuePair<double, string>>();
            var horizontal = new KeyValuePair<double, double>();

            //(1)
            var vBegin = verticals.LowerBound(
                horizontal.Key, (x, v) => Comparer<double>.Default.Compare(x.Key, v));
            if (vBegin == verticals.Count)
            {
                return;
            }

            //(2)
            var vEnd = verticals.UpperBound(
                horizontal.Key,
                vBegin, verticals.Count,
                (x, v) => Comparer<double>.Default.Compare(x.Key, v));

            //(3)
            for (var vIndex = vBegin; vIndex < vEnd; ++vIndex)
            {
                Console.WriteLine(verticals[vIndex]);
            }
        }


2. Правим то, что сразу бросается в глаза + заодно пробуем вариант с count вместо To
        private static void Sample2()
        {
            var verticals = new List<KeyValuePair<double, string>>();
            var horizontal = new KeyValuePair<double, double>();
            Func<KeyValuePair<double, string>, double, int> compare = (x, v) => Comparer<double>.Default.Compare(x.Key, v);

            //(1)
            var verticalsFrom = verticals.LowerBound(horizontal.Key, compare);
            if (verticalsFrom == verticals.Count)
            {
                return;
            }

            //(2)
            var verticalsTo = verticals.UpperBound(
                horizontal.Key,
                verticalsFrom, 
                verticals.Count - verticalsFrom,
                compare);

            //(3)
            for (var i = verticalsFrom; i < verticalsTo; ++i)
            {
                Console.WriteLine(verticals[i]);
            }
        }


Вот это и должно быть нашим стартовым примером:
1. Сами вызовы не содержат сложных подвыражений в параметрах.
2. Переменные обозваны так, как их назовут большинство программистов на шарпе.
3. Отражает все спорные моменты.


Что отсюда можно вытащить, плохие новости:
1. Моё предложение про BinarySearchLower — отстой. Пользователи привыкли, что BinarySearch возвращает отрицательное значение, мы так делать не хотим.
2. Моё предложение про count — ну, не отстой, но близко к тому.

Хорошие: из примера очевидно, как оно должно выглядеть.
        private static void Sample3()
        {
            var verticals = new List<KeyValuePair<double, string>>();
            var horizontal = new KeyValuePair<double, double>();
            Func<KeyValuePair<double, string>, double, int> compare = (x, v) => Comparer<double>.Default.Compare(x.Key, v);

            //(1)
            var verticalsFrom = verticals.IndexFrom(horizontal.Key, compare);
            if (verticalsFrom == verticals.Count)
            {
                return;
            }

            //(2)
            var verticalsTo = verticals.IndexTo(horizontal.Key, verticalsFrom, verticals.Count, compare);

            //(3)
            for (var i = verticalsFrom; i < verticalsTo; ++i)
            {
                Console.WriteLine(verticals[i]);
            }
        }


М?
Поскольку двигаемся маленькими шажками, то все изменения почти незаметны, но если сравнить с первоначальным вариантом — конфетка же
Главный бонус: как и с BinarySearch, понятно что коллекция должна быть отсортирована.
Хотим подстраховаться по максимуму — можно заменить на IndexFromValue / IndexToValue, но и без него неплохо.


Не, конечно можно спросить "зачем так упарываться, оно ж и без того отлично работало?" Ответ такой:
У public API есть две особенности:
1. Его не поменяешь. Любой косяк в большой библиотеке будет жить и раздражать всех годами. Потомучто совместимость.
2. Это public api. В одном месте неудобное API можно обложить костылями и проверить, что используем правильно. В десятке? В сотне? В проектах, про которые даже не слышал?
Получается, что плохой дизайн "отравляет" код вокруг себя и с этим ничего не сделать, потому что см п.1.

В общем дешевле сделать сразу из хорошего кода отличный, чем страдать всю жизнь из-за мелких недоделок.

L>Впрочем, если у нас будут удобные диапазоны, то можно сделать 2 варианта:

Диапазоны будут, но API надо затачивать под реальные сценарии использования. В твоём примере, если добавить диапазоны, то код сразу хуже станет.


Вопросы / предложения?
Re[2]: [CodeJam] UpperBound/LowerBound - оно чего вообще дел
От: Lexey Россия  
Дата: 20.07.16 09:50
Оценка: +1
Здравствуйте, Jack128, Вы писали:

А нужен? Он тривиально реализуется через LowerBound:
var comparer = (item, id) => item.ID - id;
var index = items.LowerBound(10, comparer);
if (index != items.Count && items[index].ID == 10)
{
    // есть значение
}
else
{
    // нет значения
}


Я посчитал, что городить еще одну функцию смысла нет, тем более, что мне чистый бинарный поиск нужен крайне редко. Гораздо чаще нужен поиск элемента или позиции вставки в одном флаконе.

J>нема? Имхо намного полезнее всяких LowerBound и ежи с ними.


У меня другое ИМХО.

Но, если хочется, то нет проблем добавить и бинарный поиск в исходном стиле:
public static int BinarySearch<T,TValue>(this IList<T> list, TValue value, Func<T, TValue, int> comparer);


Твой Try... через него потом делается с полпинка:
public static bool TryBinarySearch<T,TValue>(this IList<T> list, Func<T, TValue> projection, TValue value, out T result)
{
    var comparer = (item, value) => Comparer<TValue>.Default.Compare(projection(item), value);
    var index = list.BinarySearch(value, comparer);
    if (index != list.Count)
    {
        result = list[index];
        return true;
    }
    result = default(T);
    return false;
}


И сразу видно минус твоего интерфейса — приходится внутри еще создавать дополнительный компаратор.
"Будь достоин победы" (c) 8th Wizard's rule.
Отредактировано 20.07.2016 10:21 Lexey . Предыдущая версия . Еще …
Отредактировано 20.07.2016 10:05 Lexey . Предыдущая версия .
Отредактировано 20.07.2016 10:04 Lexey . Предыдущая версия .
[CodeJam] UpperBound/LowerBound - оно чего вообще делает?
От: Sinix  
Дата: 18.04.16 08:07
Оценка:
Можно пример реального юз-кейза для этой штуки?

Как я понял, ищется индекс вставки для элемента в отсортированном списке, так?

Тогда:
0. Комментарии

// Returns the minimum index i in the range [0, list.Count — 1] such that list[i] > value — Upper
// Returns the minimum index i in the range [0, list.Count — 1] such that list[i] >= value — Lower

Вот фиг из них поймёшь, что имеется в виду. IndexOfFirstGreaterBy/IndexOfFirstGreaterByOrEqual тогда уж

1. Проблема с именем, будет путаница с Array.GetUpperBound()

2. Путаница с параметром to. В дотнете принято делать пару startIndex + count (сколько элементов просматривать). Аля BinarySearch() / CopyTo() / Substring().
Ок, допустим неудобно настолько, что мы забиваем на least surprise. Зачем тогда to может быть равен count? это ж индекс типа. Я вот про это:

        private static void ValidateIndicesRange(int from, int to, int count)
        {
            ...
            Code.AssertArgument(to <= count, nameof(to),
                "The {0} index should not exceed the {1}", nameof(to), nameof(count));
            ...
        }



3. Проблема с возвращаемым значением. Непонятно, найдено ли точное совпадение, или просто все предыдущие оказались меньше.

4. Выдаёт рандом на неотсортированных списках. Вот это для меня самый главный WTF.


И собственно вопрос: чем плох стандартный BinarySearch? С учётом стандартного трюка
var index = Array.BinarySearch(data.BinarySearch(2);
if (index < 0)
{
  var insertIndex = ~index;
  ...
}



UPD и тот же вопрос — для EqualRange. Как часто нам нужен диапазон с-по для одного значения, не для valueFrom-valueTo?
UPD2 и для PartitionPoint — тож. Очень неочевидно, что у нас 4 метода по сути делают одно и то же, только с слегка разным поведением при сравнении.
Отредактировано 18.04.2016 8:20 Sinix . Предыдущая версия . Еще …
Отредактировано 18.04.2016 8:13 Sinix . Предыдущая версия .
Re[2]: [CodeJam] UpperBound/LowerBound - оно чего вообще делает?
От: Sinix  
Дата: 19.04.16 07:08
Оценка:
Здравствуйте, Lexey, Вы писали:

S>>Можно пример реального юз-кейза для этой штуки?


L>Всякая математика, требующая многократных поисков в списке/массиве. У меня в одном из проектов используется для поиска пересечений кластеров на плоскости.

L>Ну и, в Google Code Jam иногда бывает полезно.

Ага, тогда так (плиз, прочитать целиком, потом отвечать):

0.
Все предложения — это только предложения. В смысле, ты всяко лучше меня понимаешь сценарии использования для этих хелперов. Моё дело — более-менее внятно сформулировать то, что пугает неподготовленного пользователя и предложить вариант решения, чтоб было понятно, что имелось в виду. Поехали

1.
Для *Bound нужно написать примеры использования, лучше всего оформлять их в виде тестов.
Почему это важно:
В дотнете API стараются оформлять так, чтобы его можно было использовать без чтения документации. Любой другой вариант резко уменьшает число пользователей, отсылки к STL тут не помогут, т.к. у подавляющего большинства дотнетчиков опыта работы с c++ — мизер.

для простейших перегрузок готовые тесты (комментарии только убрать):
        [Test]
        public void Test001LowerBoundExample()
        {
            // важно: намекаем, что список должен быть отсортирован
            // важно: используем другой тип для значений, чтобы не спутать с индексами.
            var sortedData = new List<string> { "B", "C", "D", "F" };

            var indexOfLowerBound = sortedData.LowerBound("A");
            Assert.AreEqual(indexOfLowerBound, sortedData.IndexOf("B"));

            indexOfLowerBound = sortedData.LowerBound("B");
            Assert.AreEqual(indexOfLowerBound, sortedData.IndexOf("B"));

            indexOfLowerBound = sortedData.LowerBound("C");
            Assert.AreEqual(indexOfLowerBound, sortedData.IndexOf("C"));

            indexOfLowerBound = sortedData.LowerBound("E");
            Assert.AreEqual(indexOfLowerBound, sortedData.IndexOf("F"));

            indexOfLowerBound = sortedData.LowerBound("G");
            Assert.AreEqual(indexOfLowerBound, sortedData.Count);
        }

        [Test]
        public void Test002UpperBoundExample()
        {
            // важно: намекаем, что список должен быть отсортирован
            // важно: используем другой тип для значений, чтобы не спутать с индексами.
            var sortedData = new List<string> { "B", "C", "D", "F" };

            var indexOfUpperBound = sortedData.UpperBound("A");
            Assert.AreEqual(indexOfUpperBound, sortedData.IndexOf("B"));

            indexOfUpperBound = sortedData.UpperBound("B");
            Assert.AreEqual(indexOfUpperBound, sortedData.IndexOf("C"));

            indexOfUpperBound = sortedData.UpperBound("C");
            Assert.AreEqual(indexOfUpperBound, sortedData.IndexOf("D"));

            indexOfUpperBound = sortedData.UpperBound("E");
            Assert.AreEqual(indexOfUpperBound, sortedData.IndexOf("F"));

            indexOfUpperBound = sortedData.UpperBound("G");
            Assert.AreEqual(indexOfUpperBound, sortedData.Count);
        }


Для UpperBound сходу подбирается очевидное название FindIndexAfter.
СLowerBound сложнее.
* FindInsertIndex? Неа, при таком названии должно возвращаться отрицательное значение, если ничего не найдено.
* FindIndexBeforeOrSelf? Ну и чем оно лучше LowerBound?
* FindIndex? Пожалуй, пойдёт, но возможна путаница с List<T>.FindIndex.
* BinarySearchLower/BinarySearchUpper? Практически идеал, т.к. ещё и показывает, что нам нужно отсортировать список перед использованием.

Если последний вариант не подходит, то мы получаем, что текущий вариант с наскока не улучшить. Тоже результат

В общем, пример использования написан не зря.


2.
Если мы решаем не трогать имена методов, то у нас такая ситуация: вперемешку с обычными бери-и-пользуйся методами лежат методы, которые надо изучать перед тем, как использовать. Как минимум из-за необходимости сортировать данные и неочевидной пары up-to.

Решить легко: вытаскиваем все *Bound-методы в отдельный тип, скажем, в BinarySearchExtenstions — вуаля.

3.
Мне отчаянно не нравится пара up-to. Её или переименовать в startIndex+endIndex и сделать endIndex < count, или поменять на традиционный дотнетовский startIndex + count.
Чтобы принять решение надо бы написать реальный пример использования с этими параметрами и посмотреть, что будет лучше. Возьмёшься? Я могу придумать только такие, где вариант с startIndex + count выигрывает.

4.
Возвращаемое значение.
Или оставляем как есть, или, если значение не найдено, возвращаем bitwise complement к индексу, как это делает BinarySearch. Второй вариант явно не подходит для UpperBound, там по определению не может быть "не найдено". Оставляем как есть?

5.
Тип параметра. В идеале, надо бы сделать IReadOnlyList, но там столько возни, что я бы отложил до лучших времён.
Пример возни см в DictionaryExtensions.GetValueOrDefault. По три перегрузки на каждый метод — нафиг-нафиг.

P.S.
С DisjointSets давай разберёмся после того, как добьём Lower/UpperBound()
Re[4]: [CodeJam] UpperBound/LowerBound - оно чего вообще делает?
От: Sinix  
Дата: 19.04.16 21:17
Оценка:
Здравствуйте, Lexey, Вы писали:

L>Прочитал. Отвечать пока не готов (времени нет, увы). Ближе к выходным, наверное, доберусь.

Ок, буду ждать
С временем та же фигня.
Re[4]: [CodeJam] UpperBound/LowerBound - оно чего вообще делает?
От: AndrewVK Россия http://blogs.rsdn.org/avk
Дата: 22.04.16 22:05
Оценка:
Здравствуйте, Lexey, Вы писали:

S>>P.S.

S>>С DisjointSets давай разберёмся после того, как добьём Lower/UpperBound()
L>ОК.

Так что в итоге с релизом то? Вы это все в ближайшее время финализируете? Или лучше в релизной ветке DisjointSets грохнуть совсем, оставив на 1.1?
... << RSDN@Home 1.0.0 alpha 5 rev. 0 on Windows 8 6.2.9200.0>>
AVK Blog
Re[5]: [CodeJam] UpperBound/LowerBound - оно чего вообще делает?
От: Sinix  
Дата: 22.04.16 22:13
Оценка:
Здравствуйте, AndrewVK, Вы писали:

AVK>Так что в итоге с релизом то? Вы это все в ближайшее время финализируете? Или лучше в релизной ветке DisjointSets грохнуть совсем, оставив на 1.1?

Я бы пока перенёс, чтоб релиз не затягивать. Но решение за Lexey, как за автором.
Re[5]: [CodeJam] UpperBound/LowerBound - оно чего вообще делает?
От: Lexey Россия  
Дата: 23.04.16 10:08
Оценка:
Здравствуйте, Sinix, Вы писали:

S>Огромное спасибо за пример. Теперь показываю, как работает магия с

S>

S>Framework Design Principle: Frameworks must be designed starting from a set of usage scenarios and code samples implementing these scenarios.


Угу, книжку читал. Но тут проблема в том, что у меня бэкграунд C++ника, который привык именно к STLному варианту этих алгоритмов. И он мне ближе.

S>Вот это и должно быть нашим стартовым примером:

S>1. Сами вызовы не содержат сложных подвыражений в параметрах.
S>2. Переменные обозваны так, как их назовут большинство программистов на шарпе.
S>3. Отражает все спорные моменты.

ОК.

S>Что отсюда можно вытащить, плохие новости:

S>1. Моё предложение про BinarySearchLower — отстой. Пользователи привыкли, что BinarySearch возвращает отрицательное значение, мы так делать не хотим.
S>2. Моё предложение про count — ну, не отстой, но близко к тому.

ОК.

S>Хорошие: из примера очевидно, как оно должно выглядеть.

S>
S>        private static void Sample3()
S>        {
S>            var verticals = new List<KeyValuePair<double, string>>();
S>            var horizontal = new KeyValuePair<double, double>();
S>            Func<KeyValuePair<double, string>, double, int> compare = (x, v) => Comparer<double>.Default.Compare(x.Key, v);

S>            //(1)
S>            var verticalsFrom = verticals.IndexFrom(horizontal.Key, compare);
S>            if (verticalsFrom == verticals.Count)
S>            {
S>                return;
S>            }

S>            //(2)
S>            var verticalsTo = verticals.IndexTo(horizontal.Key, verticalsFrom, verticals.Count, compare);

S>            //(3)
S>            for (var i = verticalsFrom; i < verticalsTo; ++i)
S>            {
S>                Console.WriteLine(verticals[i]);
S>            }
S>        }
S>


S>М?

S>Поскольку двигаемся маленькими шажками, то все изменения почти незаметны, но если сравнить с первоначальным вариантом — конфетка же
S>Главный бонус: как и с BinarySearch, понятно что коллекция должна быть отсортирована.
S> Хотим подстраховаться по максимуму — можно заменить на IndexFromValue / IndexToValue, но и без него неплохо.

IndexFrom/IndexTo мне не нравятся. За ними теряется реальный смысл того, как именно делается поиск.
Плюс, у LowerBound есть еще один классический сценаций использования — определение позиции вставки нового элемента, чтобы не нарушить порядок сортировки:
    var values = new List<int> { 2, 1, 7, 6, 4, 5 };
    values.Sort();
    const int valueToInsert = 3;
    var insertionPoint = values.LowerBound(valueToInsert);
    values.Insert(insertionPoint, valueToInsert);


IndexFrom в таком варианте только запутает, ИМХО.

S>Не, конечно можно спросить "зачем так упарываться, оно ж и без того отлично работало?" Ответ такой:

S>У public API есть две особенности:
S>1. Его не поменяешь. Любой косяк в большой библиотеке будет жить и раздражать всех годами. Потомучто совместимость.
S>2. Это public api. В одном месте неудобное API можно обложить костылями и проверить, что используем правильно. В десятке? В сотне? В проектах, про которые даже не слышал?
S>Получается, что плохой дизайн "отравляет" код вокруг себя и с этим ничего не сделать, потому что см п.1.

Это понятно. Но тут можно при желании навесить обертки с другими именами и даже с другими параметрами (count вместо endIndex). Так что, КМК, главное, чтобы базовый вариант был разумным и удобным для последующей адаптации.

S>Вопросы / предложения?


Предложения: или оставить названия as is (только параметры переименовать в startIndex/endIndex) или
переименовать методы в IndexOfEqualOrGreater и IndexOfGreater.
Вопросы: что с EqualRange и PartitionPoint делать?
"Будь достоин победы" (c) 8th Wizard's rule.
Re[6]: [CodeJam] UpperBound/LowerBound - оно чего вообще дел
От: Lexey Россия  
Дата: 23.04.16 10:08
Оценка:
Здравствуйте, Sinix, Вы писали:

S>Здравствуйте, AndrewVK, Вы писали:


AVK>>Так что в итоге с релизом то? Вы это все в ближайшее время финализируете? Или лучше в релизной ветке DisjointSets грохнуть совсем, оставив на 1.1?

S>Я бы пока перенёс, чтоб релиз не затягивать. Но решение за Lexey, как за автором.

Выпилю из релиза. В мастере перенесу в Experimental

Update: done.
"Будь достоин победы" (c) 8th Wizard's rule.
Отредактировано 23.04.2016 10:46 Lexey . Предыдущая версия .
Re[6]: [CodeJam] UpperBound/LowerBound - оно чего вообще делает?
От: Sinix  
Дата: 23.04.16 11:24
Оценка:
Здравствуйте, Lexey, Вы писали:

L>IndexFrom/IndexTo мне не нравятся.


Не вопрос — с тебя любой сценарий использования, в котором вылезают косяки моего предложения Ну, или любой другой вариант, который все 4 метода покрывает.

На мой взгляд текущий вариант самый сбалансированный по плюсам-минусам, т.к. покрывает все четыре метода, включая EqualRange + PartitionPoint. Я этот момент учёл, забыл дописать.

* EqualRange -> IndexesFromTo, напрашиваются две перегрузки, с одним value и с парой valueFrom + valueTo — про это спрашивал в стартовом посте. Решилось
* PartitionPoint -> IndexFromWhere (и IndexToWhere парой напрашивается).

Но можем попробовать варианты FindFrom/FindTo/FindFromTo/FindFromWhere соответственно. Или любой другой.


Будет что-то лучше — выберем его, без вопросов. Главное чтоб аргументация была по реальным примерам, а не про вкус фломастеров, как я вначале делал.
Вон from-to индексы мне не нравились, после реального сценария использования выяснилось, что я предлагаю херню (пардон мой французский), вопрос снят
То же самое — про возвращать отрицательное значение, если не найдено. Предложение оказалось дурацким, убираем.


L>За ними теряется реальный смысл того, как именно делается поиск.

L>Плюс, у LowerBound есть еще один классический сценаций использования — определение позиции вставки нового элемента, чтобы не нарушить порядок сортировки:
Ну, имя "LowerBound" оба этих момента документирует не лучше.
Да ещё и конфликтует с Array.GetLowerBound(). Наличие двух одинаковых методов, которые делают принципиально разные вещи — эт ппц. Периодически приходится чинить легаси-код с подобными косяками, единственное желание — найти автора, нанять обратно и спихнуть этот код ему


L>Предложения: или оставить названия as is (только параметры переименовать в startIndex/endIndex) или

L>переименовать методы в IndexOfEqualOrGreater и IndexOfGreater.
Не, IndexOf — эт всегда линейный поиск, с O(n), т.е. ради компромисса мы код не улучшим, а ухудшим.

Итого: или оставляем как есть, или подбираем аналог четвёрке IndexFrom/IndexTo/IndexesFromTo/IndexFromWhere, чтоб он всех устраивал. Решение за тобой как за owner-ом


2all: а предлагайте тож варианты. А то я сейчас на себя одеяло перетяну в разгаре обсуждения, в итоге все недовольны будут.
Re[8]: [CodeJam] UpperBound/LowerBound - оно чего вообще делает?
От: Sinix  
Дата: 23.04.16 20:56
Оценка:
Здравствуйте, Lexey, Вы писали:

L>FindNotLess/FindGreater/FindEqualRange/FindToWhere?

L>или
L>LocateNotLess/LocateGreater/LocateEqualRange/LocateFalse

Не, эт не совсем то что надо получается. Название должно отражать "что метод делает" в смысле "какие проблемы он решает", т.е. подсказывать подразумеваемые сценарии использования. Весь фреймворк на этом построен — 99% кода не требуют чтения документации, она и так есть — в самом коде.

А если под "что метод делает" понимать "что у метода внутри", то получается вот что: Ну ок, я ставлю библиотеку и автодополнением студии пишу вот такой вот код:
var something = collection.LocateNotLess(someValue); // huh?

и чего с этим делать дальше?
Ну, в смысле как мне обозвать something? Как узнать, какой у него тип, если код читается без подсказок студии?
Откуда мне узнать, что рядом есть похожие методы, которые могут решить мою проблему лучше?

Получается, что код точно хуже оригинала с LowerBound (это как раз несложно, сложно сделать лучше )

Конкретно для нашей ситуации api должен подсказывать как минимум вот это:
* пара NotLess + Greater эффективно заменяется EqualRange.
* ToWhere — решает ту же проблему, что и Greater, только использует предикат вместо значения.
Хороший дизайн отражает подобные моменты в именах, обычный — прячет в документации

На эти грабли в фреймворке натолкнулись в версии 1.0. Вот шикарные выдержки из FDG:

KRZYSZTOF CWALINA We did not test the usability of the types in the System.IO namespace before shipping version 1.0 of the Framework.

Soon after shipping, we received negative customer feedback about System.IO usability.
We were quite surprised, and we decided to conduct usability studies with eight average VB developers. Eight out of eight failed to read text from a file in the 30 minutes we allocated for the task. We believe this was due in part to problems with the documentation search engine and insufficient sample coverage; however, it is clear that the API itself had several usability problems. If we had conducted the studies before shipping the product, we could have eliminated a significant source of customer dissatisfaction and avoided the cost of trying to fix the API of a major feature area without introducing breaking changes.

и

BRAD ABRAMS There is no more powerful experience to give an API designer a visceral understanding of the usability of his or her API than sitting behind a one-way mirror watching developer after developer get frustrated with an API he or she designed and ultimately fail to complete the task.

I personally went through a full range of emotions while watching the usability studies for System.IO that we did right after shipping version 1.0. As developer after developer failed to complete the simple task, my emotions moved from arrogance to disbelief, then to frustration, and finally to stringent resolve to fix the problem in the API.


У нас конечно проблемы "промахнулись, но поправить нельзя" нет, но хочется сразу сделать всё круто

L>Пока оставил как есть. Только поменял названия параметров from/to и добавил твои примеры и один свой в тесты.

Принято Раз лучше сделать не получется, то хоть ухудшать не будем
Re[8]: [CodeJam] UpperBound/LowerBound - оно чего вообще делает?
От: AndrewVK Россия http://blogs.rsdn.org/avk
Дата: 23.04.16 22:20
Оценка:
Здравствуйте, Lexey, Вы писали:

S>>2all: а предлагайте тож варианты. А то я сейчас на себя одеяло перетяну в разгаре обсуждения, в итоге все недовольны будут.

L>+1

Я бы от ValueTuple в публичном API избавился в пользу специальной структурки. Потом можно будет с Range объединить из песочницы.
... << RSDN@Home 1.0.0 alpha 5 rev. 0 on Windows 8 6.2.9200.0>>
AVK Blog
Re[8]: [CodeJam] UpperBound/LowerBound - оно чего вообще делает?
От: Evgeny.Panasyuk Россия  
Дата: 19.07.16 16:06
Оценка:
Здравствуйте, Lexey, Вы писали:

L>Один я тебе привел уже — нахождение позиции для вставки. Все 4 не осилю. PartitionPoint вообще не разу не использовал


Например есть список ревизий. Начиная с какой-то из них в проекте появился баг. Есть предикат для тестирования конкретной ревизии. Необходимо найти первую ревизию с багом (а-ля git bisect).
Предикат унарный — на входе только номер ревизии. Для задач с подобной структурой лучше всего подходит partition_point.
00000000000000000000000000000111111111111111111111111
                             ^ partition_point
Re: [CodeJam] UpperBound/LowerBound - оно чего вообще делает?
От: Evgeny.Panasyuk Россия  
Дата: 19.07.16 16:37
Оценка:
Здравствуйте, Sinix, Вы писали:

S>Ок, допустим неудобно настолько, что мы забиваем на least surprise. Зачем тогда to может быть равен count? это ж индекс типа. Я вот про это:


В STL используются "left-closed, right open" диапазоны. То есть два итератора (индекса) first, second задают диапазон [first, second).
Это удобно по нескольких причинам
Равные индексы/итераторы означают пустой диапазон [first, first), это упрощает как реализацию многих алгоритмов, так и использование.
Итераторы/индексы легко комбинировать, взять тот же parition_point:
00000000000000000000000000000111111111111111111111111
^first                       ^ partition_point       ^second
Результат partition_point на самом деле даёт не просто указатель на один элемент, а два диапазона: [first, partition_point) и [partition_point, second)
Пустота правого диапазона, то есть partition_point == second, обычно трактуется как "элемент не найден", но это даже не всегда проверять нужно, так как часто этот диапазон едет по цепочке в следующий алгоритм, который корректно обрабатывает пустые диапазоны.

Вот например попробуй реализовать find_if:
template<typename I, typename P>
I find_if(I first, I last, P pred)
{
    while (first != last && !pred(*first))
        ++first;
    return first;
}
но на базе left-closed, right closed диапазона.
Re: [CodeJam] UpperBound/LowerBound - оно чего вообще делает?
От: Evgeny.Panasyuk Россия  
Дата: 19.07.16 17:06
Оценка:
Здравствуйте, Sinix, Вы писали:

S>UPD2 и для PartitionPoint — тож. Очень неочевидно, что у нас 4 метода по сути делают одно и то же, только с слегка разным поведением при сравнении.


PartitionPoint — базовый.
LowerBound и UpperBound — по сути лишь обёртки (и могут быть реализованы как однострочные обёртки) вокруг PartitionPoint. Они удобны для некоторых сценариев.
EqualRange семантически это LowerBound + UpperBound, но может быть реализован немного эффективнее чем два соответствующих вызова.
Re[2]: [CodeJam] UpperBound/LowerBound - оно чего вообще делает?
От: Sinix  
Дата: 19.07.16 18:45
Оценка:
Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>В STL используются "left-closed, right open" диапазоны. То есть два итератора (индекса) first, second задают диапазон [tt][first, second

Дак выяснили, обсудили и закрыли тему уже

У нас проблема в следующем: проект не на плюсах, целевая аудитория привыкла, что API проектируется так, чтобы его было удобно использовать без чтения документации. С этой точки зрения lower и upper bounds у нас вышли фейлом, но все прочие варианты, судя по обсуждению, заметно хуже.

И в итоге выбор у нас получается такой: или вот такой вот компромисс, или вообще убирать методы. Т.е. вот такой вот компромисс
Re[4]: [CodeJam] UpperBound/LowerBound - оно чего вообще делает?
От: Sinix  
Дата: 19.07.16 20:13
Оценка:
Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Это как-нибудь можно было вывести без чтения документации?

EP>Убрать полезные методы только потому что есть те кто не читает документацию?

Ну так к этому и пришли выше по топику: всем угодить не получается, поэтому оставляем пусть и не идеальный, но хотя бы рабочий вариант.
Re: [CodeJam] UpperBound/LowerBound - оно чего вообще делает?
От: Jack128  
Дата: 20.07.16 07:55
Оценка:
Здравствуйте, Sinix, Вы писали:

А я правильно понимаю, что самого обычного бинарного поиска а-ля:

var items = LoadItems().OrderBy(item => item.ID).ToList();
...
TItem item10;
if (items.TryBinarySearchItem(item => item.ID, 10, out item10)
{

}


нема? Имхо намного полезнее всяких LowerBound и ежи с ними.
Re[2]: [CodeJam] UpperBound/LowerBound - оно чего вообще делает?
От: Sinix  
Дата: 20.07.16 09:06
Оценка:
Здравствуйте, Jack128, Вы писали:

J>А я правильно понимаю, что самого обычного бинарного поиска а-ля:


Нету. Заводи реквест — будет
Re[2]: [CodeJam] UpperBound/LowerBound - оно чего вообще делает?
От: Evgeny.Panasyuk Россия  
Дата: 20.07.16 13:35
Оценка:
Здравствуйте, Jack128, Вы писали:

J>А я правильно понимаю, что самого обычного бинарного поиска а-ля:

J>
J>var items = LoadItems().OrderBy(item => item.ID).ToList();
J>...
J>TItem item10;
J>if (items.TryBinarySearchItem(item => item.ID, 10, out item10)
J>{

J>}
J>

J>нема? Имхо намного полезнее всяких LowerBound и ежи с ними.

Для подобных случаев обычно нужна не отдельная функция, а полноценная map у которой внутри отсортированный массив, а-ля boost::container::flat_map.
Для тех же случаев когда нужна именно функция — достаточно простой обёртки над lower_bound. Я себе сделал возвращающую boost::optional<T>, использование вот такое:
if(auto x = binary_search(xs, value))
{
    // ...
}
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.