Дела и проблемы

Если на вопрос "Как дела?" вам отвечают "Нормально", значит вы не входите с группу доверия этого человека.

Прикольно, но для меня это даже не рефлексивно. Лично я изобрел фразу: "Ты бы еще спросил как у меня дела..."

А еще в последнее время от меня можно услышать фразу "Это твои проблемы". С большой вероятностью, это означает что мы более-менее хорошо знакомы. Если мы не знакомы, и вы услышали от меня эту фразу - значит мы точно не будем знакомы. А если мы малознакомы, и вы начинаете на что-то жаловаться, то я буду тупо улыбаться, так как природная скромность не позволит мне честно сказать.

Фразу "Это моя проблема" я произношу довольно часто.

А если в решении проблемы заинтересовано более одного субъекта, то это проблема. Поэтому надо делить до "Это моя проблема"/"Это твоя проблема". Только очень маленький класс проблем будет решен парой качественно (тут проблемы с внимательностью). Все остальное надо делить на эгоистические подзадачи.

Дерево

Таки реализовал порядковую статистику с поиском минимума на отрезке.
Декартовы деревья (они же дерамиды, они же treap, они же cartesian tree, они же деревья приоритетного поиска (по Вирту)) рулят. Смесь дерева и пирамиды. Дерево - для поиска, свойства кучи - для балансировки (у каждого узла есть дополнительный признак - приоритет, выбирается рандомом - по которому имеется свойства кучи). Вставка/удаление/поиск - как дерево, балансировка - как куча (два тривиальных поворота).

В Б-дереве удаление (точнее, сжатие узлов при удалении) - штука довольно нетривиальная при реализации.

Правда, поиск минимума на отрезке тривиален только первоначально в голове, при первой реализации поймаете "кучку" (в смысле множества) тонкостей. Советую нарисовать полный хип на 31/63 узла и потренироваться на "кошках". Порядковая статистика отличается от порядковой статистикой с поиском агрегата, только дополнительным методом для поиска всего-этого и тривиальным вызовом при поворотах для обновления агрегата.

На Б-дереве (с плотностью более 2) поиск минимума будет еще не тривиальнее.

Странно, все влезло в 10К. Теперь стоит написать комментарии, вынести минимум в сущность моноида и еще пара моментов. В 15К точно буду.

Update:
Дженерики более второго порядка в современном программировании - зло.
Как же называется коммутативная полугруппа? Моноид - не то, промахнулся я с абстракцией. Абелевы полугруппы? В мое время были только абелевы группы, let it be...
Вынес сущность, на (min, +\inf) все работало, на (+, 0) перестало. Где-то дважды хожу по дереву. Все не тривиальнее и не тривиальнее...

Update2:
забыл я алгебру... это просто коммутативный моноид.

Современность

HTC Hero очень современный телефон.

Вставив и достав наушники, он почему-то считает что уши еще есть, и поэтому при звонке голос собеседника отправляется в /dev/null (ну, или в /dev/куда_не_надо). Стоимость двух fake-звонков в Мск составляет двухмесячный бюджет моих звонков, не то что дорого, просто я звоню мало. Помог только перегруз телефона, да и потом я решил звонить с городского.

В первый раз

Сегодня впервые смог оттянуть свояка в невке. Понравилось.

Недавно за пять минут (ибо Haskell) реализовал "почти Рабина-Миллера". Не совсем классический, тупо рандомом выбираю числа и проверяю малую теорему Ферма. Начал тестировать. На двух числах, которые я был уверен что они Кармайкловы (561 как минимальное, и Рамануджан) тест выдает что составные. Что бы разобраться "что за фигня" потребовалось больше времени, чем на написание. Оказывается, все правильно. Казалось бы, что такой тест должен пропускать все Кармайкловы числа, но мы очень часто случайно выбираем число не взаимно простое с числом (561 вообще делится на 3, 11,17; 1729 на 7,13,19). Хотя из определения Кармайкловости "казалось" что должно быть "Кармайкловым".

Сейчас сижу и реализовываю Б-дерево. Вставка/замена/доступ работает, удаление пока в отладке. Найти нормальную реализацию сбалансированного дерева почему-то для меня в 2010 году еще составляет нетривиальную задачу, что проще самому написать.

Нашел несколько реализаций красно-черных и других, но там код "вонючий". Если есть приватная филда с именем "tempNode", которая инициализируется в одном методе, а используется в другом - то код для меня "вонючий". В другой реализации кода порядка 130 Кб - что-то много нетривиального, видимо. А мне не надо просто дерево, мне надо динамическую статистику (понятие из Кормена), то есть удаление/добавление/индексный_доступ за log(n), и еще расширив потребуется поиск минимума на отрезке то же за log(n).

Хотя недавно видел на Haskell реализацию красно-черного - там все повороты красиво описаны в 5-ти строках. Я же решил писать Б-дерево, так как оно интуитивно понятно (нет никаких странных поворотов), правда с удалением не совсем все тривиально.

Резюмируя, все что вы делаете в первый раз может сильно отличаться от того, что у вас было в голове всю предыдущую жизнь.

n-юродность

Я долгое время не мог понять родственные отношения с n-юродностью, n >= 3. "Троюродная сестра" или "двоюродный дядя" - эти абстракции не помещались у меня в голове. Двоюродные братья/сестры у меня есть, дяди/тети тоже имеются, а всех кто дальше я причисляю к дальним родственникам.

Таки въехал. Оказывается все просто. Берем две вершины. Ищем lca. n = min(r(lca, v_1), r(lca, v_2)). \ldots Дедушка/дядя/брат/племянник/внук /ldots определяется простой разницей: r(lca, v_1) - r(lca, v_2), где r(i, j) - расстояние между прямыми потомками, не симметрично; lca - по определению :) .

Объективно пол определяется по записи в свидетельстве о рождении. Хотя я знаю нескольких физиологически-мальчиков с головами девочек, и несколько физиологически-девочек с головами мальчиков. Так что пол для меня вещь субъективная.