Pull to refresh

Comments 27

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

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

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

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

Вот теперь уж точно — всем спасибо за внимание :)
Части не будут казаться цельными, тут же единая мысль логическая идет, развивается, накапливается новыми подробностями, завершается кульминацией трех жизненных примеров, и все. Ничего нельзя выкинуть, без контекста оно совершенно не читается, сколько ты не ори триста раз, что «это продолжение статьи по ссылке такой-то, сначала читайте её».
Торт! Кстати отличная демонстрация применения чистой математики, в свое время изучал в университете дискретную математику и практические занятия были далеки от реальной практики. Автору спасибо за материал, было бы интересно, если бы Вы продожили публиковать подобные вещи.
Спасибо. Я, собственно, и задумал-то эту статью, потому что сталкивался с множеством человек, которые начинают интересоваться Computer Science (кто-то в вузе по программе, а кого-то просто совесть берет, что программистом работает, а матбазы не учил), читают про, например, моноиды, и начинают ныть: «Нет, ну это все, конечно, красиво, абстрактно, логично и всё такое… но на черта оно надо?» В итоге злость берет =)
Точно! Я, признаться, лентяй. Мне чудовищно лениво сесть и попробывать осмыслить чистую теорию для переложения на практику, но стоит только показать реальный пример, как то, что казалось занудной бредятиной во время подготовки к экзамену, становится не таким уж непонятным, скучным и ненужным. Конечно, в ВУЗах не обязаны все разжевывать нерадивым студентам, им для этого мозги даны, но я, лично, думаю, что подкрепляя любой теоретический материал примерами и наработками из реальной практики, а не абстрактными задачами, можно получить несколько больше специалистов, идущих работать по специальности. Ведь не все люди гении, верно?
Не нужно быть гением, чтобы самому искать приложения «этой теории». Зачастую требуется лишь чуточку внимания и немного мотивации.
Убедили, про гениальность пожалуй и впрямь несколько утрировано :)
Прекрасная статья!

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

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

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

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

Однако, если алгоритмы нужно применять в библиотеках, тот тут появляется мета-цель сделать эффективный алгоритм, потому что не все пользователи смогут запросить процессоров и возможно им придётся пересчитывать сходные задачи по многу раз.
UFO landed and left these words here
Честно говоря, понимаю Вас — когда я учился я тоже не понимал, насколько все эти знания могут быть полезны в моей практике, как программиста.

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

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

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

Сначала да, не нужно было. А вот теперь я с огромным удовольствием читаю вот такие вот статьи (однозначно в фейворитс на будущее и +1 за труды автору)
UFO landed and left these words here
Создавайте, вам же никто не мешает! Только не следует выдавать такую практику за единственно возможную. Другие люди могут делать по-другому.
Спасибо за отменную статью! У Вас талант к подаче материала)

П.С. Хабр торт!
Монойд — полугруппа с единицей, думаю возможно когда вы описывали что такое полугруппа и добавив единицу к конструкции нужно было упомянуть что это полугруппа.
Конечно, нужно.
Эх, сколько бы я еще всего упомянул здесь, будь у меня ещё хоть треть-столько же байт доступно для заполнения…
Отличный стиль изложения и оформление статьи. Нечасто бывает, что длинные и не совсем простые для понимания статьи получается дочитать до конца, а главное всё осмыслить.
UFO landed and left these words here
Хорошая статья. В этой статье habrahabr.ru/blogs/algorithm/105450/ я использовал похожий подход.
Но в основе были полукольца. А точнее, конечные автоматы на тропическом и вероятностном полукольцах. В статье об этом не написано, т.к. не решился писать про кольца, моноиды и т.п. Но математика работает красиво.
Отличная статья! В институте как раз закончился семестр теории групп, было интересно узнать где она применяется.
Не понимаю, раз в Java такая структура данных используется (Rope), почему конкатенации такие дорогие.
Или создавать новые ноды так дорого стоит?
В яве ropes не используются для хранения строк. Используется просто массив символов из-за чего и получается долгая конкатенация.
Почему не ropes — вероятно потому что более долгое время доступа к элементам и оверхед по памяти.
Есть статья от Эрика Липперта, в которой он делится опытом создания такой структуры и причинами, по которым они в последующих проектах от них отказались.
Only those users with full accounts are able to leave comments. Log in, please.