Решая задачу по физике, gpt-oss:20b допустил ровно ту же ошибку в вычислениях, что и я. Таким образом, эмпирически я пришёл к выводу, что интеллекта у меня с AMD RX9070XT.
Binary tree
Нормализированные данные в принципе вкусные, да и на ощупь приятные. Всегда, сужая общий случай до частного, в процессе у более ограниченного подмножества всплывает всё больше свойств и оголяется структура, из которой могут следовать интересные заключения.
Так и с упорядоченными массивами. Как только оная гарантируется, сложность поиска резко падает с линейной до логарифмической, за счёт возможности применения бинарного поиска вместо линейного. К сожалению, выигрыш в поиске за счёт вставки: теперь, для поддержания гарантии, вставка работает в среднем за линейную сложность. Всё-таки место в массиве само себя не освободит - все элементы правее нужного места должны быть смещены вправо на одну позицию, прямо как в отеле Гильберта. Представьте, какого это: участок на гигабайт переместить на 8 байт правее. Это ж блять чистая комедия.
Однако тривиальность переоценивать - обсёрами чревато. Как, например, в Java 9 лет таилось переполнение при взятии среднего арифметического. Rookie ass mistake. Зато в Go всё изначально в порядке - длина всегда представлена в int, а среднее арифметическое берётся в uint. Лишний бит гарантирует отсутствие переполнения.
А ещё не всегда учитывается субоптимальность обобщённого бинарного поиска по массиву строк. Имея L < key < R (где L, R - строки в массиве), беря их среднее арифметическое (строка в массиве между L и R), нам необязательно её сравнивать полностью с искомым ключом. Потому что ключ заведомо имеет общий префикс с L и R:
int prefix = lcp(L, R);
if (strcmp(key+prefix, mid+prefix) == 0)
...
(Где
lcp(s1,s2) возвращает длину общего префикса двух строк, а key+prefix аналогичен key[prefix:] в других языках.)То есть, мы можем опустить сравнение первых lcp(L, R) между искомым и средним арифметическим. А так можно чуть ли не пол строки скрутить. Правда, если строки в массиве всё-таки практически общих префиксов не имеют, то мы лишь расстратимся на лишнюю пару инструкций. Так что вслепую применять всё равно не стоит.
А сейчас - самое интересное. Бинарный поиск по упорядоченному массиву - частный случай бинарного дерева, схлопнутого к одномерному массиву, логично. Но тут сразу вырисовывается неприятное заключение: если на нашем множестве ключей такая оптимизация с отсеканием префикса из сравнения действительно работает, то это означает лишь то, что мы тратим пространство неэффективно. Если столько байт пропускаются, то хули они там вообще забыли?