Во-первых, не бойтесь названия «стресс-тестер». Это просто модный термин для написанного мной служебного инструмента для соревнований по программированию. Вместо того чтобы просто дать вам код, я расскажу о стратегии и плане, которые у меня были, когда я писал этот инструмент.
Введение
Мы много раз сталкивались с трудностями в соревнованиях, особенно когда чувствовали, что наша логика безошибочна, но оказывалось, что код терпит неудачу в каком-то крутом тестовом примере. При этом не всегда есть резервная копия, когда в голову приходит спасительное решение с помощью грубой силы.
Да, метод грубой силы дает верное решение. Тогда в чем проблема? Вы угадали: этот метод медленный. Строго говоря, с точки зрения соревновательного программирования, он не оптимален, и в некоторых задачах код может выйти за рамки временных ограничений некоторых небольших подзадач. Мы могли бы воспользоваться тем фактом, что наше решение методом грубой силы правильное, и протестировать оптимальное решение вместе с ним.
Мне пришла в голову идея: что, если мы возьмем тестовый пример, скормим его брут-форсу и оптимальному решению и проверим, где решение терпит неудачу. Но где взять столько тестовых случаев? Здесь в игру вступает случайность.
Стратегия
- Сгенерировать случайные тестовые наборы.
- Скормить их программам.
- Вооружиться исполняемыми файлами брут-форса и оптимального решения.
- Поместить их результаты в разные файлы и проверить разницу.
И еще одно: может потребоваться выполнить эту задачу тысячу раз.
Выбор технологий
Я мог бы реализовать эту стратегию с помощью 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»
maxzhurkin
Почему нельзя было, например, просто