Моноиды и их приложения: моноидальные вычисления в деревьях

[@Skiminok]

Я прошу прощения у аудитории, что конец статьи получился несколько скомканным. Когда ты публикуешь статью, а она обрезается на полуслове (какого бабуина это ограничение на объём?!), это сильно деморализирует.

Полностью неосвещённым остался третий пример, про движок регулярных выражений, впрочем, я здесь вряд ли смогу сказать больше Евгения Кирпичева, а уж он расписал свою статью в «ПФП» так замечательно, что этот стиль достоин стать в журнале эталоном, имхо.

Ещё одна тема, которой пришлось пожертвовать — свертки и их связь с моноидами. Любознательный читатель может заглянуть в поисках основ в неплохой перевод Катаморфизм в F#, а более глубокое погружение в тему я как-нибудь соберусь с силами и все же накатаю :)

Для дальнейшего чтения еще рекомендуется:
Блог Дэна Пипони. Уникальное место и уникальный человек, без комментариев.
Посты Владимира Матвеева о структурах данных.
Monoids and Finger Trees
Finger Trees: A Simple General-purpose Data Structure — основополагающая статья на тему Finger Tree и концепции измеримых моноидами деревьев вообще.
Ropes: an Alternative to Strings — основополагающая статья по концепции Rope.

Вот теперь уж точно — всем спасибо за внимание :)

[@chaliy]

А че не разбил на две части?

[@Skiminok]

Части не будут казаться цельными, тут же единая мысль логическая идет, развивается, накапливается новыми подробностями, завершается кульминацией трех жизненных примеров, и все. Ничего нельзя выкинуть, без контекста оно совершенно не читается, сколько ты не ори триста раз, что «это продолжение статьи по ссылке такой-то, сначала читайте её».

[@zloddey]

Спасибо, небожитель!
</irony>

[@gwinn]

Торт! Кстати отличная демонстрация применения чистой математики, в свое время изучал в университете дискретную математику и практические занятия были далеки от реальной практики. Автору спасибо за материал, было бы интересно, если бы Вы продожили публиковать подобные вещи.

[@Skiminok]

Спасибо. Я, собственно, и задумал-то эту статью, потому что сталкивался с множеством человек, которые начинают интересоваться Computer Science (кто-то в вузе по программе, а кого-то просто совесть берет, что программистом работает, а матбазы не учил), читают про, например, моноиды, и начинают ныть: «Нет, ну это все, конечно, красиво, абстрактно, логично и всё такое… но на черта оно надо?» В итоге злость берет =)

[@gwinn]

Точно! Я, признаться, лентяй. Мне чудовищно лениво сесть и попробывать осмыслить чистую теорию для переложения на практику, но стоит только показать реальный пример, как то, что казалось занудной бредятиной во время подготовки к экзамену, становится не таким уж непонятным, скучным и ненужным. Конечно, в ВУЗах не обязаны все разжевывать нерадивым студентам, им для этого мозги даны, но я, лично, думаю, что подкрепляя любой теоретический материал примерами и наработками из реальной практики, а не абстрактными задачами, можно получить несколько больше специалистов, идущих работать по специальности. Ведь не все люди гении, верно?

[@chiaroscuro]

Не нужно быть гением, чтобы самому искать приложения «этой теории». Зачастую требуется лишь чуточку внимания и немного мотивации.

[@gwinn]

Убедили, про гениальность пожалуй и впрямь несколько утрировано :)

[@marazmus]

Ухуху, Хабр снова Торт! :D
Спасибо!

[@Bas1l]

Прекрасная статья!

Тем не менее, позволю себе напомнить, что погоня за эффективными и красивыми алгоритмами никогда не должна являться самоцелью, и ее необходимость всегда должна предварительно оцениваться.

Однажды я стажировался полгода в одном неплохом немецком институте, занимаясь вычислительной физикой, и мой профессор всегда говорил что-то типа: «Зачем тратить время на эту дурацкую оптимизацию? Запроси в два раза больше процессоров на суперкомпьютере, и все проблемы решены. Нам нужны результаты, а не оптимальный код».

Например, если нам подходит другая сторона компромисса память/время, то большинство этих примеров легко реализовать без treapa, просто вычисляя меру на подотрезках заново. Плюс код будет намного лучше, читабельнее, сопровождаемее.

И да, торт!

[@vuspenskiy]

Тут есть деталь. Если вы для себя считаете и вам нужно один раз посчитать и получить результат, то этот подход работает.

Однако, если алгоритмы нужно применять в библиотеках, тот тут появляется мета-цель сделать эффективный алгоритм, потому что не все пользователи смогут запросить процессоров и возможно им придётся пересчитывать сходные задачи по многу раз.

[@AlexTikhonov]

Честно говоря, понимаю Вас — когда я учился я тоже не понимал, насколько все эти знания могут быть полезны в моей практике, как программиста.

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

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

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

Сначала да, не нужно было. А вот теперь я с огромным удовольствием читаю вот такие вот статьи (однозначно в фейворитс на будущее и +1 за труды автору)

[@chiaroscuro]

Создавайте, вам же никто не мешает! Только не следует выдавать такую практику за единственно возможную. Другие люди могут делать по-другому.

[@RodeGO]

Спасибо за отменную статью! У Вас талант к подаче материала)

П.С. Хабр торт!

[@Ilya_Smelykh]

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

[@Skiminok]

Конечно, нужно.
Эх, сколько бы я еще всего упомянул здесь, будь у меня ещё хоть треть-столько же байт доступно для заполнения…

[@Dale]

Отличный стиль изложения и оформление статьи. Нечасто бывает, что длинные и не совсем простые для понимания статьи получается дочитать до конца, а главное всё осмыслить.

[@fledgling]

Январь 2011 — месяц поднятия тортовости хабра.

[@lightcaster]

Хорошая статья. В этой статье habrahabr.ru/blogs/algorithm/105450/ я использовал похожий подход.
Но в основе были полукольца. А точнее, конечные автоматы на тропическом и вероятностном полукольцах. В статье об этом не написано, т.к. не решился писать про кольца, моноиды и т.п. Но математика работает красиво.

[@wishope]

Отличная статья! В институте как раз закончился семестр теории групп, было интересно узнать где она применяется.

[@vuspenskiy]

Не понимаю, раз в Java такая структура данных используется (Rope), почему конкатенации такие дорогие.
Или создавать новые ноды так дорого стоит?

[@ttim]

В яве ropes не используются для хранения строк. Используется просто массив символов из-за чего и получается долгая конкатенация.
Почему не ropes — вероятно потому что более долгое время доступа к элементам и оверхед по памяти.

[@Xitsa]

Есть статья от Эрика Липперта, в которой он делится опытом создания такой структуры и причинами, по которым они в последующих проектах от них отказались.