В первый раз

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

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

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

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

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

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