Николай Ершов nickme

Шикарный спотыкач! Кстати, возникает интересная алгоритмическая задача по автоматической генерации такого рода текстов.

А неплоский… лабиринт тоже довольно экзотичен для реального мира.

Понял, спасибо!

Хм, а первая задача разве за линейное время не решается? В каждом слове ищем первую слева букву (начиная при этом со второй буквы, т.к. префикс не должен быть пустым), большую первой буквы в следующем слове и обрезаем слово по найденной букве (не включая ее), от последнего слова оставляем только первую букву. На всех приведенных примерах это вроде работает…

С числом 210 смешно получается (или с 222, короче, если в делителях только одна двойка) — эффект двоения в глазах зачетный :)

Красиво! Пифагор бы порадовался :)

Оригинальная статья на английском (Yann Esposito) и перевод на русский (mungobungo), в pdf-формате для чтения на 6-дюймовых е-читалках.

Быстро вы вторую часть выкатили, спасибо!

кстати, на викибукс есть викиучебник по хаскелю в формате pdf, сверстанный под 6-дюймовые читалки…

Спасибо за статью, ждем продолжения!

ЗЫ: Не совсем функционально, зато рекурсивно и в одну строчку :)

int sum(int* x) 
{ 
  return x[0]?(((x[0]%2)?0:x[0])+sum(x+1)):0; 
}

Во, то что доктор прописал :) Спасибо еще раз!

Спасибо большое за ссылки, обязательно поизучаю на досуге! С libdatrie, кстати, я сравнение не делал… Относительно терминологии, мне больше нравится Radix Tree и русский вариант — дерево цифрового поиска.

Кстати, кто-нибудь может подскажет, где найти стандартные тестовые наборы для такого рода задач?

Это я к тому, что суммарный объем необходимой памяти, в принципе, один и тот же, поэтому, чем меньше куски, тем больше их нужно, тем больше операций с памятью…

Эти куски памяти к тому же и очень мелкие :(

Была мысль вместо односвязного списка хранить двоичное дерево (то же АВЛ), но что-то страшно стало :) А вот с алфавитом все немного интереснее выглядит, надо будет подумать…

Доля правды в ваших словах есть. Вот распределение длин ключей во внутренних узлах дерева для двух тестовых наборов:



Однако, хранить в одном узле один символ (при двух указателях) — это, по-моему, перебор. Хотя, с другой стороны, такой вариант (несжатое префиксное дерево) у меня реализован, но статистику я с него еще не снимал…

Ссылку попозже посмотрю, спасибо!

1) С этим замечанием согласен, на графике время отнормировано на размер (в символах) используемого набора строк, иначе разброс для одного графика оказывался очень большим. Сейчас попробую пересчитать чистое время… На третьем графике шкала обозначена в подписи :) — по оси Y отложено количество байт на один символ (символ у меня занимает один байт)…
2,3) Про продакшн никто и не говорит :)

1) На первых двух графиках сравниваются между собой два времени, какая разница, какая там шкала? На третьем шкала обозначена… На серьезную статобработку данных времени и сил пока нет :)
2) Стек выдержал :) Кстати, да, надо было бы глубину дерева измерить. А в принципе, можно и итеративную реализацию сделать…
3) А какая длина массива должна быть (это в случае, когда дерево мутируется)? На самом деле я уже думал над таким вариантом — держать в узле вектор указателей на всех дочерей узла…

Про минимум эвристики улыбнуло :) Есть мнение, что уйти от экспоненциальности (а ведь это ваша цель?) и при этом сохранить оптимальность нельзя…

В результате вы все равно получили эвристический алгоритм… Чуда не произошло! :)

Как я понял, АВЛ-деревья лучше сбалансированы, чем красно-черные. В этом их плюс, т.к. поиск выполняется чуть-чуть быстрее: высота в АВЛ-дереве ограничена величиной 1.44log₂(n+2) против 2log₂(n+1) в красно-черных. С другой стороны, это означает, что в АВЛ-деревьях больше сил затрачивается на балансировку, следовательно, операции вставки и удаления работают медленнее, чем в красно-черных деревьях. Так что однозначного победителя здесь похоже нет…

Оглавление интересное, надо поискать… Спасибо!
PS: уже нашел :)

Т.е. все-таки случай, когда ключи не все одинаковы! Как я понимаю, количество «ложных» срабатываний (когда мы переходим в узел, не содержащий искомого ключа, как в вашем примере) в одном случае будет 2h, во втором h, где h — высота дерева. Если дерево идеально сбалансировано, то получим 2log₂n против log₂n, что уже не выглядит так драматично :)

Спасибо! Теперь можно сравнить с реализацией на Haskell… Кстати, не нашел удаления ключей в вашей программе. Правда, там есть union — это слияние двух деревьев? Если «да», то удаление уже несложно реализовать…

Все равно непонятно: чтобы добраться до какого-то элемента, мы должны спуститься к нему из предыдущего по дуге, что эквивалентно выполнению ровно одного сравнения. Т.е. число сравнений (<= или >=) все равно окажется равным n-1. Для примера можно взять случай с тремя вершинами (выше в комментариях) — в обоих нарисованных вариантах дерева нам потребуется 3 (т.е. n) сравнения на равенство и 2 (т.е. n-1) на меньше-больше, нет? Возможно, по другому будет, если число одинаковых ключей, которые мы ищем, равно k и оно меньше n? Сейчас подумаю…

Предположим, что у нас в дереве n одинаковых ключей (предельный случай) и больше ничего, и одинаковые ключи могут быть и слева и справа. Тогда поиск найдет все их, обойдя все дерево, и выполнит при этом O(n) действий. Пока я не вижу проблемы — чтобы найти n вхождений, потребовалось выполнить O(n) действий… Может я чего-то не понимаю?

Красиво! И местами даже понятно… :)

Нет, не только вам, мне теперь тоже так кажется :) Обычно пишу, как во втором варианте, а тут решил «укомпактить» код…

Собственно, при написании топика я этот момент не проверил, т.к. мне казалось, что я помню именно такое определение (два нестрогих неравенства). Сейчас посмотрел Кормена, оказывается я правильно помнил… Вообще-то, чуть ниже в топике (в том же абзаце) я ввел более строгое ограничение, предположив, что все ключи различны, и рисунок относится именно к этому случаю. Уникальность же ключей, например, гарантрируется, если мы с помощью дерева поиска реализуем какой-нибудь словарь (или ассоциативный массив).

Спасибо!

Сначала хочется разобраться со сплей-деревьями, а потом уже очередь красно-черных…

Как это не удивительно, но я не встретил ни разу рекурсивной реализации АВЛ-деревьев, везде предлагается итеративный подход. Поделитесь ссылками на реализацию на непроцедурных ЯП?

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

Геделя упустил, каюсь. А Левенштейна не нашел карточку. Вернее одна есть на его персональной странице в ИПМ, но она слишком маленькая (хотя можно было попытаться ее увеличить)… Точно придется вторую версию делать! :)

Затруднит :) т.к. списков никаких не составлялось… Как только был превышен порог в 256 персон, процесс остановился. Википедия (например, вот) и гугл-картинки — вот по сути и все источники. Бумажные энциклопедия по информатике и математический энциклопедический словарь (единственное место, где я нашел фотографию Жегалкина). Еще пара ссылок, которыми я пользовался: тыц и тыц.

Спасибо!

А Цезарь вас на этом постере не смущает? :)

Гильберт в q10. В остальном согласен, но переделывать ничего не буду :)

Спасибо, то что надо!