Время: 2 недели (8 февраля — 22 февраля 2010 г.)
Конкурс завершён.. Здесь подводятся его итоги.

На своем блоге я буду проводить много конкурсов, связанных (прямо или косвенно) с научными задачами. Конкурсы будут как с платным, так и с бесплатным участием. Это первый конкурс, и чтобы не распугать людей, он будет с бесплатным участием, но и призовой фонд будет не слишком большим — 1000 р.. По этой причине предлагается задача, которую любой опытный программист сможет реализовать за 10-15 минут (а при знании продвинутых алгоритмов — за час): перемножение двух квадратных матриц с заданным размером n на n. Победителем станет тот, чья реализация будет работать быстрее реализаций остальных участников (подробности о числе победителей ниже). Хотите заработать 1000 р. за (максимум) час работы? Тогда участвуйте!

Положения

Общие правила и ограничения

  1. Операционная система — Windows XP SP3.
  2. Тестирование производится на компьютере с процессором Intel Core 2 Duo 8400 (3000 MHz) 2GB DDR2-800.
  3. Программа должна использовать не более одного процесса и одного потока в нём. Несмотря на то, что процессор двухъядерный, разрешается использовать только одно ядро на 100% его мощности.
  4. Запрещено использовать динамически-подключаемые библиотеки (dll).
  5. Программа должна быть представлена в виде одного только исполняемого EXE файла и работать корректно без необходимости установки дополнительного ПО. Исходите из варианта, что у Вас есть лишь «голый» Windows XP.
  6. Программа должна использовать не более 1Gib (230 байт) оперативной памяти.
  7. Время работы программы на каждом тесте не должно превышать 900 секунд.
  8. Максимальный порядок матрицы в тесте n = 5000.
  9. Элементы матрицы — целые числа, не превосходящие по модулю 600.
  10. Программа должна работать в консольном режиме, то есть никаких графических интерфейсов писать не нужно. Ваша программа считывает матрицы из входного файла (который будет находится в той же директории), перемножает их и выводит ответ в другой файл (в ту же директорию). Подробнее о формате ввода / вывода см. ниже.
  11. Конкурс завершается 22 февраля ровно в 12 ч. 00 м.
  12. Оплата только через Яндекс.Деньги или WebMoney.
  13. Я оставляю за собой право менять правила проведения конкурса, если в них обнаружатся неточности.

Порядок проведения конкурса

  1. Во время проведения конкурса участники посылают на электронный адрес «zealint.comp@gmail.com» письмо с темой «Быстрое Перемножение Матриц — Конкурс». В теме необходимо указать свой ник, язык программирования и название компилятора, которым вы пользовались, укажите какими надстройками вы пользовались (boost, atlas, blas и т. д.) или вы реализовали алгоритм самостоятельно (ручная реализация). Прикрепите к письму EXE файл, который будет тестироваться. Файл назовите «<ваш ник>.exe». Внимание: узнал, что gmail не пропускает EXE файлы даже в сжатом виде. Давайте переименовывать их в mp3 и архивировать rar или zip.
  2. По мере тестирования поступающих программ, результат их работы будет указываться в таблице рейтинга, внизу этой страницы. Участник может присылать новые версии программы не более одного раза в сутки. Если участник посылает более одной версии за сутки, учитывается только последняя, а остальные удаляются.
  3. Присланная участником версия программы засчитывается и попадает в рейтинг только в том случае, если она выполняет все тесты без ошибок, укладывается в указанные ограничения по времени и по памяти, а также (если это не первая версия автора) работает хотя бы на 2% быстрее его предыдущей программы.
  4. Победившим считается тот участник, программа которого оказалась самой быстрой на момент завершения конкурса. Но при условии, что она работает хотя бы на 1% быстрее, чем программа его ближайшего соперника. Если времена работы лучших программ у нескольких человек отличаются менее, чем на 1%, то приз делится между победителями поровну.
  5. (Дополнено 10.02.2010) Поскольку я тоже участник конкурса, мне проще участвовать. Поэтому я предлагаю уровнять шансы: как только моя программа оказывается в ТОПе, или просто начинает работать быстрее, я сразу делюсь подсказками о том, как я её улучшил. Только не ждите, что это будут прямые подсказки типа листингов кода.

Формат входных и выходных данных

  1. Программа должна считывать данные из файла «input.txt».
  2. Программа должна записывать ответ в файл «output.txt» (и должна сама создавать его по мере необходимости). Запрещается выводить какую-либо информацию на экран.
  3. Во входном файле содержится следующая информация: в первой строке записано число n — порядок матриц. В следующих n строках, в каждой из которых n чисел, записаны строки первой матрицы, а дальше точно так же (n строк по n чисел) записана вторая матрица. Например, так может выглядеть входной файл:
    2
    1 3
    3 4
    2 1
    0 3
    в нем две матрицы 2×2. В выходной файл нужно записать результат произведения матриц:
    2 10
    6 15
    Все числа отделяются друг от друга пробелом или табуляцией, а также символом перевода строки.

Гарантии

Я гарантирую, что победитель(и) получит(ат) приз в соответствии с правилами. Во-первых, я собираюсь проводить другие конкурсы. Зачем мне кого-то обманывать? Во-вторых, вы же мне ничего не платите, и я даже не требую предоставлять мне исходный код программы. В-третьих, если вы подумали, будто мне нужна программа перемножения матриц и будто я сам не могу её нормально написать, то это далеко не так. Тысячу рублей я так просто не отдам — соревнуйтесь со мной и заберите приз! : ) После завершения конкурса я предоставлю тесты, на которых проверялись ваши программы, и вы сами сможете потестировать. Заметьте, что я не запрещаю пользоваться самыми продвинутыми на сегодняшний день средствами программирования, в том числе библиотеками, в которых есть функции работы с матрицами. Мне нужен только один исполняемый файл, все честно. Так что не волнуйтесь.

Пожелания

По мере проведения конкурса привлекайте новых участников. Мой блог не так сильно раскручен, поэтому участие хотя бы 10 человек я буду считать большим успехом.

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

Если пишите комментарии, то подписывайтесь тем ником, который у вас отображается в таблице рейтинга (если отображается).

FAQ

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

  1. Что за тупой конкурс? Ответ: идите нафиг.
  2. Вы правда думаете, что за 1000 р. люди сразу побегут к вам писать программы? Ответ: не нравится — не участвуйте. 1000 р. за 15 минут (или за час) работы я считаю нормальным. Конкурс не для всех, а для тех, кому интересно писать оптимальный код. В будущем я сделаю другие конкурсы. Но они будут гораздо сложнее. Настолько, что даже профессионалам будет здесь делать нечего. Это будут конкурсы для математиков-программистов, а не для промышленных программистов. И призы будут на порядок больше. Но все это так сразу не делается, я провожу свой первый конкурс, поэтому он такой простой и недорогой.
  3. Тут без ассемблера и SSE не обойтись! Ответ: я совершенно не ограничиваю вас в выборе инструмента. Такой вопрос часто задают те, кто плохо понимает для чего нужен ассемблер. Предупреждаю, что машинной оптимизацией лучше заниматься после того, как выполнили все алгоритмические оптимизации. Например, посмотрите на время работы моих программ v0 и v1. Разница почти в пять раз. Оптимизация до жути простая — замена второй матрицы на транспонированную с соответствующим изменением порядка суммирования. И ВСЕ! Причина простая — кэш стал использоваться более оптимально. Так что думайте прежде, чем садиться за машинный код.
  4. Я 5 лет работаю программистом и понятия не имею что такое Перемножение Матриц. Ответ: программисты бывают разными, например, web-программисты и т. д. Конечно же, если вы не понимаете в чем состоит задача и почему в ней надо думать — это конкурс не для вас. Это для тех, кто умеет писать оптимальный код для вычислительных задач, то есть для тех, кто на этом специализируется. Конечно же этим конкурсом я не хочу обидеть остальных программистов, которые сильны в какой-то своей области. Это просто не для них и все.
  5. То, что вы являетесь участником и организатором дает вам те или иные преимущества — это нечестно, например, вдруг Вы мега-крутой программист и уже написали кучу программ, а самую лучшую оставили на потом и «спалите» её в конце, когда не будет времени отыграться? Ответ: ничего подобного. Моя самая лучшая программа — это та, которая в рейтинге. Я точно так же, как и все участники начинаю думать «что делать?», когда меня кто-то обгоняет. Здесь, конечно, вам придется поверить на слово. Скажите тогда, а зачем мне надо было делать конкурс? Чтобы поиздеваться над народом? Нет, я делаю его для того, чтобы понять чего можно выжать из различных подходов и пр. Вот если бы конкурс был с платным участием, то я бы понимал ваши опасения, а так, что волноваться-то? Впрочем, я понимаю, что одно преимущество у меня все-таки есть — я получаю программы в своё распоряжение и могу делать с ними что угодно, например, анализировать время работы на самых разных тестах (не выпадающих из условий). Что это даёт? Появляется интуитивное ощущение того, что лучше а что — хуже. Поэтому я, пожалуй, изменю немного правила. Как только улучшается время работы моей программы, я сообщаю, каким методом я это время улучшил. Итак, почему моя v1 работает быстрее v0 я написал в ответе на вопрос 3. Остальное будут выписывать в комментариях. В конце конкурса сделаю резюме.
  6. Что значит «голая» винда? Ответ: Windows XP SP3 32-bit. Хотя если я не указал этого ранее, то, видимо, не так важно. В целом, они все довольно хорошо совместимы и все-таки понятно, что XP пока более распространена (из всех Windows). Главное здесь пожалуй — 32 бита.
  7. А вы учли, что размер входного вайла 238Mб и оно долго считывается? Ответ: Конечно, в моей программе ввод занимает 12 секунд и вывод около того. Эту часть кода я буду оптимизировать после того, как время самих вычислений окажется более-менее сравнимым с временем ввода. Считывание из файла — принципиальное ограничения конкурса. И вообще, ограничения обсуждению не подлежать. С одним замечанием только соглашусь — я обидел тех, кто любит Linux. Но для них конкурс ещё будет.

Окончательный рейтинг

Конкурс завершён. Здесь подводятся его итоги.

Таблица ниже будет постоянно обновляться по мере поступления новых программ. Внимание: прежде чем присылать программу, убедитесь, пожалуйста, что она укладывается в отведённое время на самом большом тесте и при этом не использует оперативной памяти больше, чем указано в правилах. Также убедитесь, что она работает не намного медленнее, чем реализация текущего лидера (учтите также разницу между вашим процессором и тем, на котором я тестирую). Удачи!

  1. venco[v4] :: C++ GCC 4.0.2 :: 21.02.10 :: 7,52 с.
  2. venco[v3] :: C++ GCC 4.0.2 :: 20.02.10 :: 8,86 с.
  3. venco[v2] :: C++ GCC 4.0.2 :: 18.02.10 :: 9,3 с.
  4. venco[v1] :: C++ GCC 4.0.2 :: 16.02.10 :: 10,84 с.
  5. blackmirror[v1] :: fasm :: 22.02.10 :: 11,13 с.
  6. Zealint [v7] :: Intel C++ 11.1 + ASM (Вин.-Штр.) :: 22.02.10 :: 11,33 с.
  7. Zealint [v6] :: Intel C++ 11.1 + ASM (Вин.-Штр.) :: 21.02.10 :: 12,66 с.
  8. venco[v0] :: GCC 4.0.2 + GCC Intrinsics :: 15.02.10 :: 13,22 с.
  9. Zealint [v5] :: Intel C++ 11.1 + ASM (р. реал.) :: 19.02.10 :: 18,34 с.
  10. alexBlack [v3] :: Delphi (ручн. реал.) + MMX :: 14.02.10 :: 19,2 с.
  11. blackmirror[v0] :: Microsoft Visual C++ 2008 :: 18.02.10 :: 22,14 с.
  12. alexBlack [v2] :: Delphi (ручн. реал.) + MMX :: 12.02.10 :: 22,8 с.
  13. Zealint [v4] :: Intel C++ 11.1 + ASM (р. реал.) :: 16.02.10 :: 33,00 с.
  14. ghoul [v2] :: GCC 3.4.5 + gotoBLAS2 1.13 :: 12.02.10 :: 35,84 с.
  15. Zealint [v3] :: Intel C++ 11.1 (ручн. реал.) :: 13.02.10 :: 55,09 с.
  16. Ulex :: Masm 6.14.8444 :: 11.02.10 :: 57,74 с.
  17. covax :: MS VC 2010 :: 15.02.10 :: 62,89 с.
  18. Zealint [v2] :: Intel C++ 11.1 (ручн. реал.) :: 11.02.10 :: 94,58 с.
  19. alexBlack [v1] :: Delphi (ручн. реал.) :: 11.02.10 :: 106,3 с.
  20. alexBlack [v0] :: Delphi (ручн. реал.) :: 10.02.10 :: 112,2 с.
  21. ghoul [v1] :: GCC 3.4.5 + gotoBLAS2 1.13 :: 11.02.10 :: 124,31 с.
  22. yakasuka :: VS6 (ручн. реал.) :: 10.02.10 :: 144,44 с.
  23. Zealint [v1] :: GCC 3.4.5 (ручн. реал.) :: 10.02.10 :: 154,78 с.
  24. ghoul [v0] :: GCC 3.4.5 + BLAS :: 10.02.10 :: 310,88 с.
  25. Zealint [v0] :: GCC 3.4.5 (ручн. реал.) :: 8.02.10 :: 805,56 с.

Следите за конкурсами на моём блоге, дальше будет сложнее и интереснее.

Информационные спонсоры

КиберФорум — форум начинающих и профессиональных программистов, системных администраторов, администраторов баз данных. Компьютерный форум.

Клуб ПРОграммистов — Форум программистов.

Обсуждение конкурса на форуме в этой теме.