- PVSM.RU - https://www.pvsm.ru -
Многие команды используют так называемый fuzzing [1] (генерация случайных наборов данных) для тестирования и некоторые [2] — вполне успешно. Я же попробую рассказать о попытке применения fuzzing-техник для создания/оптимизации кода приложения. Сфера применения таких приложений, разумеется, ограничена — только задачи, где точное и полное решение отсутствует в принципе, а для любых решений есть некоторый критерий качества. Мы используем технику для оптимизации приложения для распознаванию рукописного ввода, но этим применение метода не заканчивается, а задуматься о нем можно, когда у себя в исходном коде вы видите нечто похожее:
|
Нет, я не предлагаю вовсе избавляться от констант/параметров методов, ибо даже в случае очень гибких и адаптивных систем ограничивающие параметры нужны, чтобы обеспечивать некоторую сходимость внутренних методов, и в целом, стабильность приложения. То есть, написать хороший распознаватель текста вообще без констант нельзя, а, значит нужно эти константы каким-то образом выбирать. И варианта у нас по сути два:
Первый способ хорош, но при условии достаточного количества времени, прекрасного представления о логике работы каждой части программы и наличии этого «здравого смысла»; человеку очень легко угадать нужный порядок константы, и там где должно быть 0.001, он не напишет 1000 (как правило). Но какая, в сущности, разница между 0.1 и 0.15? Особенно, если не знать, зачем эта константа нужна, а человек, который ввел ее, уже несколько лет как не работает с вами. И ручное определение никогда не даст «замечательных» результатов ни в общем случае, ни на какой-либо тестовой коллекции.
И мы должны понимать, что изменение некоторой части кода может существенным образом повлиять на все последующие методы, и их параметры в том числе.
Для обеспечения автоматической генерации нам потребуется организовать окружение разработки, позволяющее подгадывать параметры методов «на лету». В идеале, этим должен заниматься build-server в свободное от основной работы время.
Конечно, весьма желательно вынести все константы в отдельные файлы, тогда с ними будет удобнее работать. Но мы живем не в идеальном мире, и если это кто-то не сделал за вас, то работа вам достанется нелегкая. Особенно тем — что константы нужно как-то называть, а по контексту это сделать не всегда возможно. И некоторые константы являются действительно точными значениями, которые модификации не подлежат.
int grayscale = round(0.30 * R + 0.59 * G + 0.11 * B);
А другие же, напротив, только этого и ждут:
if (width/height > 0.25 && width/height < 1.25 && width > 10) ...
Если менять и те и другие, то с вероятностью, близкой к 1 мы получим нерабочую программу, соответственно необходимо их как-то разделять. Для этого можно использовать специальные маркеры, например:
#define FUZZ
int grayscale = round(0.30 * R + 0.59 * G + 0.11 * B);
...
FUZZ if (width/height > 0.25 && width/height < 1.25 && width > 10)
В общем вся работа сводится к проставлению маркеров, для тех объектов, значение которых следует менять. Чтобы найти константы в проекте помогут регулярные выражения, а вот чтобы понять какие «ждут» маркера —
Далее, пишется простейшая программка (ConstFuzzer), для случайной модификации этих констант, которая находит помеченные маркером строчки и модифицирует значения в них на определенную случайную величину. Привет, Entropy [4]! Возможно, если разрешат, чуть позже ее выложу.
Запускаем: ConstFuzzer src/*.cpp fuzzed_output_dir/ 0.1 и получаем «перепорченные исходники».
Пока мы не знаем, есть ли от новых исходников какой-то прок, или нет, и чтобы это выяснить — нужно их скомпилировать. Под gcc у вас, наверняка есть Makefile, а под Visual Studio, при наличии solution сделать это нетрудно:
%VS_CPP_COMPILER% %OUR_SLN% /Build Release /Out log-cpp.txt
Теперь, если приложение собралось, результат его работы следует проверить. Для этого, собранное приложение прогоняется по тестовому набору данных (в нашем случае картинки) и его выход сопоставляется с эталонным (распознанные тексты). Считается процент правильно распознанных и среднее время выполнения.
Кстати, не всегда полученное приложение будет работать правильно, оно может и зависнуть (зациклиться где-то из-за «неправильных» констант). Для того чтобы весь процесс Fuzzing'а на этом не рухнул — приложение вызывается через TimeLimit (утилита, ограничивающая время исполнения). Не прошло порог времени — считаем, что получило «0» в качестве результата.
Если грамотно расставлять маркеры, то такое случается редко, и константы при которых это происходит интересны для исправления потенциальных багов приложения.
Вышеописанный процесс по сути мало чем отличается от любой системы машинного обучения. И здесь можно смело применять большинство известных схем.
1. примитивный подход: max (случайные_изменения(начальные_значения) -> результат)
2. итеративный подход: while(iteration) {случайные_изменения(текущие_лучшие_значения) -> результат}
3. деление отрезка пополам: новые_значения = (max(случайные_изменения(начальные_значения) -> результат)) + начальные_значения) / 2
4. симплекс-метод [5].
Используемый метод определяет только скорость сходимости (то есть получения локальных лучших результатов), качество же результирующей программы — качеством тестовой коллекции.
Однако, чтобы получить глобальный максимум (то есть оптимально работающую программу) необходимо научиться делить входные данные на кластера, и использовать лучший набор констант (теперь уже переменных) для этого кластера. Если это интересно, то чуть позже расскажу, как это можно технически реализовать, без особых усложнений процесса разработки.
Конечно, обучить «константы» в программе, так чтобы она давала наилучший результат на одной тестовой коллекции — дело не хитрое, но это вовсе не будет гарантировать оптимального поведения в целом. Для того чтобы ослабить влияние этого фактора мы берем более объемлющую коллекцию для вывода итоговых результатов работы. То есть «тренируются» константы на одной коллекции, а итоговый результат считается на другой.
Но тестовую коллекцию все равно нужно постоянно расширять, и ручной контроль результатов — более чем желателен (ну да, все-таки пока еще программа сама себя не напишет).
Однако, наличие пусть и субоптимальных результатов на определенной коллекции и представление их в удобной форме — некоторый шаг вперед относительно вечных «TODO».
Итоги:
+ меньше времени тратится на изменение констант, неявно зависящих от других частей кода;
+ возможно получение более близких к оптимальным результатов, практически «просто так», даже если вы не находитесь за рабочим местом;
+ возможность протестировать изменения (вы добавили новый код, но если с ним пока нет улучшений, то можно постоянно тестировать версии, как с ним, так и без него — FUZZ if (true), и может когда-нибудь он «поможет»);
— некоторое время придется потратить на автоматизацию процесса.
Автор: sic
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/algoritmy/8136
Ссылки в тексте:
[1] fuzzing: http://en.wikipedia.org/wiki/Fuzz_testing
[2] некоторые: http://habrahabr.ru/post/142958/
[3] мозг: http://www.braintools.ru
[4] Entropy: http://habrahabr.ru/post/144300/
[5] симплекс-метод: http://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D0%BC%D0%BF%D0%BB%D0%B5%D0%BA%D1%81-%D0%BC%D0%B5%D1%82%D0%BE%D0%B4
Нажмите здесь для печати.