Комментарии 27
Я прошу прощения у аудитории, что конец статьи получился несколько скомканным. Когда ты публикуешь статью, а она обрезается на полуслове (какого бабуина это ограничение на объём?!), это сильно деморализирует.
Полностью неосвещённым остался третий пример, про движок регулярных выражений, впрочем, я здесь вряд ли смогу сказать больше Евгения Кирпичева, а уж он расписал свою статью в «ПФП» так замечательно, что этот стиль достоин стать в журнале эталоном, имхо.
Ещё одна тема, которой пришлось пожертвовать — свертки и их связь с моноидами. Любознательный читатель может заглянуть в поисках основ в неплохой перевод Катаморфизм в F#, а более глубокое погружение в тему я как-нибудь соберусь с силами и все же накатаю :)
Для дальнейшего чтения еще рекомендуется:
Блог Дэна Пипони. Уникальное место и уникальный человек, без комментариев.
Посты Владимира Матвеева о структурах данных.
Monoids and Finger Trees
Finger Trees: A Simple General-purpose Data Structure — основополагающая статья на тему Finger Tree и концепции измеримых моноидами деревьев вообще.
Ropes: an Alternative to Strings — основополагающая статья по концепции Rope.
Вот теперь уж точно — всем спасибо за внимание :)
Полностью неосвещённым остался третий пример, про движок регулярных выражений, впрочем, я здесь вряд ли смогу сказать больше Евгения Кирпичева, а уж он расписал свою статью в «ПФП» так замечательно, что этот стиль достоин стать в журнале эталоном, имхо.
Ещё одна тема, которой пришлось пожертвовать — свертки и их связь с моноидами. Любознательный читатель может заглянуть в поисках основ в неплохой перевод Катаморфизм в F#, а более глубокое погружение в тему я как-нибудь соберусь с силами и все же накатаю :)
Для дальнейшего чтения еще рекомендуется:
Блог Дэна Пипони. Уникальное место и уникальный человек, без комментариев.
Посты Владимира Матвеева о структурах данных.
Monoids and Finger Trees
Finger Trees: A Simple General-purpose Data Structure — основополагающая статья на тему Finger Tree и концепции измеримых моноидами деревьев вообще.
Ropes: an Alternative to Strings — основополагающая статья по концепции Rope.
Вот теперь уж точно — всем спасибо за внимание :)
А че не разбил на две части?
Части не будут казаться цельными, тут же единая мысль логическая идет, развивается, накапливается новыми подробностями, завершается кульминацией трех жизненных примеров, и все. Ничего нельзя выкинуть, без контекста оно совершенно не читается, сколько ты не ори триста раз, что «это продолжение статьи по ссылке такой-то, сначала читайте её».
Спасибо, небожитель!
</irony>
</irony>
Торт! Кстати отличная демонстрация применения чистой математики, в свое время изучал в университете дискретную математику и практические занятия были далеки от реальной практики. Автору спасибо за материал, было бы интересно, если бы Вы продожили публиковать подобные вещи.
Спасибо. Я, собственно, и задумал-то эту статью, потому что сталкивался с множеством человек, которые начинают интересоваться Computer Science (кто-то в вузе по программе, а кого-то просто совесть берет, что программистом работает, а матбазы не учил), читают про, например, моноиды, и начинают ныть: «Нет, ну это все, конечно, красиво, абстрактно, логично и всё такое… но на черта оно надо?» В итоге злость берет =)
Точно! Я, признаться, лентяй. Мне чудовищно лениво сесть и попробывать осмыслить чистую теорию для переложения на практику, но стоит только показать реальный пример, как то, что казалось занудной бредятиной во время подготовки к экзамену, становится не таким уж непонятным, скучным и ненужным. Конечно, в ВУЗах не обязаны все разжевывать нерадивым студентам, им для этого мозги даны, но я, лично, думаю, что подкрепляя любой теоретический материал примерами и наработками из реальной практики, а не абстрактными задачами, можно получить несколько больше специалистов, идущих работать по специальности. Ведь не все люди гении, верно?
Ухуху, Хабр снова Торт! :D
Спасибо!
Спасибо!
Прекрасная статья!
Тем не менее, позволю себе напомнить, что погоня за эффективными и красивыми алгоритмами никогда не должна являться самоцелью, и ее необходимость всегда должна предварительно оцениваться.
Однажды я стажировался полгода в одном неплохом немецком институте, занимаясь вычислительной физикой, и мой профессор всегда говорил что-то типа: «Зачем тратить время на эту дурацкую оптимизацию? Запроси в два раза больше процессоров на суперкомпьютере, и все проблемы решены. Нам нужны результаты, а не оптимальный код».
Например, если нам подходит другая сторона компромисса память/время, то большинство этих примеров легко реализовать без treapa, просто вычисляя меру на подотрезках заново. Плюс код будет намного лучше, читабельнее, сопровождаемее.
И да, торт!
Тем не менее, позволю себе напомнить, что погоня за эффективными и красивыми алгоритмами никогда не должна являться самоцелью, и ее необходимость всегда должна предварительно оцениваться.
Однажды я стажировался полгода в одном неплохом немецком институте, занимаясь вычислительной физикой, и мой профессор всегда говорил что-то типа: «Зачем тратить время на эту дурацкую оптимизацию? Запроси в два раза больше процессоров на суперкомпьютере, и все проблемы решены. Нам нужны результаты, а не оптимальный код».
Например, если нам подходит другая сторона компромисса память/время, то большинство этих примеров легко реализовать без treapa, просто вычисляя меру на подотрезках заново. Плюс код будет намного лучше, читабельнее, сопровождаемее.
И да, торт!
Тут есть деталь. Если вы для себя считаете и вам нужно один раз посчитать и получить результат, то этот подход работает.
Однако, если алгоритмы нужно применять в библиотеках, тот тут появляется мета-цель сделать эффективный алгоритм, потому что не все пользователи смогут запросить процессоров и возможно им придётся пересчитывать сходные задачи по многу раз.
Однако, если алгоритмы нужно применять в библиотеках, тот тут появляется мета-цель сделать эффективный алгоритм, потому что не все пользователи смогут запросить процессоров и возможно им придётся пересчитывать сходные задачи по многу раз.
НЛО прилетело и опубликовало эту надпись здесь
Честно говоря, понимаю Вас — когда я учился я тоже не понимал, насколько все эти знания могут быть полезны в моей практике, как программиста.
Сейчас уже не раз и не два посыпал голову пеплом и выпрашивал конспекты у тех, кто более внимательно учился на лекциях, пытаясь проходить еще и еще раз это сам.
Вы не поверите, но если Вы хотите быть хорошим программистом, который не только умеет кодить то, что «сверху» прислали, а и предлагать более оптимальные решения и самим «отсылать вниз», то просто необходимо не просто _выучить_ это, а и понимать.
Так что все что я могу посоветовать, не повторяйте ошибок тех, кто (как я) не ценил практические полезные знания, ошибочно полагая что это все теоретическая туфта и когда я буду кодить, мне это нафиг не пригодится.
Сначала да, не нужно было. А вот теперь я с огромным удовольствием читаю вот такие вот статьи (однозначно в фейворитс на будущее и +1 за труды автору)
Сейчас уже не раз и не два посыпал голову пеплом и выпрашивал конспекты у тех, кто более внимательно учился на лекциях, пытаясь проходить еще и еще раз это сам.
Вы не поверите, но если Вы хотите быть хорошим программистом, который не только умеет кодить то, что «сверху» прислали, а и предлагать более оптимальные решения и самим «отсылать вниз», то просто необходимо не просто _выучить_ это, а и понимать.
Так что все что я могу посоветовать, не повторяйте ошибок тех, кто (как я) не ценил практические полезные знания, ошибочно полагая что это все теоретическая туфта и когда я буду кодить, мне это нафиг не пригодится.
Сначала да, не нужно было. А вот теперь я с огромным удовольствием читаю вот такие вот статьи (однозначно в фейворитс на будущее и +1 за труды автору)
Спасибо за отменную статью! У Вас талант к подаче материала)
П.С. Хабр торт!
П.С. Хабр торт!
Монойд — полугруппа с единицей, думаю возможно когда вы описывали что такое полугруппа и добавив единицу к конструкции нужно было упомянуть что это полугруппа.
Отличный стиль изложения и оформление статьи. Нечасто бывает, что длинные и не совсем простые для понимания статьи получается дочитать до конца, а главное всё осмыслить.
Январь 2011 — месяц поднятия тортовости хабра.
Хорошая статья. В этой статье habrahabr.ru/blogs/algorithm/105450/ я использовал похожий подход.
Но в основе были полукольца. А точнее, конечные автоматы на тропическом и вероятностном полукольцах. В статье об этом не написано, т.к. не решился писать про кольца, моноиды и т.п. Но математика работает красиво.
Но в основе были полукольца. А точнее, конечные автоматы на тропическом и вероятностном полукольцах. В статье об этом не написано, т.к. не решился писать про кольца, моноиды и т.п. Но математика работает красиво.
Отличная статья! В институте как раз закончился семестр теории групп, было интересно узнать где она применяется.
Не понимаю, раз в Java такая структура данных используется (Rope), почему конкатенации такие дорогие.
Или создавать новые ноды так дорого стоит?
Или создавать новые ноды так дорого стоит?
Есть статья от Эрика Липперта, в которой он делится опытом создания такой структуры и причинами, по которым они в последующих проектах от них отказались.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Моноиды и их приложения: моноидальные вычисления в деревьях