Введение 3
Постановка задачи 4
1. Предметная область и подход к тестированию 5
1.1. Мотивация 5
1.2. Обзор конкурентов 6
1.3. Глобальная математическая модель 6
1.4. Математическая модель 7
1.5. Проблемы модели и существующих решений 9
1.6. Особенности среды тестирования 9
2. Базовые алгоритмы поиска квантилей 11
2.1. Максимум выборки как квантиль 11
2.2. Линейная регрессия 11
2.3. Квантили из теории экстремальных значений 12
2.4. Таблица сравнения базовых алгоритмов 14
3. Модификации gpd 15
3.1. Среднее на полной выборке 15
3.2. Среднее на половинках выборок 15
3.3. Взвешенное среднее 16
3.4. Медиана полных выборок и среднего на половинках 16
3.5. Выбор по среднему на половинках 17
3.6. Таблица сравнения комбинированных методов 18
4. Выравнивание ошибки 19
4.1. Выравнивание ошибки 19
4.2. Таблица сравнения полученных алгоритмов 21
4.3. Выбор оптимального алгоритма 21
4.4. Советы по применению 23
Заключение 25
Список литературы 26
Тестирование программного обеспечения является неотъемлемой частью процесса разработки ПО. Оно позволяет не только убедиться в корректности работы определённых модулей или даже целых программ, но и отслеживать время за которое они работают. Первым этапом, с которым сталкиваются разработчики, является создание прототипа продукта и исправление ошибок в поведении программы. Второй же этап это оптимизация скорости работы созданной программы. В зависимости от задачи ПО второй этап может как отсутствовать, так и занимать большую часть процесса разработки. В случае, когда данный этап достаточно долгий или вообще не заканчивается, хорошей практикой считается создать автоматическое тестирование производительности. Данное тестирование позволяет отслеживать прогресс оптимизации, как по отдельным модулям, так и по сценариям работы ПО.
В сфере производительности ПО и находится тема данного дипломного проекта. Для автоматического анализа результатов тестов создано немало библиотек [1.2], которые имеют инструменты для отслеживания времени работы. Функционал такого отслеживания практически у всех этих библиотек останавливается на возвращении времени работы на каждом тесте, если те работают и не превысили временное ограничение заданное тестировщиком. К несчастью фиксированные ограничения на время работы очень редко связанны с реальным временем выполнения теста, а иногда вообще остаётся по умолчанию. Из-за этого плохо работающая программа может пройти тестирование и надежда заключается в том, что последующий анализ времени работы выявит проблему.
В ходе выполнения этого проекта будут исследованы подходы и эвристики, позволяющие автоматически определять является ли время, которое работает тест недопустимым. В результате исследований будет создан метод позволяющий автоматически оценивать временные ограничения для тестов.
По итогам работы был разработан алгоритм превосходящий базовые алгоритмы, но всё ещё не являющийся идеальным. При размерах выборки в 100 элементов и целевом математическом ожидании вероятности падения теста на фиксированном распределении равном 0.999, достичь удалось 0.9960.997. При этом значения временных ограничений, полученные при помощи алгоритма, имеют низкие стандартные отклонения, что добавляет программе предсказуемости.
