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

Введение


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

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

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

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

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

Первая кровь


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



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

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

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

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


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

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


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

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

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

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

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


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

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

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



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


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

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

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

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


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

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

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

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

Резюме


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

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

Similar posts

AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 13

    +3
    Вы только опубликовали, а я сразу вспомнил кусок своей программы, за который мне стыдно)
    Github
    Histogram shift. This correction makes the background really blank. After the correction
        # numpy clipping is performed to fit the 0-100 range
        hist_shift_0 = parsed_json["hist_shift_0"]
        hist_shift_1 = parsed_json["hist_shift_1"]
        hist_shift_2 = parsed_json["hist_shift_2"]
    
        image_separated = color.separate_stains(image_original, matrix_dh)
        stain_ch0 = image_separated[..., 0]
        stain_ch1 = image_separated[..., 1]
        stain_ch2 = image_separated[..., 2]
    
        stain_ch0 = (stain_ch0 + 1) * 200
        stain_ch0 -= hist_shift_0
        stain_ch0 = np.clip(stain_ch0, 0, 100)
    


    Просто я не знаю, как это описать в коде. Функция color.separate_stains возвращает картинку с диапазоном то [-1;-0.5]. Понятия не имею почему, не моя она. А мне надо получить от 0 до 100. Плюс еще абсолютный сдвиг гистограммы, который подбирается эмпирически, но его я хотя бы смог вынести во внешний файл, описывающий свойства конкретной пары красителей.
    {
      "channel_0":"Hematoxylin",
      "channel_1":"DAB-chromogen",
      "channel_2":"Supplementary channel",
      "vector": [[0.66504073, 0.61772484, 0.41968665],
                [0.4100872, 0.5751321, 0.70785],
                [0.6241389, 0.53632, 0.56816506]],
      "thresh_0":30,
      "thresh_1":40,
      "hist_shift_0":5,
      "hist_shift_1":16,
      "hist_shift_2":0
    }
    
      +1
      Функция color.separate_stains возвращает картинку с диапазоном то [-1;-0.5]. Понятия не имею почему, не моя она. А мне надо получить от 0 до 100.
      На мой взгляд, в таких случаях достаточно прокомментировать — что делает данная строка кода, причём лучше было бы написать на мой взгляд:
          stain_ch0 = (stain_ch0 + 1) * 2 * 100 # convert range of values from [-1;-0.5] to [0; 100]
      

      Тем самым мы явно показываем что делаем, к тому же умножение на 2 и на 100 будет лучше раскрывать ход мыслей — сначала увеличиваем вдвое, чтобы получить максимум до единицы, а потом уже переводим в проценты, умножая на сто.
        0
        Отлично, спасибо.
      –10
      Если ты что то не понимаешь то это называется магия. Если ты разбираешся в сути проблемы то это уже не магия.
      Вот отличный пример
      k[0..63] :=
      0x428A2F98, 0x71374491, 0xB5C0FBCF, 0xE9B5DBA5, 0x3956C25B, 0x59F111F1, 0x923F82A4, 0xAB1C5ED5,
      0xD807AA98, 0x12835B01, 0x243185BE, 0x550C7DC3, 0x72BE5D74, 0x80DEB1FE, 0x9BDC06A7, 0xC19BF174,
      0xE49B69C1, 0xEFBE4786, 0x0FC19DC6, 0x240CA1CC, 0x2DE92C6F, 0x4A7484AA, 0x5CB0A9DC, 0x76F988DA,
      0x983E5152, 0xA831C66D, 0xB00327C8, 0xBF597FC7, 0xC6E00BF3, 0xD5A79147, 0x06CA6351, 0x14292967,
      0x27B70A85, 0x2E1B2138, 0x4D2C6DFC, 0x53380D13, 0x650A7354, 0x766A0ABB, 0x81C2C92E, 0x92722C85,
      0xA2BFE8A1, 0xA81A664B, 0xC24B8B70, 0xC76C51A3, 0xD192E819, 0xD6990624, 0xF40E3585, 0x106AA070,
      0x19A4C116, 0x1E376C08, 0x2748774C, 0x34B0BCB5, 0x391C0CB3, 0x4ED8AA4A, 0x5B9CCA4F, 0x682E6FF3,
      0x748F82EE, 0x78A5636F, 0x84C87814, 0x8CC70208, 0x90BEFFFA, 0xA4506CEB, 0xBEF9A3F7, 0xC67178F2
      Это первые 32 бита дробных частей кубических корней первых 64 простых чисел [от 2 до 311]. Да можно написать как они вычисляются, но эти константы для разбирающихся людей. А для остальных это магические цифры.
        +2
        Это не та 'магия', про которую речь в статье.
        Ряду алгоритмов необходим набор каких-то констант, теоретически — произвольных*. Когда алгоритм стандартизируют в стандарт попадает и конкретный набор констант.
        (*) но с какими то наборами алгоритм может работать лучше, с какими-то хуже (а с какими-то иметь неочевидную уязвимость) и настоящая криптографическая магия скрыта в том, почему в стандарт попал именно этот набор констант. Про s блоки des целую теорию заговора строили. Подозреваю, что в sha 'первые 32 бита дроб...' взяты как раз за тем, чтобы обеспечить хоть минимальную прозрачность 'почему выбраны именно эти'.
          +9
          Пример хороший, но при этом вы, или кто-то другой, копировавший изначально этот код, забыл скопировать рядом стоящий комментарий, который и делает это не массивом магических констант, а кодом, с вполне нормальным описанием. Во всех примерах в топе гугла этот код имеет комментарии:
          -- Initialize table of round constants
          -- (first 32 bits of the fractional parts of the cube roots of the first
          -- 64 primes 2..311):
          local k = {
             0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
             0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
             0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
             0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
             0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc,
             0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
             0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
             0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
             0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13,
             0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
             0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3,
             0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
             0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5,
             0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
             0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
             0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2,
          }
          

          Таблица констант
          (первые 32 бита дробных частей кубических корней первых 64 простых чисел [от 2 до 311]):
          k[0..63] :=
             0x428A2F98, 0x71374491, 0xB5C0FBCF, 0xE9B5DBA5, 0x3956C25B, 0x59F111F1, 0x923F82A4, 0xAB1C5ED5,
             0xD807AA98, 0x12835B01, 0x243185BE, 0x550C7DC3, 0x72BE5D74, 0x80DEB1FE, 0x9BDC06A7, 0xC19BF174,
             0xE49B69C1, 0xEFBE4786, 0x0FC19DC6, 0x240CA1CC, 0x2DE92C6F, 0x4A7484AA, 0x5CB0A9DC, 0x76F988DA,
             0x983E5152, 0xA831C66D, 0xB00327C8, 0xBF597FC7, 0xC6E00BF3, 0xD5A79147, 0x06CA6351, 0x14292967,
             0x27B70A85, 0x2E1B2138, 0x4D2C6DFC, 0x53380D13, 0x650A7354, 0x766A0ABB, 0x81C2C92E, 0x92722C85,
             0xA2BFE8A1, 0xA81A664B, 0xC24B8B70, 0xC76C51A3, 0xD192E819, 0xD6990624, 0xF40E3585, 0x106AA070,
             0x19A4C116, 0x1E376C08, 0x2748774C, 0x34B0BCB5, 0x391C0CB3, 0x4ED8AA4A, 0x5B9CCA4F, 0x682E6FF3,
             0x748F82EE, 0x78A5636F, 0x84C87814, 0x8CC70208, 0x90BEFFFA, 0xA4506CEB, 0xBEF9A3F7, 0xC67178F2
          


          И так далее.
          0
          Вспомнилось быстрое вычисление обратного квадратного корня. Вот где настоящая магия!
            +1
            Никакой магии бы не было, если бы автор кода удосужился добавить описание применяемого метода или вообще хоть какое-то обоснование выполняемых действий. Но в реальном коде было это:
            /*
            ** float q_rsqrt( float number )
            */
            float Q_rsqrt( float number )
            {
            	long i;
            	float x2, y;
            	const float threehalfs = 1.5F;
            
            	x2 = number * 0.5F;
            	y  = number;
            	i  = * ( long * ) &y;			    // evil floating point bit level hacking
            	i  = 0x5f3759df - ( i >> 1 );               // what the fuck?
            	y  = * ( float * ) &i;
            	y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
            //	y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed
            
            #ifndef Q3_VM
            #ifdef __linux__
            	assert( !isnan(y) ); // bk010122 - FPE?
            #endif
            #endif
            	return y;
            }
            

            Естественно ничего, кроме возгласа WTF?! такой код и в таком виде вызвать не может и не для математика сравним с магией.
              0
              В том и дело, что это не математика, а очень хитрое использование особенностей представления дробных чисел. Кто и каким образом вывел волшебную константу — доподлинно не известно.
                +1
                И, тем не менее, это чистой воды математика. Так, вместо «evil floating point bit level hacking» там вполне могло бы стоять пояснение, что алгоритм базируется на logₙ(1/√x) = −½ logₙ(x) и данное преобразование в int возвращает значение, достаточно близкое к логарифму от float-числа. Я согласен с тем, что это великолепное применение знаний математики и битовых операций, но уж точно не магия. Просто магией мы называем то, что мы не понимаем.
                  0

                  Способ вывода "волшебной" константы описан в Википедии довольно понятным языком.

              +1

              Я как-то не понимаю зачем такая статья, проблема то небольшая. Магические числа, это первое про что пишут в книгах. Пиши код, чтобы он читался как текст. Лично я предпочитаю длинные имена классов/методов/параметров, однако не любитель повсеместных комментариев.

                +2
                Мне в большей степени хотелось привлечь внимание к функциональным зависимостям между параметрами. То есть, если по сути
                const int a = b*c; // а - ...
                
                то так и надо написать, а не
                const int a = ...; // a = b*c, а - ...
                

              Only users with full accounts can post comments. Log in, please.