Во-первых, не бойтесь названия «стресс-тестер». Это просто модный термин для написанного мной служебного инструмента для соревнований по программированию. Вместо того чтобы просто дать вам код, я расскажу о стратегии и плане, которые у меня были, когда я писал этот инструмент.
Введение
Мы много раз сталкивались с трудностями в соревнованиях, особенно когда чувствовали, что наша логика безошибочна, но оказывалось, что код терпит неудачу в каком-то крутом тестовом примере. При этом не всегда есть резервная копия, когда в голову приходит спасительное решение с помощью грубой силы.
Да, метод грубой силы дает верное решение. Тогда в чем проблема? Вы угадали: этот метод медленный. Строго говоря, с точки зрения соревновательного программирования, он не оптимален, и в некоторых задачах код может выйти за рамки временных ограничений некоторых небольших подзадач. Мы могли бы воспользоваться тем фактом, что наше решение методом грубой силы правильное, и протестировать оптимальное решение вместе с ним.
Мне пришла в голову идея: что, если мы возьмем тестовый пример, скормим его брут-форсу и оптимальному решению и проверим, где решение терпит неудачу. Но где взять столько тестовых случаев? Здесь в игру вступает случайность.
Стратегия
- Сгенерировать случайные тестовые наборы.
- Скормить их программам.
- Вооружиться исполняемыми файлами брут-форса и оптимального решения.
- Поместить их результаты в разные файлы и проверить разницу.
И еще одно: может потребоваться выполнить эту задачу тысячу раз.
Выбор технологий
Я мог бы реализовать эту стратегию с помощью Python и нескольких его модулей, таких как
subprocess для запуска команд терминала, difflib для проверки разницы вывода, random для генерации случайных тест-кейсов и операций ввода-вывода файлов, но подход может стать лихорадочным, потому что включает в себя много операций в терминале, то есть мы можем столкнуться с проблемами. Поэтому я выбрал идеальное сочетание bash и python.
Причина выбора
bash — легкость, с которой скрипт bash может выполнять большинство вышеперечисленных действий, а для генерации тестовых данных я буду использовать Python.
Структура каталога:
brute.cppиoptimal.cppсодержат соответствующий названиям код.testcase.pyгенерирует тестовые данные.brute_out.txtиoptimal_out.txt, (которые будет созданы во время выполнения), будут содержать соответствующие выходные названиям данные.difference_file.txt, где мы можем посмотреть на разницу.
1. Генерация тестовых файлов
Я выбрал в качестве примера вопрос на codechef. Прежде всего нужно понимать, что один тестовый файл — это точные значения входного формата. Уточню: один тестовый файл (не то же самое, что тест-кейс) из этого вопроса содержит все, что описывается на изображении:
Ниже тестовый файл. Пожалуйста, посмотрите на входной формат выше.
Мы будем генерировать
n таких тестовых файлов. Код для создания тестового файла зависит от входного формата. Посмотрите на приведенный ниже код для создания подходящего входному формату тестового файла.
Я написал несколько классов, чтобы проще генерировать тест-кейсы и облегчить некоторые общие операции, скажем, генерацию массива из n целых чисел и другие действия. Вот код:
import sys
import random
sys.stdout = open("testcase.txt", "w")
class RandomGenerator():
def __init__(self):
pass
def integer(self, lower_bound, upper_bound):
ret = random.randint(lower_bound, upper_bound)
return ret
def array(self, array_size, lower_bound, upper_bound):
l = [0]*array_size
for index, element in enumerate(l):
l[index] = self.integer(lower_bound, upper_bound)
return l
class ListOperation():
def __init__(self):
pass
def print_space(self, l):
for element in l:
print(element, end=" ")
print()
def print_csv(self, l):
for element in l:
print(element, end=", ")
print()
class Print():
def __init__(self):
pass
def inline_print(self, n):
"""
print n elements in a line and then print an endline
"""
for i in range(n):
print()
if __name__ == "__main__":
rand = RandomGenerator()
lops = ListOperation()
t = 10
for __ in range(t):
print(rand.integer(1, 1000))testcase.py
2. Bash
- Генерирует исполняемые файлы брут-форса и оптимального решения.
- Принимает аргумент командной строки — количество исполняемых файлов — для запуска
- Для каждого сгенерированного тестового файла сопоставляет выходные данные и проверяет разницу
В коде всё объясняется:
# 1. creating the executables
g++ brute.cpp -o brute_executable
g++ optimal.cpp -o optimal_executable
# 2. getting the number of times to run the script from command line args
n=$1
# --------------------- 3 -------------------------- #
# running loop for n times (N files)
for (( i=1; i<=n; ++i ))
do
# generate and map testcases to testcase.txt
python testcase.py
# generate and map respective outputs
./brute_executable < testcase.txt > brute_out.txt
./optimal_executable < testcase.txt > optimal_out.txt
# Bash Magic : If the difference command produces any output
if [[ $(diff brute_out.txt optimal_out.txt) ]]
then
# map the output of diff command to difference_file
echo "$(diff -Z brute_out.txt optimal_out.txt)" > difference_file.txt
echo "Difference reported in file difference_file.txt"
echo "-----------------------------------------------"
echo "You Can find the testcase where your optimal solution failed in testcase.txt"
echo "and their respective outputs in brute_out.txt and optimal_out.txt"
# Once the difference is found and we've reported it
# then no need to generate extra testcases we can break right here
break
else
echo "AC on super-test $i"
fi
done
# When the program passes all the test files
echo "--------------Testing done-----------"mapper.sh
Описание некоторых важных частей скрипта
Важно: цикл прерывается, когда обнаруживается разница и мы смотрим на тест-кейс, на котором программа терпит неудачу. Программа записывает тест-кейс в файл
testcase.txt.Команда
diff:diff <file_1> <file_2> возвращает разницу между двумя файлами. Флаг -Z используется, чтобы diff пропускала начальные пробелы и новые строки. Получение результата выполнения команды внутри скрипта bash:
$(command) дает нам вывод command. Воспользуемся этим фактом и проверим, есть ли какая-то разница, потому что если команда diff ничего не возвращает, то это означает, что файлы одинаковы.Перенаправление ввода-вывода:
command > "filename"перенаправит вывод команды на «filename».command < "filename"передает содержимое файла вcommandв качестве входных данных.
Применение стресс-тестера:
- Скопируйте ваш код в
brute.cppиoptimal.cpp. - Измените
testcase.pyтак, чтобы он подходил выходному формату. - Переключитесь на терминал и перейдите в каталог проекта.
- Выполните
mapper.sh, передав аргумент командной строки (количества тестовых файлов) и наслаждайтесь магией. - Посмотрите в файл
difference_file.txt, чтобы увидеть разницу выводов.
Мне потребовалось некоторое время, чтобы привыкнуть к использованию этого инструмента. Но когда я почувствовал помощь в работе со сложными «Answer is correct», прилив адреналина был потрясающим. И это еще не все: можно использовать стресс-тестер для тестирования ожидаемого решения, которое проходит придуманные нами тест-кейсы.
Посмотрите: я запустил инструмент на 20 тестовых файлах, но разница замечена в самом первом из них.
И после проверки файла с разницей я обнаружил несколько крайних случаев, когда моя программа каждый раз выводила 1. После изменения
optimal.cpp и обработки крайнего случая я запустил код снова. На этот раз я убедился, что учитываю каждый тестовый случай, и запустил инструмент на 100 тестовых файлах. Вы можете посмотреть процесс выполнения в видео ниже. Поверьте, мне без этого инструмента я бы не получил «Answer is Correct». Инструмент стоит того, чтобы поделиться им. GithubОсваивать новую сферу или повышать квалификацию куда проще с промокодом HABR, который даст вам дополнительные 10% к скидке указанной на баннере.
- Онлайн-буткемп по Data Science
- Обучение профессии Data Analyst с нуля
- Онлайн-буткемп по Data Analytics
- Обучение профессии Data Science с нуля
- Курс «Python для веб-разработки»
- Профессия Этичный хакер
Eще курсы
- Курс по аналитике данных
- Курс по DevOps
- Профессия Веб-разработчик
- Профессия iOS-разработчик с нуля
- Профессия Android-разработчик с нуля
- Профессия Java-разработчик с нуля
- Курс по JavaScript
- Курс по Machine Learning
- Курс «Математика и Machine Learning для Data Science»
- Продвинутый курс «Machine Learning Pro + Deep Learning»
