Стресс-тестер для соревнований по программированию

Во-первых, не бойтесь названия «стресс-тестер». Это просто модный термин для написанного мной служебного инструмента для соревнований по программированию. Вместо того чтобы просто дать вам код, я расскажу о стратегии и плане, которые у меня были, когда я писал этот инструмент.

Введение

Мы много раз сталкивались с трудностями в соревнованиях, особенно когда чувствовали, что наша логика безошибочна, но оказывалось, что код терпит неудачу в каком-то крутом тестовом примере. При этом не всегда есть резервная копия, когда в голову приходит спасительное решение решение с помощью грубой силы.

Да, метод грубой силы дает верное решение. Тогда в чем проблема? Вы угадали: этот метод медленный. Строго говоря, с точки зрения соревновательного программирования, он не оптимален, и в некоторых задачах код может выйти за рамки временных ограничений некоторых небольших подзадач. Мы могли бы воспользоваться тем фактом, что наше решение методом грубой силы правильное, и протестировать оптимальное решение вместе с ним.

Мне пришла в голову идея: что, если мы возьмем тестовый пример, скормим его брут-форсу и оптимальному решению и проверим, где решение терпит неудачу. Но где взять столько тестовых случаев? Здесь в игру вступает случайность.

Стратегия

Сгенерировать случайные тестовые наборы.
Скормить их программам.
Вооружиться исполняемыми файлами брут-форса и оптимального решения.
Поместить их результаты в разные файлы и проверить разницу.

И еще одно: может потребоваться выполнить эту задачу тысячу раз.

Выбор технологий

Я мог бы реализовать эту стратегию с помощью 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% к скидке указанной на баннере.

Eще курсы

Стресс-тестер для соревнований по программированию

Введение

Стратегия

Выбор технологий

1. Генерация тестовых файлов

2. Bash

Рекомендуемые статьи

Комментарии

Добавить комментарий Отменить ответ