Acceler8 2011 — Accelerate 2012 — и так далее

в 13:33, , рубрики: Блог компании Intel, конкурс, ненормальное программирование, параллельное программирование, Программирование, Спортивное программирование, метки: , ,

Acceler8 2011 — Accelerate 2012 — и так далее
Вы участвовали в конкурсе параллельного программирования Acceler8 2011? Тогда этот пост — про вас.
Вы участвуете в проходящем сейчас конкурсе Аccelerate-2012? Тогда этот пост — для вас.
Вы принимали участие или только планируете участвовать в любом конкурсе спортивного программирования? А может, собираетесь начать свой первый самостоятельный проект? Тогда Вас, Штирлиц, я попрошу остаться с нами.

Этот пост — «разбор полетов» прошлогоднего конкурса Intel — Acceler8 2011, выполненный одним из членов жюри. Он прокомментировал ключевые конкурсные моменты, а также дал банальные и очевидные, но до сих пор актуальные советы по участию в подобных соревнованиях и по ведению проектов.

Итак, поехали!

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

Задача конкурса

Ох, каких только нелестных эпитетов выслушали организаторы конкурса по поводу поставленной задачи. Методом проб и ошибок она была приведена к более-менее приемлемому виду. Но после получения первых решений, мы осознали насколько она была богата на различные оптимизации. Основной упор участники (ожидаемо) сделали на вычисление «периодических» матриц и параллелизацию. Но некоторые конкурсанты также сделали теоретические исследования алгоритма, оптимизации выделения памяти и хранения матриц, их заполнения, способов их обхода. В глазах жюри конкурса такой подход к решению задачи прибавлял минимум +100 к карме участника.

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

Качество кода

Тут организаторы конкурса прочувствовали истинность народной китайской поговорки «не важно какого цвета кошка, если она ловит мышей». Каких только витиеватых конструкций и выражений не было в коде. Организаторы вспомнили свою юность, когда писали почти так же. Приведу TOP-5 «неловких» мест в проектах:

5 место (хитрая инициализация указателя в конструкторе): m_memory_pointer((char*)this + 1024)
4 место (инициализация переменной): static const int min_int = -2147483648;
3 место: сравнение структуры с указателем. Как это вообще скомпилировалось под Linux?
2 место: main.c файл на 1900 строк. Парни, серьёзно, как вы в нём ориентируетесь?
1 место (почти десяток претендентов): несоблюдение формата ввода-вывода.

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

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

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

Качество алгоритмов

Признаюсь, моим фаворитом в прошедшем конкурсе была команда KomsomolskDV. Чувствуется, что парни имеют достаточно богатый опыт участия в подобных соревнованиях. Они подошли к исследованию алгоритма до такой степени педантично, что даже вычислили теоретическое время работы алгоритма в тактах. Если бы все участники провели подобные исследования, то нам бы не пришлось запускать приложения. Достаточно бы было сравнить теоретические времена вычислений.
Также некоторые участники описали в своих сопроводительных документах ход их мыслей, с чего они начинали, как развивалась их мысль.
Если представить ход мыслей участников в виде графика (хм, интересно, возможен ли такой график?), то до каких-то базовых улучшений додумались почти все участники. С ростом хитрости и сложности какой-то идеи количество справившихся участников резко падало.

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

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

В заключение хочу сказать, что участники конкурса доставили много весёлых минут организаторам.
Почти совет: Относитесь к программированию, как серьёзной игре. С одной стороны, всё должно работать, с другой — процесс разработки должен приносить радость.

Например, почему бы не оставить в комментариях «послание» будущим поколениям?

Автор: victor_cherepanov

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js