![](https://habrastorage.org/webt/qw/fs/-h/qwfs-hdfzszlxcr-64tbt_idcbg.jpeg)
Во-первых, не бойтесь названия «стресс-тестер». Это просто модный термин для написанного мной служебного инструмента для соревнований по программированию. Вместо того чтобы просто дать вам код, я расскажу о стратегии и плане, которые у меня были, когда я писал этот инструмент.
Введение
Мы много раз сталкивались с трудностями в соревнованиях, особенно когда чувствовали, что наша логика безошибочна, но оказывалось, что код терпит неудачу в каком-то крутом тестовом примере. При этом не всегда есть резервная копия, когда в голову приходит спасительное решение с помощью грубой силы.
Да, метод грубой силы дает верное решение. Тогда в чем проблема? Вы угадали: этот метод медленный. Строго говоря, с точки зрения соревновательного программирования, он не оптимален, и в некоторых задачах код может выйти за рамки временных ограничений некоторых небольших подзадач. Мы могли бы воспользоваться тем фактом, что наше решение методом грубой силы правильное, и протестировать оптимальное решение вместе с ним.
Мне пришла в голову идея: что, если мы возьмем тестовый пример, скормим его брут-форсу и оптимальному решению и проверим, где решение терпит неудачу. Но где взять столько тестовых случаев? Здесь в игру вступает случайность.
![](https://habrastorage.org/webt/3n/ul/nv/3nulnvwkafb3dfhvn1laaj3drio.png)
Стратегия
- Сгенерировать случайные тестовые наборы.
- Скормить их программам.
- Вооружиться исполняемыми файлами брут-форса и оптимального решения.
- Поместить их результаты в разные файлы и проверить разницу.
И еще одно: может потребоваться выполнить эту задачу тысячу раз.
Выбор технологий
Я мог бы реализовать эту стратегию с помощью Python и нескольких его модулей, таких как
subprocess
для запуска команд терминала, difflib
для проверки разницы вывода, random
для генерации случайных тест-кейсов и операций ввода-вывода файлов, но подход может стать лихорадочным, потому что включает в себя много операций в терминале, то есть мы можем столкнуться с проблемами. Поэтому я выбрал идеальное сочетание bash и python.![](https://habrastorage.org/webt/94/pm/1k/94pm1kh77q3katdwklsiqsjbz_m.png)
Причина выбора
bash
— легкость, с которой скрипт bash
может выполнять большинство вышеперечисленных действий, а для генерации тестовых данных я буду использовать Python.![](https://habrastorage.org/webt/fl/7o/0z/fl7o0z-xnn3mrbl6avrmchbvlvw.png)
Структура каталога:
brute.cpp
иoptimal.cpp
содержат соответствующий названиям код.testcase.py
генерирует тестовые данные.brute_out.txt
иoptimal_out.txt
, (которые будет созданы во время выполнения), будут содержать соответствующие выходные названиям данные.difference_file.txt
, где мы можем посмотреть на разницу.
![](https://habrastorage.org/webt/54/d9/nd/54d9nd2vexq7toc9rpqr5llsrys.png)
1. Генерация тестовых файлов
Я выбрал в качестве примера вопрос на codechef. Прежде всего нужно понимать, что один тестовый файл — это точные значения входного формата. Уточню: один тестовый файл (не то же самое, что тест-кейс) из этого вопроса содержит все, что описывается на изображении:
![](https://habrastorage.org/webt/tf/bz/50/tfbz50pkgnvclb-kz7khkscctg4.png)
Ниже тестовый файл. Пожалуйста, посмотрите на входной формат выше.
![](https://habrastorage.org/webt/-u/ia/wq/-uiawqv5vw6k4i8rytxljn3m960.png)
Мы будем генерировать
n
таких тестовых файлов. Код для создания тестового файла зависит от входного формата. Посмотрите на приведенный ниже код для создания подходящего входному формату тестового файла.![](https://habrastorage.org/webt/f_/x3/gt/f_x3gtjubymorbekyje0yj6dj0g.png)
Я написал несколько классов, чтобы проще генерировать тест-кейсы и облегчить некоторые общие операции, скажем, генерацию массива из 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:
![](https://habrastorage.org/webt/jv/ev/pd/jvevpdtrkboewlaw_mufymdri04.png)
$(command)
дает нам вывод command
. Воспользуемся этим фактом и проверим, есть ли какая-то разница, потому что если команда diff
ничего не возвращает, то это означает, что файлы одинаковы.Перенаправление ввода-вывода:
![](https://habrastorage.org/webt/k-/bl/sa/k-blsamg2utgz7p5-xmj78gxp2e.png)
command > "filename"
перенаправит вывод команды на «filename».command < "filename"
передает содержимое файла вcommand
в качестве входных данных.
Применение стресс-тестера:
- Скопируйте ваш код в
brute.cpp
иoptimal.cpp
. - Измените
testcase.py
так, чтобы он подходил выходному формату. - Переключитесь на терминал и перейдите в каталог проекта.
- Выполните
mapper.sh
, передав аргумент командной строки (количества тестовых файлов) и наслаждайтесь магией. - Посмотрите в файл
difference_file.txt
, чтобы увидеть разницу выводов.
Мне потребовалось некоторое время, чтобы привыкнуть к использованию этого инструмента. Но когда я почувствовал помощь в работе со сложными «Answer is correct», прилив адреналина был потрясающим. И это еще не все: можно использовать стресс-тестер для тестирования ожидаемого решения, которое проходит придуманные нами тест-кейсы.
![](https://habrastorage.org/webt/11/he/-c/11he-c85odep8bnfnmgaocxgbgk.png)
Посмотрите: я запустил инструмент на 20 тестовых файлах, но разница замечена в самом первом из них.
![](https://habrastorage.org/webt/kj/gn/ij/kjgnijzsaiohguqc4csljiw0_4a.png)
И после проверки файла с разницей я обнаружил несколько крайних случаев, когда моя программа каждый раз выводила 1. После изменения
optimal.cpp
и обработки крайнего случая я запустил код снова. На этот раз я убедился, что учитываю каждый тестовый случай, и запустил инструмент на 100 тестовых файлах. Вы можете посмотреть процесс выполнения в видео ниже. Поверьте, мне без этого инструмента я бы не получил «Answer is Correct». Инструмент стоит того, чтобы поделиться им. GithubОсваивать новую сферу или повышать квалификацию куда проще с промокодом HABR, который даст вам дополнительные 10% к скидке указанной на баннере.
![image](https://habrastorage.org/webt/zs/g_/v8/zsg_v8ou6lldwpmosr_t5g5naqu.jpeg)
- Онлайн-буткемп по 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
Почему нельзя было, например, просто