По работе попалась несложная, но достаточно интересная задачка из области обработки данных. Так как она была связана с вычислениями над массивами, то я по-быстрому запрограммировал её на Фортране. Но мне стало интересно, насколько эффективным или неэффективным будет её решение на 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 строк. Референсное время сообщать не буду, так не интересно. Но думаю, что его вполне можно превзойти, так как я не заморачивался слишком уж сильно, стремясь сохранить ясность кода при удовлетворительном времени.
Я оставляю за собой право при необходимости комментировать как квалифицированные, так и не квалифицированные решения.
В комментариях можно задавать уточняющие вопросы, на которые я оставляю за собой право отвечать или не отвечать по существу.
Я готов рассмотреть программы и на других языках программирования, если смогу без труда их скомпилировать и запустить в своей среде.
upd: Референсная программа в зашифрованном архиве находится тут. Ключ я опубликую после проведения конкурса.
Комментарии (91)
cadovvl
04.10.2023 09:15+9Можно для такой задачки информацию о железе какую-то? Например, флаги процессора типа такого:
Model: Intel(R) Xeon(R) CPU E3-1271 v3 @ 3.60GHz
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm cpuid_fault epb invpcid_single pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid ept_ad fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid xsaveopt dtherm ida arat pln pts md_clear flush_l1d
Хотелось бы узнать список установленных на систему пакетов, например, есть ли libclang-common-10-dev, мало ли. Да, в конце-концов, boost установлен?
Про входной файл: он находится в файловой системе, или в tmpfs? На hdd или sdd? А поддерживается ли в системе mmap, включены ли в системе HugePages?
Если я, в какой-то момент, упрусь в скорость чтения входных данных - что с этим делать?
Можно ли использовать несколько потоков, включен ли hyper-threading?
Очень странная постановка задачи для соревнования по скорости работы.
Решение можно очень хорошо заточить под железо. Если железо известно не до конца, можно сделать реализации под разные типы железа (например, c avx512 и avx2), а потом выбрать реализацию в рантайме. Но это промышленная история, а не соревновательная.
В соревнованиях хотелось бы иметь четко указанные условия, чтобы не придти с болидом формулы 1 на гонки по бездорожью.
vadimr Автор
04.10.2023 09:15-3Время чтения файла, как указано в условиях, не учитывается в зачёте.
Можно использовать любые пакеты, входящие в обычные дистрибутивы.
Несколько потоков использовать можно, HT включён.
Программа должна иметь возможность запускаться на разных компьютерах. Проверять буду на обычном десктопе. Если надо, я позже приведу все эти флажки, но это копейки на общем разбросе, который можно получить. Лидеры зачёта получат возможность дополнительного улучшения, если это будет критично.
Практическое содержание исходной задачи состоит в том, что неустановленное лицо, получив с камеры этот кадр на своём ноутбуке, должно иметь возможность быстро его обработать.
cadovvl
04.10.2023 09:15Дайте определение понятию "обычные дистрибутивы.".
Программа должна иметь возможность запускаться на разных компьютерах
Я правильно понимаю, что его нужно иметь возможность запускать и на x86 и на M1? И на little endian и на big endian? Насколько разных?
но это копейки на общем разбросе
Откуда такая информация? Есть какое-то обоснование, почему именно на этой задачи технологии, которые ускоряют производительность программ в сотни раз, конкретно в этой не заработают? Вот тут "копейки" - это в 3.5 раза.
Практическое содержание
Так мы вам практическую задачу решаем, или у нас соревнование?
vadimr Автор
04.10.2023 09:15Я правильно понимаю, что его нужно иметь возможность запускать и на x86 и на M1? И на little endian и на big endian? Насколько разных?
А насколько это важно для вашей программы? Референсная программа работает на любой архитектуре. Но для простоты можно ограничиться x86_64.
Есть какое-то обоснование, почему именно на этой задачи технологии, которые ускоряют производительность программ в сотни раз, конкретно в этой не заработают? Вот тут "копейки" - это в 3.5 раза.
Секунду, 3.5 раза – это разница между чем и чем? Если между применением конвейера и его неприменением, то это естественно. А если между компиляцией под avx512 и avx2, то где это показано?
like_the_sun
04.10.2023 09:15Мало вводных: версия компилятора, разрешено ли многопоточное решение,
В идеале было бы хорошо иметь референсное наивное решение для определения корректности 'своего решения' и 'замера времени'.
Мне кажется более удобным предоставлять решения в виде динамической библиотеки с интерфесом(проекта, котрый собирается в библиотеку):
void solve(void** matrix, size_t N, size_t M, rad_t(?) R, dim_t* resx, dim_t* resy);
таким способом замерить и проверить любое решение можно довольно просто автоматизировать.
vadimr Автор
04.10.2023 09:15Мне не хотелось бы привязываться к конкретной версии компилятора именно потому, что в спорных случаях оценку производительности лучше бы произвести на разных компиляторах и системах. Поскольку у нас нет призового фонда, то вряд ли возникнут кровавые споры.
Я на основной машине использую clang 17.0.1
vadimr Автор
04.10.2023 09:15Что касается динамической библиотеки. Я не хочу ограничивать желающих определённым способом загрузки и определённым окружением главной программы, а уж тем более – определённым представлением матрицы в памяти.
like_the_sun
04.10.2023 09:15+1Способ загрузки в первую очередь снимает с вас достаточное количество усилий связанных с влезанием в код каждой программы для проверки корректности ее оценки, например, времени выполнения.
Никто не мешает иметь внутреннее представление матрицы, при вашем подходе во время загрузки матрицы можно сразу класть данные в нужном представлении и не учитывать это время.
vadimr Автор
04.10.2023 09:15+1В код каждой программы всё равно придётся внимательно влезать. Потому что решение может работать только в частном случае. Или, в пределе, недобросовестный участник может просто распечатать заранее посчитанные ответы.
Что касается представления матрицы, то я, например, в ходе размышлений над задачей менял его 5 раз. Конечно, во-первых, это было связано с факторами исходной проблемы, не нашедшими отражения в текущей упрощённой формулировке, а во-вторых, все эти действия по существу ничего мне не дали, но тем не менее. А изменение представление матрицы означает, что придётся переписывать код её заполнения в главной программе, поэтому простой линковкой библиотеки тут не отделаться.
iig
04.10.2023 09:15+7Ориентировочная трудоёмкость качественного решения задачи – 1 день.
У кого будет сумма времён меньше при правильных результатах – тот молодец.
1 рабочий день в обмен на знание, что кто-то молодец. Интересный конкурс ;)
vadimr Автор
04.10.2023 09:15Колхоз – дело добровольное.
bfDeveloper
04.10.2023 09:15+6А в чём польза хоть для кого-то? Какие шансы, что при такой постановке условий примут участие действительно крутые программисты, которые могут выжать те самые проценты разницы, которые гипотетически отличают Fortran от C? Вот пришлют вам несколько решений, написанных теми, кому больше заняться нечем, что это вам или им покажет? Скорее всего пришлют не лучшие решения, и что? Вы убедитесь в том, что вы круто пишете на фортране и "ни один сишник так не умеет".
Простите, но выглядит как стремление потешить ЧСВ.
vadimr Автор
04.10.2023 09:15-3Я вам страшную вещь скажу. Разницы в эффективности выполнения Фортрана от Си для крутого программиста вообще нет.
Но мне интересно посмотреть, что и какой ценой в этой задаче, не особо парясь (как и я), может получить программист на C/C++, которых сейчас много и среди которых есть и очень талантливые люди, в том числе и получающие удовольствие от самого процесса.
Данная задача лично мне, кроме зарплаты, доставила и удовольствие от своего решения, потому что она в меру нетривиальна.
Если рассматривать вопрос в терминах ЧСВ, то у меня, в лучшем случае, равные шансы как его потешить, так и получить удар от более сообразительных коллег. И скорее всего потешить не получится. Но моя цель состоит не в этом.
vadimr Автор
04.10.2023 09:15+1В вопросах тут спрашивают о конкретных режимах процессора, но я не думаю, что дело упрётся в них. Для справки скажу, что я при написании референсной программы ускорил её на порядки от наивного решения. А учёт особенностей архитектуры конкретного процессора вам, скорее всего, даст ну процентов 20 максимум, а наиболее вероятно что ещё меньше.
bfDeveloper
04.10.2023 09:15+1То есть вам интересна именно алгоритмическая сторона соревнования? Тогда к чему C/C++ в заголовке и сравнение с фортраном? Алгоритмически задача интересная, но мне кажется я видел её аналог на leetcode.
vadimr Автор
04.10.2023 09:15Эта задача хороша тем, что её можно независимо друг от друга весьма сильно оптимизировать как алгоритмически, так используемыми инструментальными средствами. Выше я хотел сказать только то, что от конкретного процессора (в разумных пределах используемой в современности аппаратуры), по моему разумению, не сильно зависит ни алгоритмическая, ни техническая оптимизация.
cadovvl
04.10.2023 09:15Тут на highload.fun соревнуются в задаче "посчитать сумму чисел" из стандартного потока ввода. Разница в скорости между дефолтным решением на С++ и лучшим примерно в 4 тысячи раз.
Разница лично моего решения, до использования флага avx2 и после - в 4 раза. И я точно выжал из него не все.
Вы лишаете участников возможностей на основе ваших предположений о том, что "нам этот ваш флажок не нужон!". Могли бы просто указать железо: не смогут воспользоваться, ну и не смогут.vadimr Автор
04.10.2023 09:15+1Разумется, я обещаю често рассмотреть все апелляции к особенностям выполнения на конкретном железе.
Но Ваше замечание содержательно, поэтому напишу, что для начала штатно буду запускать на Mac mini (Intel) 2018 3,6 GHz 4 core Intel Core i3:
machdep.cpu.features: FPU VME DE PSE TSC MSR PAE MCE CX8 APIC SEP MTRR PGE MCA CMOV PAT PSE36 CLFSH DS ACPI MMX FXSR SSE SSE2 SS HTT TM PBE SSE3 PCLMULQDQ DTES64 MON DSCPL VMX EST TM2 SSSE3 FMA CX16 TPR PDCM SSE4.1 SSE4.2 x2APIC MOVBE POPCNT AES PCID XSAVE OSXSAVE SEGLIM64 TSCTMR AVX1.0 RDRAND F16Cmachdep.cpu.leaf7_features: RDWRFSGS TSC_THREAD_OFFSET SGX BMI1 AVX2 SMEP BMI2 ERMS INVPCID FPU_CSDS MPX RDSEED ADX SMAP CLFSOPT IPT SGXLC MDCLEAR TSXFA IBRS STIBP L1DF ACAPMSR SSBDmachdep.cpu.extfeatures: SYSCALL XD 1GBPAGE EM64T LAHF LZCNT PREFETCHW RDTSCP TSCImachdep.cpu.core_count: 4machdep.cpu.thread_count: 4
monah_tuk
04.10.2023 09:15В своей работе у меня было только ускорение в 225 раз. Как раз из-за трюка в правильном использовании железа. У нас сделали загрузку битстрима в fpga из user space через jtag интерфейс. Изначальная реализация - битбенг. На этих же gpio был spi. В общем, пока jtag работает в режиме диалога, используем битбенг, как только начинаем слать сам битстрим, переключаемся в spi и испольщуем его аппаратно. Загрузка 3 минуты против 0.8сек.
cadovvl
04.10.2023 09:15О, круто! Но это же прямо железная работа - gpio просто отдельный мир. Мы ковыряли серверные приложеньки только.
Einherjar
04.10.2023 09:15+3У кого будет сумма времён меньше при правильных результатах – тот молодец.
И все? А в чем смысл участвовать тогда? Или суть конкурса в том что решение которое окажется быстрее референсного в итоге его и заменит в том месте где задача возникла?
vadimr Автор
04.10.2023 09:15-5Какой вы тоже корыстный человек. Фу таким быть.
Референсное решение удовлетворяет всем имеющимся требованиям, поэтому его нет смысла менять. Но интересно оценить альтернативы в жизни. Может, я как-то неправильно живу. Я вот думаю, что Фортран на таких задачах намного превосходит C/C++ по отношению эффективности к трудоёмкости, а может я ошибаюсь.
Breathe_the_pressure
04.10.2023 09:15+5Это наверное какой-то приступ неадекватства у вас, да? От статьи сквозит тема "а ну ка докажите мне да за 1 день, что ваш С\С++ лучше чем моя прелесть на букву Ф". Да, кстати, сделайте это просто так. Выложите всё, я имею право решать, подходит мне решение или нет.
На резонные вопросы, зачем вообще тешить ваше самолюбие забесплатно, вы обзываетесь в корысти и фукаете.
vadimr Автор
04.10.2023 09:15-1Почему-то, когда предлагаешь в инженерных вопросах честно взять и что-нибудь померить, то многие люди предпочитают вместо этого переводить вопрос в гуманитарную плоскость.
Лично для меня объективное инженерное знание самоценно.
iig
04.10.2023 09:15O(N) вполне получается. Задача имеет решение, без тригонометрии и квадратуры круга в двойном цикле, но требует нудной писанины. А архитектурно-зависимое тактоложество, оно ИМХО еще более нудное.
vadimr Автор
04.10.2023 09:15Для программы-минимум достаточно превзойти референсный код размером 100 строк.
Sdima1357
04.10.2023 09:15+2Оптимальное решение займёт явно больше одного дня, так как придётся писать оптимизированную библиотеку FFT. То что вы ищете - это максимум на свёртке этой матрицы с изображением круга нужного радиуса, то есть n^2 log n ( n - сторона матрицы) операций и узкое место- собственно свертка, а если использовать готовую библиотеку fft , то узкое место будет не у Вас.
Если искать максимум суммы в прямоугольниках с заданными сторонами, то порядок сложности будет n^2 с помошью интегральный суммы исходной матрицы( со стороной n)
vadimr Автор
04.10.2023 09:15Я понимаю ход Ваших рассуждений, но комментировать его по существу пока не буду. Скажу только, что это не единственный возможный подход к решению задачи. Ход Ваших мыслей, видимо, происходит оттого, что Вы мыслите категорией поиска определённого изображения на кадре. Но здесь мы решаем несколько другую задачу.
Для простоты давайте ограничимся разумными усилиями. Напоминаю, что референсный код, с которым для начала хочется сравнить, имеет длину 100 строк.
Sdima1357
04.10.2023 09:15+1Я понимаю ход Ваших рассуждений
А я не очень понимаю, как можно сделать быстрее чем n^2 log n.
vadimr Автор
04.10.2023 09:15+1Я не буду подсказывать конкретное решение, но отмечу два уязвимых момента в Вашем рассуждении:
1) Асимптотическая оценка сложности может не быть лучшей на конкретных небольших величинах.
2) Значения искомой функции в соседних точках не являются независимыми и значительно коррелированы между собой, в том числе и вычислительно связаны.
Sdima1357
04.10.2023 09:15+1Вы не сказали ничего о радиусе - 3 пикселя или 300...то есть формулировка неполная и некорректная
vadimr Автор
04.10.2023 09:15+1В условиях задачи написано, что радиус не менее 4 (просто для удобства). И, очевидно, радиус должен быть строго меньше половины короткой стороны обрезанного кадра, иначе круг не влезет в кадр целиком.
iig
04.10.2023 09:15del
vadimr Автор
04.10.2023 09:15+1А чего стёрли? Сама по себе мысль у Вас была перспективная, хотя я не уверен, что именно в таком виде она приведёт к заметному улучшению.
Sdima1357
04.10.2023 09:15+1Для больших радиусов такой способ, со сдвигом , будет медленнее свертки.
Есть быстрый и неточный способ, с помощью свертки с приближением гауссиана
vadimr Автор
04.10.2023 09:15-2А что вы, кстати, предлагаете сворачивать? Мы совершенно не знаем, как выглядит изображение в круге.
Sdima1357
04.10.2023 09:15Circularly symmetric convolution and lens blur:
vadimr Автор
04.10.2023 09:15+1Я хочу специально подчеркнуть, что гауссово распределение яркости вокруг максимума никто не обещает. И центральную симметрию тоже.
Может, там слово из трёх букв написано в пейнтбраше.
Sdima1357
04.10.2023 09:15+2Свертка любого изображения с изображением белого( 1.0 ) круга на черном (0.0) фоне дает в каждой точке точно сумму всех значений в радиусе круга. Это база которую надо знать.
M- исходная матрица, С-матрица c изображение круга
матрица сумм:
ММ = IFFT2(FFT2D(M)*FFT2D(C))
ps: в одну строчку кода :)
vadimr Автор
04.10.2023 09:15Идея красивая, но самая быстрая ли?
Нам ведь по существу не нужны значения в каждой точке.
Sdima1357
04.10.2023 09:15я думаю , что уровень оптимизации и распараллеливания современных библиотек FFT настолько хорош (в ваших размерностях 2000x2000 будет около 100-200 FPS на слабеньком CPU и раз в 10-20 быстрее на GPU) что Вам вряд ли удастся написать что нибудь быстрее. Обходы матрицы не по порядку очень сложны с точки зрения оптимизации кеша.
Sdima1357
04.10.2023 09:15Проверьте на CPU в матлабе например или попросите кого-нибудь . Примерную скорость я написал выше те ~10ms на CPU и ~1ms на GPU. Достоинство- в простоте кода и универсальности.
vadimr Автор
04.10.2023 09:15Меня этот подход очень заинтересовал, я посчитал в Питоне с помощью NumPy. По времени получилось не 10ms, конечно, а около 0.7 секунды на моём железе. Возможно, Вы в своей оценке не учли время расчёта инициализационных коэффициентов. Это немного похуже по времени, чем референсная программа, но входит в квалификационное время. Наверное, по сравнению с Питоном можно слегка разогнать, хотя основное торможение, конечно, внутри fft. Но основная проблема в том, что метод неточен. Получается погрешность почти процент в суммах. И потом даже не пересчитать руками, так как координаты от этого тоже слегка смещаются. В решении появляются мнимые компоненты порядка 1e-10, что само по себе мало, но существенно утягивает вещественную часть.
Sdima1357
04.10.2023 09:15Коэффициенты от трансформации круга считаются аналитически и ошибка у Вас слишком большая, Вы забыли добавить достаточно нулей по краям (padding) . И нужно использовать для forward real to complex версию . Вообщем-то возьмите консультацию у кого нибудь, мне лень.
Добавлю. Написанные мной оценки времен, реально достижимые на современных процессорах.
vadimr Автор
04.10.2023 09:15По краям я добавляю ровно столько точек, какой у меня размер кадра, так как матрицы нужно перемножать. Бесконечной плоскости у меня, к сожалению, нет.
Если посчитать коэффициенты аналитически, то это будет решение не той задачи, которая поставлена. Я ищу не какую-то пространственную частоту в изображении, а конкретно то, что написал - сумму пикселей в конфигурационном пространстве, принадлежащих кругу. Очевидно, что они образуют некоторую ломаную фигуру, вписанную в окружность, а не сам круг. И это важно. А в аналитическом решении мы никогда не добьёися такой же дискретизации в частотном пространстве, как в конфигурационном.
Я ж писал, что центральной симметрии и гауссовского распределения никто не обещает.
Вся надежда была на то, что погрешность приближения круга на кадре кругом в спектре окажется не очень большой. Но не получается.
Sdima1357
04.10.2023 09:15Ошибка именно из-за недостаточного паддига. Учите теорию. Ффт даёт циркулярную свертку.
vadimr Автор
04.10.2023 09:15-1Очень странно, что Вы мне предлагаете учить теорию, предлагая неподходящее решение. Я ни на минуту не сомневаюсь, что на бесконечной плоскости и при нулевом размере пикселя всё в точности сойдётся (правда, при этом придётся провести бесконечный объём вычислений).
Или если бы у нас было очень много гауссово распределённых фотонов и мы могли бы свободно интерполировать между пикселями (условно говоря, имели право блюрить изображение), то мы бы тоже получили ответ с достаточно большой точностью, задав круг аналитически.
Но вопрос-то был не в этом.
Sdima1357
04.10.2023 09:15Вы не правы, не надо бесконечности. Достаточно отсутствия перекрытия те 2000 + 2 радиса. Почитайте теорию и не гоните чушь
vadimr Автор
04.10.2023 09:15К сожалению, это не так. Даже для очень маленьких кружков и большой матрицы мы не получаем точных значений.
Это происходит именно из-за того, что круг не идеален.
Sdima1357
04.10.2023 09:15Теорию читайте. Про свертку. Я пользуюсь её свойствами больше 20 лет в разных программах и у меня все работает... удачи в отладке :)
А я работаю и консультирую за деньги...
vadimr Автор
04.10.2023 09:15у меня все работает
Думаю, что вы решаете другие задачи.
Если говорить о теории, на которую вы так напираете, то не приходило ли вам в голову, что прямоугольные углы пиксельной фигуры, вписанной в окружность, имеют бесконечный частотный спектр?
vadimr Автор
04.10.2023 09:15-1Ну просто Вы ведёте себя несколько по-детски. Придумали хорошую идею, но получилось так, что она нерабочая при заданных значениях параметров. И вместо того, чтобы признать, что да, метод аппроксимации множества пикселей в круге идеальным кругом оказался в данном случае недостаточно точным (в чём никакой беды нет) – начали делать вид, что вы один в мире знаете про дискретное преобразование Фурье.
Sdima1357
04.10.2023 09:15За $20k я Вам все отлажу. Это работает и я работаю именно в этой области . Можете посмотреть профиль..
vadimr Автор
04.10.2023 09:15У Вас в профиле стоит обработка изображений, что имеет по своему предмету достаточно отдалённое отношение к метрологической задаче, о которой идёт речь.
Politura
04.10.2023 09:15Вроде в условиях задачи там нет изображения круга, из условий круг это лишь область на данных, яркость пикселей которых надо сложить. А внутри этого круга может быть только точка, или любое другое изображение.
noRoman
04.10.2023 09:15+6Сдается мне что хотят, с помощью сообщества, получить готовую программку)
ftp27
04.10.2023 09:15+8Да. Плюс по заданию похоже на то, что это может использоваться в системах наведения :)
vadimr Автор
04.10.2023 09:15-2Чтобы не создавать такого впечатления (как ни странно звучит сам по себе этот аргумент) добавил в конец статьи ссылку на референсную программу в запароленном архиве. Ключ сообщу после проведения конкурса.
sergio_nsk
04.10.2023 09:15-2Что это меняет, а если не сообщишь?
vadimr Автор
04.10.2023 09:15-2А что меняет, если сообщу? Чисто расстановку точек над I, кто занимается пустой болтовнёй, а кто шарит в теме.
Politura
04.10.2023 09:15+2Если бы вы написали свою статью по-другому: привели задачу, привели свое решение на Фортране, разобрали бы его, объяснив как оно работает и предложили бы попробовать сделать лучше на плюсах, то во-первых, ресурс в целом получил бы пользу от еще одной хорошей статьи, во-вторых вы получили бы пользу от того, что народ тогда начал бы активно разбирать и ваш алгоритм, и предлагать другие варианты, а не обвинять вас в том, что вы хотите нажиться на чужом труде.
vadimr Автор
04.10.2023 09:15народ тогда начал бы активно разбирать и ваш алгоритм
Этого бы не было. Проходили :)
Видя готовый более-менее вменяемый алгоритм, мало кто испытывает интенцию его улучшать.
JordanCpp
04.10.2023 09:15Почти весь код который нас окружает это С/ С++.
Как вы считаете реально ли написать быструю программу?
Для проведения такого конкурса следует, запостить алгоритм и реализацию хоть на Фортране. Для проведения тестов.
Начинать типа вот вам описание, че слабо? Фэйспалм.
JordanCpp
04.10.2023 09:15Вангую, что на С/С++ такая программа будет быстрее. Быстрее чего, в задаче не указано. Даже код не нужон:)
iig
04.10.2023 09:15Быстрее чего, в задаче не указано.
Чем на фортране ;)
Автор мог бы взять Fortran to C++ Converter, и, не раскрывая свой код, проверить скорость этого же алгоритма на другом языке.
vadimr Автор
04.10.2023 09:15Ну естественно, что так окажется намного хуже (как и при гипотетическом обратном конвертировании), потому что ряд конструкций Фортрана не имеют прямых аналогов в Си/libc и будут эмулироваться. Любой конвертер, банально, развернёт параллельный цикл в последовательный код. Тут шансы есть только если писать с нуля.
JordanCpp
04.10.2023 09:15+1Я автора понимаю, самому лень, что то писать. Но в контексте авторства задачи понять не могу. Логичнее если бы он запостил варианты на фортране и С++. Когда есть код, его можно оптимизировать. Раз нет тестов, можно вообще всё утверждать. Питон быстрее:)
vadimr Автор
04.10.2023 09:15Я недостаточно хорошо знаю C++, чтобы написать на нём эффективный код в данном случае. Если бы у меня были продуктивные мысли нв этот счёт, логично предположить, что я бы не спрашивал.
Не исключаю, что может и на питоне будет быстрее, если оправдает себя подход @Sdima1357с FFT. В питоне по сути денег за использование IMSL в NumPy платить не надо. По сути там под капотом коммерческий код на Фортране и вручную переведённый с Фортрана на Си.
Breathe_the_pressure
Можно написать, я проверил.
shasoftX
А можно не писать. Я тоже проверил.
Breathe_the_pressure
кому теперь верить?
shasoftX
мне-можно верить
simenoff
Можно писать, можно не писать, можно закинуть программирование куда подальше