Конкурс: можно ли написать быструю программу на C/C++?
По работе попалась несложная, но достаточно интересная задачка из области обработки данных. Так как она была связана с вычислениями над массивами, то я по-быстрому запрограммировал её на Фортране. Но мне стало интересно, насколько эффективным или неэффективным будет её решение на C или C++. Поэтому, если кто любит решать задачки среднего уровня сложности с литкода, тот может поучаствовать в предлагаемом конкурсе, где я упростил эту задачу, оставив только самое интересное.
Условия задачи:
Необходимо написать консольную программу на языке C или C++, транслируемую с помощью clang в юникс-совместимой ОС и выложить в комментариях ссылку на проект. Проект может быть устроен как угодно, но должен транслироваться из командной строки обычными штатными средствами Unix/Linux при помощи написанного вами командного файла с именем build. Там могут быть прописаны такие режимы компиляции, какие вы хотите. Я оставляю за собой право модифицировать их для соответствия возможностям установленного у меня компилятора.
Программа получает в командной строке два параметра — имя текстового файла и целое число R не менее 4. Тестовый файл (20 мегабайт) можно скачать отсюда. Файл содержит размеры прямоугольного массива и сам массив, состоящий из 12-разрядных неотрицательных целых чисел (т.е. со значениями от 0 до 4095), разбитый построчно, с разделением точкой с запятой. Можно считать, что это яркости пикселей в монохромном 4-мегапиксельном кадре изображения.
Необходимо сделать в программе следующее:
Обрезать рамку шириной 16 пикселей с каждой стороны, содержащую нерелевантную информацию.
Найти полностью принадлежащий обрезанному кадру круг радиусом R пикселей, сумма яркостей точек в котором максимальна среди всех возможных в кадре таких кругов. Локальных максимумов яркостей в кадре может быть несколько. Может получиться так, что один круг будет содержать несколько максимумов.
Посчитать и напечатать координаты центра найденного круга и процентное отношение суммы яркостей в найденном круге к общей сумме яркостей в обрезанном кадре с точностью до 0.01%. Если таких кругов с максимальной яркостью окажется в кадре несколько, можно напечатать координаты любого из них (проценты, очевидно, будут одинаковы).
Посчитать и напечатать время вычисления (исключая время чтения файла) с точностью до 0.01 с.
Ссылку на вашу программу вы можете разместить в комментариях. Она должна иметь возможность обрабатывать массивы любого размера, влезающие в свободную оперативную память. Тестировать её я буду на корректность результата на своих собственных примерах, удовлетворяющих условиям задачи, а на корректность результата с зачётом времени — на приведённом по ссылке выше файле тремя командами с разными R:
программа test.txt 300
программа test.txt 100
программа test.txt 4
В каждом из трёх запусков будет учитываться полученный результат расчёта (он должен быть верным) и посчитанное время вычисления. Если результат неверен или время худшего из трёх тестов более чем в 10 раз хуже, чем у референсной фортрановской реализации, ставится оценка «Н/К» (не квалифицирован) без дальнейшей детализации. Иначе в зачёт идёт сумма трёх времён.
У кого будет сумма времён меньше при правильных результатах — тот молодец.
Вырваться вперёд можно как за счёт общего алгоритма, так и за счёт эффективного использования возможностей языка и компилятора.
Ориентировочная трудоёмкость качественного решения задачи — 1 день. Референсная программа на Фортране занимает 100 строк. Референсное время сообщать не буду, так не интересно. Но думаю, что его вполне можно превзойти, так как я не заморачивался слишком уж сильно, стремясь сохранить ясность кода при удовлетворительном времени.
Я оставляю за собой право при необходимости комментировать как квалифицированные, так и не квалифицированные решения.
В комментариях можно задавать уточняющие вопросы, на которые я оставляю за собой право отвечать или не отвечать по существу.
Habrahabr.ru прочитано 71101 раз
