Результаты конкурса ПФП–2009

В третьем выпуске нашего журнала мы объявили конкурс для программистов. Каждый уважающий себя журнал считает необходимым публиковать конкурсы, викторины и кроссворды с целью собственной популяризации. Естественно, что и мы обязаны были придумать свой собственный конкурс — такой, который бы сумел показать неоспоримое преимущество подхода и инструментальных средств, предлагаемых функциональным программированием, над обычными инструментами императивного программирования.

Детали подготовки к конкурсу

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

Почему задания не могли быть слишком простыми? Мы хотели оценить, как использование различных пакетов инструментов влияет на эффективность решения задач. Простые задания зачастую могут решаться парой магических заклинаний в каких-то эзотерических языках, что совершенно ничего не сможет сказать о практике, дневной рутине написания чего-то более стоящего или объемного с помощью этих инструментов. Повышенная, неигрушечная сложность задач не могла не повлиять на желание людей участвовать в конкурсе. Чтобы компенсировать этот эффект, нами были предложены материальные призы и проведена дополнительная работа по популяризации конкурса.

Задания мы собирали «всем миром», опубликовав соответствующие призывы на страницах личных журналов Дмитрия Астапова и Льва Валкина. Слишком математические, слишком хорошо ложащиеся на функциональную парадигму и слишком хорошо решаемые с помощью существующих в мейнстримных языках библиотек задания были отброшены сразу. Оставшиеся несколько десятков заданий были предложены для оценки нескольким известным специалистам, «представляющим» разные парадигмы программирования.

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

Ожидаемые результаты

Мы приложили силы к тому, чтобы конкурсом заинтересовалось как можно большее количество читателей журнала: были выбраны практические, достаточно повседневные задания, проведена реклама конкурса и обеспечены материальные призы. В каждой задаче было выделено несколько уровней сложности с тем, чтобы простейшее рабочее решение можно было получить буквально за пару часов работы.

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

Ожидалось, что будут непропорционально представлены два-три объектно-ориентированных языка (C++, C#, Java), а остальные, включая функциональные, будут представлены в гораздо меньшей степени.

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

Первичная статистика по решениям

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

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

С другой стороны, поразил разброс в языках программирования, использованных для решения задач. Вместо ожидаемого доминирования объектно-ориентированных языков, для задачи об усечении карты мы получили два варианта на OCaml и по одному варианту на языках Haskell, Erlang, Common Lisp, Python, C#, Visual Basic, Ada. Три решения по составлению плана-графика были написаны на Python, Haskell и Clojure.

Нас особенно порадовали варианты решений на Ada и Visual Basic. Это означает, что задания были подобраны корректно, без перекосов в сторону функционального программирования.

Какие же закономерности можно обнаружить в когорте из десяти решений? Давайте посмотрим!

Разбор полётов

Каждое задание оценивалось пятью членами жюри. Жюри оценивало исключительно исходные тексты решений, а функциональное тестирование и оценка производительности производились отдельно. В составе жюри все декларировали знакомство C/C++; с языками Haskell, OCaml, Java и различными диалектами Lisp было знакомо по два человека; а в C#, F#, Erlang и Clojure разбирался только кто-то один. Состав жюри можно условно разделить на двух человек «более функциональных», двух «более императивных» и одного «непримкнувшего».

Члены жюри и редакции журнала в конкурсе участия не принимали.


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

АвторЯзыкLOCОценка жюри
Е. ЗайцевPython10013.6
К. ЛопухинClojure6943.4
Р. СалминHaskell16642.8

Все решения используют разные подходы к отысканию оптимального плана-графика. В то же время, их объединяет то, что при отсутствии решения они не могут внятно уведомить пользователя о том, в чем же заключается проблема.

При сопоставлении редакцией журнала отчётов жюри по этому заданию выявилась интересная особенность: мнения членов жюри слабо коррелировали друг с другом. Например, вот цитаты из пары отчётов по решению на Haskell:

Эксперт–1Эксперт–2
«Код в достаточной степени документирован. Разбиение на модули сделано хорошо, реализация функций — небольшая, так что читать код достаточно легко.»«Код заточен под конкретную задачу, разбиение на модули в некотором роде от фонаря, повторно использовать будет сложновато.»

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

Соответственно, во главу угла ставились следующие признаки:

Четыре решения были отсеяны сразу по признаку корректности работы. Решение на Python впадало в бесконечный цикл на карте Московской области. Решение на Erlang порождало файл нулевой длины на карте Германии. Решение на Haskell не смогло корректно обработать все случаи рекурсивного включения объектов и оставляло в выходном файле лишние узлы. Решение на языке Ада оставляло в выходном файле ссылки на удаленные узлы и пути.

Язык OCaml был представлен двумя решениями от разных авторов. Одно из них без сбоев прошло все микротесты, кроме проверки на перенос из входного файла в выходной «незнакомых» тэгов. Второе решение не реализовывало режим обрезки «complete objects» и не прошло ряд микротестов. Тем не менее, эти решения не зависали на реальных картах и порождали результирующие ответы, похожие на корректные. Поэтому мы решили включить их в сводную таблицу решений, представляющих интерес.

ЯзыкLOCСкоростьОценка жюри
C#8541533.6
Visual Basic2253413.4
Common Lisp899743.1
OCaml–14492883.3
OCaml–23701582.8

В таблице жирным шрифтом отмечены лучшие результаты. Под «скоростью» понимается средняя скорость вырезки регионов из нескольких больших файлов карт, в секундах. Так, решение на Common Lisp оказалось самым быстрым, со средним результатом 74 секунды.

Редакция приняла решение разделить третье место между решениями на Common Lisp и OCaml и распределить призовые места следующим образом:

 АвторЯзык
1П. ЕгоровC#
2А. ВолковVisual Basic
3А. ВознюкCommon Lisp
3Д. ПоповOCaml

Отмеченная ранее слабая корреляция оценок жюри во всей красе наблюдалась и в этом конкурсе. На рис. 1 наглядно видно, что оценки идут вразнобой. Интересно было бы вывернуть конкурс наизнанку и искать зависимости внутри оценок жюри, а не в результатах выполнения конкурсных заданий!


Рис. 1: Разброс индивидуальных оценок членов жюри

Итоги

Поздравляем Павла Егорова и Евгения Зайцева с победой в соответствующих разделах конкурса! Поздравляем Алексея Волкова, Алексея Вознюка, Константина Лопухина, Дмитрия Попова, Романа Салмина с призовыми местами. Спасибо, что нашли время и потратили его с пользой для человечества! Для передачи призов мы свяжемся с вами по электронной почте.

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

У большинства решений нашлось два общих слабых места. Во-первых, это отсутствие инструментов, облегчающих сборку из исходников, а во-вторых — отсутствие внятных уведомлений об ошибках. Даже те решения, которые сопровождались Makefile-ом или его аналогом, почти всегда требовали «доводки напильником», а вместо внятной диагностики ошибок почти всегда выдавали стандартные сообщения вида «Runtime error 23454 at address 0xdeadbeef».

Мы были приятно удивлены призовому месту решения на Visual Basic. Надо отметить его краткость и простоту кода. Решение «в лоб», без особых изысков в плане алгоритмов и структурирования программы, победило в практичности большинство своих аналогов на языках функционального программирования.

Среди недостатков присланных решений на языках функционального программирования надо отметить излишнее мудрствование: использование нетривиальных решений, отказ от использования библиотек синтаксического анализа XML, метапрограммирование, когда задача решалась более простыми средствами, не слишком теряя при этом в производительности. Сравните, например, решение на Visual Basic с решением OCaml–1: различие в производительности в двадцать процентов было получено ценой двукратного увеличения количества кода. Кстати, в этом выпуске журнала есть статья Дмитрия Попова (одного из участников конкурса) о синтаксическом анализе, содержащая, в частности, сравнительный анализ скорости работы различных библиотек синтаксического анализа XML (см. раздел «Сравнение с другими методами парсинга»).

С другой стороны, в каких-то случаях такое мудрствование может быть оправдано. Вариант на Common Lisp, использующий несколько стадий метакомпиляции, кажется сложным для понимания (впрочем, автор все доходчиво рассказал в своем LiveJournal), но может похвастаться абсолютным рекордом скорости выполнения обрезки карт. Он может служить неплохой иллюстрацией к статье «Лисп — абстракции на стероидах» Виталия Маяцких, опубликованной в предыдущем выпуске нашего журнала.

Интересно отметить, что победившее решение на C# вызвало у жюри более полярные мнения, чем решение на Visual Basic. Вот пара отзывов о победившем решении:

Эксперт–3Эксперт–4
«Программа реализована в лучших традициях продакшен программирования, простой первый прототип и аккуратно реализованный с разбиением на подпроекты и множеством вспомогательных утилит итоговый проект.»«Декомпозиция: лютый овердизайн. Как будто платят за строчки кода. Куча мусора, не относящегося к задаче. Смысл утоплен в деталях реализации.»

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

А всем тем, кто собирался поучаствовать в конкурсе, но по каким-то причинам не стал, желаем в будущем быть более решительными.

Исходные тексты решений, занявших призовые места, можно найти на сайте журнала.


Дмитрий Астапов, adept@fprog.ru



Обсуждение результатов конкурса ведётся в LiveJournal.

Этот документ был получен из LATEX при помощи HEVEA