Магические константы в алгоритмах

в 11:40, , рубрики: algorithms, Code Style, Алгоритмы, математика, Совершенный код

Введение

В настоящее время широко известны такие принципы написания программного кода (coding standards), которые позволяют облегчить его поддержку и развитие. Эти принципы используются многими софтверными компаниями, а средства разработки и статического анализа кода предлагают для этого разнообразную автоматизацию. В то же время инженерные задачи в программировании явно требуют расширения понятия «хороший код». Мы попробуем выйти на обсуждение «хорошего» инженерного кода через, казалось бы, весьма частный пример — через практику использования в алгоритмах константных параметров.

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

Давайте подумаем, режет ли нам глаз такой код:

if (abs(leftVoltage - rightVoltage - 150.7 * balanceCurrent) > 0.002)
  doSomethingImportant();

Лично мне режет очень сильно. Во-первых, совершенно непонятно, что такое 150.7?
Вполне возможно, что 150.7 — это сопротивление точного резистора, которое варьируется от одного экземпляра устройства к другому, и на самом деле должно быть считано из калибровочного файла. Что же такое 0.002? Похоже, что это некоторый экспериментальный порог, который может быть уточнен впоследствии, хотя об этом нет никакого специального комментария.

Первая кровь

Представим себе junior-программиста Алешу, которому предложили задачу по автоматизации контроля качества заклепок для космических кораблей компании Inhabited Galactic. По конвейеру поступают эти заклепки и их фотографирует цифровая камера. Алеше необходимо написать код, который анализирует фотографии этих заклепок и принимает решение о соответствии или несоответствии формы заклепки ее нормативу.

Магические константы в алгоритмах - 1

Предположим, что к удовольствию своих начальников Алеша быстро реализовал некоторый алгоритм оценки заклепок. Этот алгоритм отлично разделял изображения плохих и хороших заклепок из тестового набора, задача была решена и Алешу переключили на другой проект.

Затем произошло следующее. Заклепок пошло несколько больше, скорость конвейера возросла и инженер Боря немного укоротил выдержку камеры.
При этом поступающие с камеры изображения стали несколько темнее, хотя заклепки все еще были хорошо видны. В то же время Алешин алгоритм начал иногда ошибочно браковать качественные заклепки. Что же произошло?

Пусть $inline$I$inline$ это входное монохромное изображение размера $inline$W(I) times H(I)$inline$ с координатами $inline$x$inline$ и $inline$y$inline$. Алеша заметил, что пискели заклепки $inline$Z$inline$ во всех тренировочных изображениях можно было найти пороговой фильтрацией:

$$display$$ (x,y) in Z Longleftrightarrow I_{min} < I(x,y) < I_{max}.$$display$$

При этом качественную заклепку $inline$Z_{good}$inline$ можно было найти по площади:

$$display$$ A_{min} < Area(Z_{good}) < A_{max}.$$display$$

Итого, Алеша ввел 4 эмпирических константы $inline$I_{min}$inline$, $inline$I_{max}$inline$, $inline$A_{min}$inline$ и $inline$A_{max}$inline$, по крайней мере одна из которых ($inline$I_{min}$inline$) потеряла актуальность после перенастройки камеры.

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

Какое решение было бы более разумным? Параметры полосовых фильтров для яркости и площади можно было перевести в относительные величины к средней яркости и площади изображения. Например, $inline$A_{min}$inline$ можно было бы заменить на $inline$A^{'}_{min}cdot W(I)cdot H(I)$inline$, где $inline$A^{'}_{min}$inline$ — тоже эмпирическое, но уже более инвариантное значение.

Давайте попробуем предположить, что произошло дальше на заводе космических кораблей.
Так как качество отбраковки заклепок было недостаточным, то главный технолог Виталий, далекий от тонкостей программирования, решил срочно поставить на оценочный стенд более дорогую камеру с высокой чувствительностью и вдвое большим разрешением. Закономерный результат такой командной работы — 100%ая отбраковка, так как все заклепки стали вдвое больше по числу пикселей и ни одна из них не прошла полосовой фильтр. Возможно, что спасло бы грамотное управление проектом, не сейчас мы не об этом.

Нормализация входных данных

Многих проблем с подбором констант можно избежать приводя входные данные к единообразному виду. Изображения — к одной форме гистограммы, 3D модели — к одному разрешению, etc. Зачастую против нормализации выдвигают такой аргумент, что она приводит к потере части исходной информации. Это действительно так, но упрощение дальнейшей работы с параметрами алгоритмов зачастую перевешивают этот минус.

Сама постановка задачи о максимальной нормализации входных данных позволяет разработчику подумать о том, что будет, если изображения придут с поворотом на 90 грудусов? А если размеры придут в дюймах? А если кто-то передаст на вход 3D-модель высокого разрешения, которая передает тонкую фактуру материала?

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

Магические константы в алгоритмах - 2

Калибровочные константы

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

Калибровочные параметры как правило поступают из внешних источников. Страшный грех — захардкодить эти параметры. Если такой код сразу не отсеять на code review, то он сможет долго портить поведение программного продукта в целом, оставаясь при этом вне подозрений. Система просто будет работать не совсем точно, но едва ли где-то выскочит сообщение об ошибке.

Для полноты картины, однако, необходимо отметить, что в некоторых задачах возможна автокалибровка, когда внутренние зависимости наблюдаемых величин позволяют вычислить также и калибровочные параметры. Смотрите, например, последние главы Multiple View Geometry или работы по Uncalibrated Structure from Motion, где калибровочные параметры камер определяются из набора перекрывающихся снимков с разными ракурсами.

Общие замечания

Давайте константам осмысленные имена и комментируйте их значения. Помните, что это очень хрупкая часть кода, которая не защищена типизацией языка или мудростью компилятора.

Группируйте параметры алгоритмов в структуры. Это обычно улучшает читаемость кода и позволяет не прозевать какой-нибудь важный параметр во время отладки.

Если вы знаете, что один какой-то параметр выражается через другие, обязательно отразите эту связь в коде. В противном случае кто-нибудь с самыми лучшими намерениями поменяет ваши неоптимальные, но консистентные параметры на неконсистентные. Например, вы ищете на изображении кружочки радиусом $inline$R$inline$ = 10 и площадью $inline$S$inline$ = 314. Это плохо, так как на самом деле у вас один параметр — радиус $inline$R$inline$ = 10, а $inline$S=pi R^2$inline$. Код с двумя параметрами может быть легко сломан программистом, забывшим школьную математику, а код с одним параметром выглядит гораздо надежнее.

Бывает так, что в алгоритм входит какая-то неэмпирическая константа. Например, нужно оценить хвост какого-нибудь распределения. Точность такой оценки определяется в большей степени математической подготовкой автора алгоритма.
Константы-оценки иногда можно улучшать, но такое улучшение обычно является изолированной задачей. Важно прокомментировать этот факт для других разработчиков.

Резюме

Эмпирические константы это естественная часть алгоритмического кода, которая, однако, требует от разработчика пристального внимания. Перечислим еще раз те правила для работы с константами, которые мы обсудили выше:

  • Константы имеют осмысленные имена
  • Значения констант определяются перед логическим блоком в котором они используются
  • Крупные блоки констант организованы в структуры/классы параметров
  • Функционально-зависимые параметры вычисляются через базисные параметры
  • Входные данные нормализуются
  • Калибровочные константы явно загружаются из конфигурационных файлов, а в противном случае возвращается сообщение об ошибке

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

Автор: Юрий

Источник

Поделиться

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