news.shamcode.ru | Стресс-тестер для соревнований по программированию

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

суббота, 31 октября 2020 г. в 00:27:25

https://habr.com/ru/company/skillfactory/blog/525262/

Блог компании SkillFactory
Спортивное программирование
Тестирование IT-систем
Python
Программирование

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

Введение

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

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

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

Стратегия

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

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

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

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