итоги алисы и боба
Подвожу итоги этого соревнования.
Довольно скоро после его начала стало понятно, что все можно сделать очень быстрым (хоть и квадратичным) вычислением, и конкурс по сути дела нивелировался в состязание того, кто выжмет это вычисление и вывод результатов в меньше миллисекунд.
К сожалению, я недостаточно жестко задал условия для того, чтобы честно и интересно делать такие микро-сравнения. Например, я заранее решил, что буду считать время запуска с командной строки, но это отсеивает все решения на Питоне просто из-за времени запуска интерпретатора, хотя в главном цикле некоторые из них, возможно, и посоревновались бы с другими.
Всего было около 20 решений, с следующим разбросом по языкам: 8 питон, 3 C, 4 C++, и по одному: Perl, Kotlin, C#, Clojure, Rust. Если я забыл или не учел чей-то вариант, прошу простить, мне их приходилось собирать из четырех источников (три блоггинг-платформы и мой мейл). Все исходники вместе я решил не собирать, вряд ли этоочень интересно; почти все можно найти в комментариях к записи о конкурсе в ЖЖ, ФБ и ТГ.
Помучившись немного, я решил присудить приз анонимному участнику, приславшему решение на C++, делающее все вычисления
в темплейтах во время компиляции, так что программа компилируется 6 секунд, но при запуске сразу выводит результат. Можноспорить с тем, отвечает ли это условиям - наверное да, т.к. я вроде и запретил "выводит сразу готовый результат", но
объяснил это тем, что надо его честно вычислить, а это тут происходит, просто во время компиляции. В конечном итоге, участник сделал ту же работу, что и почти все остальные (см. ниже), но вдобавок извратился с записью ее в compile-time
metaprogramming, и выжал максимально возможный для C/C++ перформанс, так что заслужил эти $100, так я решил. Этот код я выложил здесь: https://gist.github.com/avorobey/bc3f8128392a731a8bb65ea2edd8c0bd
Update: победитель - блоггер epimorphisms-split на DreamWidth: https://epimorphisms-split.dreamwidth.org/
Вместе с тем, хочу отметить несколько других достижений:
1. Почти все решения отслеживали число игр с перевесом X для всех X одновременно и для растущего числа бросков (обычно
добавляя по одному броску в конец, изредка расщепляя длинные цепочки пополам). Однако в комментариях в телеграм-каналекрутые и дотошные комментаторы (горжусь) добили решение через возведение в степень матрицы перехода цепи Маркова, через
алгоритм NTT (обобщение дискретной трансформации Фурье), позволяющий побить квадреатичный подход. На 100 бросках у этогокода нет шанса победить, но на многих тысячах он уже работает быстрее квадратичного. Посмотрите, если вам интересно:
https://t.me/avvablog/2257?comment=327710 и немного до и после этого комментария
2. Телеграм-юзер @satorin первым прислал решение (на Котлине), через 33 минуты после того, как я отправил запись! https://pl.kotl.in/dnSEA_QyB Он пишет: "Кстати, никому не нужен фронтендер или фуллстек? :)" Работодателям советую
обратить внимание :)
3. Это решение ЖЖ-юзера jsn на Clojure чисто по coolness factor, ну посмотрите сами на исходный код и поймете, о чем я:
https://gist.github.com/jsn/b0cec248603fbf47bc3a3e776917ad5b
Спасибо, извините, если кого-то разочаровал или что-то не учел, это было импульсивным решением и у меня было очень ограниченное
время на то, чтобы все решения собрать и сравнить, но надеюсь, вам понравилось. Попробуем еще что-то подобное в другой раз.
Довольно скоро после его начала стало понятно, что все можно сделать очень быстрым (хоть и квадратичным) вычислением, и конкурс по сути дела нивелировался в состязание того, кто выжмет это вычисление и вывод результатов в меньше миллисекунд.
К сожалению, я недостаточно жестко задал условия для того, чтобы честно и интересно делать такие микро-сравнения. Например, я заранее решил, что буду считать время запуска с командной строки, но это отсеивает все решения на Питоне просто из-за времени запуска интерпретатора, хотя в главном цикле некоторые из них, возможно, и посоревновались бы с другими.
Всего было около 20 решений, с следующим разбросом по языкам: 8 питон, 3 C, 4 C++, и по одному: Perl, Kotlin, C#, Clojure, Rust. Если я забыл или не учел чей-то вариант, прошу простить, мне их приходилось собирать из четырех источников (три блоггинг-платформы и мой мейл). Все исходники вместе я решил не собирать, вряд ли этоочень интересно; почти все можно найти в комментариях к записи о конкурсе в ЖЖ, ФБ и ТГ.
Помучившись немного, я решил присудить приз анонимному участнику, приславшему решение на C++, делающее все вычисления
в темплейтах во время компиляции, так что программа компилируется 6 секунд, но при запуске сразу выводит результат. Можноспорить с тем, отвечает ли это условиям - наверное да, т.к. я вроде и запретил "выводит сразу готовый результат", но
объяснил это тем, что надо его честно вычислить, а это тут происходит, просто во время компиляции. В конечном итоге, участник сделал ту же работу, что и почти все остальные (см. ниже), но вдобавок извратился с записью ее в compile-time
metaprogramming, и выжал максимально возможный для C/C++ перформанс, так что заслужил эти $100, так я решил. Этот код я выложил здесь: https://gist.github.com/avorobey/bc3f8128392a731a8bb65ea2edd8c0bd
Update: победитель - блоггер epimorphisms-split на DreamWidth: https://epimorphisms-split.dreamwidth.org/
Вместе с тем, хочу отметить несколько других достижений:
1. Почти все решения отслеживали число игр с перевесом X для всех X одновременно и для растущего числа бросков (обычно
добавляя по одному броску в конец, изредка расщепляя длинные цепочки пополам). Однако в комментариях в телеграм-каналекрутые и дотошные комментаторы (горжусь) добили решение через возведение в степень матрицы перехода цепи Маркова, через
алгоритм NTT (обобщение дискретной трансформации Фурье), позволяющий побить квадреатичный подход. На 100 бросках у этогокода нет шанса победить, но на многих тысячах он уже работает быстрее квадратичного. Посмотрите, если вам интересно:
https://t.me/avvablog/2257?comment=327710 и немного до и после этого комментария
2. Телеграм-юзер @satorin первым прислал решение (на Котлине), через 33 минуты после того, как я отправил запись! https://pl.kotl.in/dnSEA_QyB Он пишет: "Кстати, никому не нужен фронтендер или фуллстек? :)" Работодателям советую
обратить внимание :)
3. Это решение ЖЖ-юзера jsn на Clojure чисто по coolness factor, ну посмотрите сами на исходный код и поймете, о чем я:
https://gist.github.com/jsn/b0cec248603fbf47bc3a3e776917ad5b
Спасибо, извините, если кого-то разочаровал или что-то не учел, это было импульсивным решением и у меня было очень ограниченное
время на то, чтобы все решения собрать и сравнить, но надеюсь, вам понравилось. Попробуем еще что-то подобное в другой раз.