MikeMirzayanov's blog

By MikeMirzayanov, 12 years ago, In Russian

Update: Выпущен новый релиз 0.8.5. Скачать новую версию вы можете с сайта проекта. Новая версия внедрена во все сервисы Codeforces и Polygon. Изначально этот пост содержал информацию о девелопмент-версии, но сейчас он используется для описания версии 0.8.5.

Библиотека testlib — самая популярная и развитая библиотека для написания чекеров, генераторов, валидаторов и теперь интеракторов для задач. Первая версия testlib.h была написана мной в 2005-ом, и представляла по большей степени порт testlib.pas на С++. С тех пор многое было улучшено и расширено. В настоящий момент она активно используется в задачах Codeforces, разных этапах Всероссийской олимпиады школьников, многих петрозаводских контестах, всех саратовских соревнованиях и т.д.

Вот основные изменения/улучшения.

Комментарий программы: stdout -> stderr

Теперь системные сообщения testlib-программ (чекеров, валидаторов, интеракторов) направляются в стандартный поток ошибок (stderr) вместо стандартного потока вывода (stdout). Это сделано для идентичности поведения при написании интеракторов, стандартный вывод которых уходит в программу участника и не может использован для вывода системных сообщений. Это может повлиять на некоторые тестирующие системы, будьте внимательны!

Интеракторы

Появилась поддержка интеракторов. Напомню, что интерактор это программа взаимодействующая с решением участника при тестировании интерактивных задач. Интерактор читает одновременно содержимое теста (первый параметр командной строки, в интеракторе — это inf), вывод программы участника (передается на стандартный ввод интерактора, в интеракторе — это ouf), выводит данные в решение участника (в интеракторе выводите в cout или используйте другой вывод, не забывайте flushes), выводит спец. файл для последующей обработки его чекером (вывод в поток tout, который похож на cout).

Пример интерактора:

#include "testlib.h"
#include <iostream>

using namespace std;

int main(int argc, char* argv[])
{
    setName("Interactor A+B");
    registerInteraction(argc, argv);
    
    // reads number of queries from test file
    int n = inf.readInt();
    for (int i = 0; i < n; i++)
    {
        // reads query from test file
        int a = inf.readInt();
        int b = inf.readInt();

        // writes query to the solution, endl makes flush
        cout << a << " " << b << endl;

        // writes output file to be verified by checker later
        tout << ouf.readInt() << endl;
    }

    // exit with message
    quitf(_ok, "%d queries processed", n);
}

readStrictReal/readStrictDouble

У потоков inf/ouf/ans появились функции readStrictReal/readStrictDouble (это одно и то же). Они очень строго читают вещественные числа, применимы в большей степени в валидаторах. Принимают аргументы:

  • минимальное значение числа,
  • максимальное значение числа,
  • минимальное число цифр после десятичной точки (не обязательный),
  • максимальное число цифр после десятичной точки (не обязательный),
  • имя читаемой переменной (для вывода при ошибке).

Еще раз повторюсь — это нововведение нужно для валидаторов.

Защита от потерянных quit/quitf и readEof

Если вы пишите чекер, то легко забыть в какой-нибудь ветке выполнения сделать правильный quit или quitf. Раньше в этом случае чекер скорее всего завершался с exitcode 0 и для участника это означало вердикт "правильный ответ на тест". Теперь testlib автоматически при выходе проверит что был в самом деле вызван quit/quitf (это работает для чекеров) и аварийно завершит работу, если вызова не было. Аналогично, если валидатор не сделал чтение конца файла (readEof), то произойдет аварийное завершение.

quitif

В чекерах (и не только) очень популярна конструкция вида:

if (answer != output)
    quitf(_wa, "Expected %d, found %d", answer, output);

Теперь ее можно записать чуть короче, используя функцию "выйти если" (quitif): quitif(answer != output, _wa, "Expected %d, found %d", answer, output);

Улучшение производительности

Вместо слов короткий пример. Запускаем простой чекер сравнения миллиона целых чисел (вывод и ответ ~ 7.5 мегабайт, для C++ использовался g++ 4.6.1, а для pascal — Delphi 7):

  • предыдущий релиз testlib.h — 2.8 секунды,
  • паскалевский testlib от ИТМО — 3 секунды,
  • паскалевский testlib от СПбГУ — 4 секунды,
  • новая версия testlib.h — 0.35 секунды

Таким образом, можно утверждать, что мнение о медленной работе предыдущих версий — просто миф, а новый testlib быстрее предыдущего примерно в 8 раз!

Аналогичные измерения, если использовать текстовые чекеры (сравнения строк или токенов):

  • предыдущий релиз testlib.h — 1.2 секунды,
  • паскалевский testlib от ИТМО — 3.5 секунды,
  • паскалевский testlib от СПбГУ — 2 секунды,
  • новая версия testlib.h — 0.25 секунды.

Миф подтверждается, а время работы сократилось вдвое. Видимо, на больших файлах скорость работы возросла примерно в 3-6 раз.

Функции-помощники

Добавлены несколько простых полезных функций (некоторые уже были):

  • lowerCase(std::string), upperCase(std::string) — перевести строку в нижний или верхний регистр,
  • trim(std::string) — удаляет слева и справа строки пробелы, табы и символы перевода строк,
  • vtos(T) — шаблонная функция, превращает экземпляр T в строку (медленная, использует stringstream),
  • format(шаблон, параметры), например format("n=%d", 5) — возвращает строку по шаблону и параметрам,
  • englishEnding(int) — правильное окончание для числительного, например englishEnding(2)="nd",
  • compress(std::string) — заменяет длинную строку более короткой, оставляя ее префикс и суффикс, а между ними многоточие, очень полезна при выводе в комментарий какого-либо вывода участника,
  • startTest(int) — используется в мультигенераторах, фактически делает freopen(имя-тест, "r", "stdin"), то последующий вывод перенаправляется в файл с именем равным номеру теста.

Мелочи

Макросы I64, U64

Теперь определены макросы:

#ifdef ON_WINDOWS
#define I64 "%I64d"
#define U64 "%I64u"
#else
#define I64 "%lld"
#define U64 "%llu"
#endif

Пример использования: printf("n=" I64 ", m=%d", n, m). Используйте их для ввода-вывода 64-битных знаковых/беззнаковых чисел через scanf/printf. Хотя такое делать почти не надо, так как чтение происходит через inf/ouf/ans, а при выводе лучше сделать vtos(n).

Случайный элемент коллекции (отрезка итераторов).

Теперь можно в генераторе написать так: cout << rnd.any(v) << endl, где v — это вектор. Так же поддерживается вариант с парой итераторов random_t::any(begin, end), т.е. произвольный элемент массива можно получить так rnd.any(a, a + n).

Issue

Исправлен issue с пространством имен около iter_swap, из за чего были проблемы с компиляцией на некоторых GCC g++.

Новый члены-функции у InStream: readWordTo/readTokenTo/readStringTo/readLineTo

Такие функции были добавлены для ускорения чтения в чекерах (валидаторах и т.д.), где приходится очень много читать. Например, вот так может выглядеть основной код чекера, который сравнивает ответы и вывод по словам (токенам):

    string j, p;
    while (!ans.seekEof() && !ouf.seekEof()) 
    {
        n++;
        ans.readWordTo(j);
        ouf.readWordTo(p);
        if (j != p)
            quitf(_wa, "%d%s words differ - expected: '%s', found: '%s'", n, englishEnding(n).c_str(), compress(j).c_str(), compress(p).c_str());
    }

InStream::quitf

Добавлен InStream::quitf, теперь. Помните, что для потоков ans/inf любая причина выхода, отличная от _fail приводит к _fail. Например, следующий участок кода корректен

int readAnswer(InStream& in)
{
    int n = in.readInt();
    if (n % 2 != 0)
        in.quitf(_wa, "n should be even, but %d found", n);
    return n;
}

int main(int argc, char * argv[])
{
    registerTestlibCmd(argc, argv);
    
    int ja = readAnswer(ans);
    int pa = readAnswer(ouf);
    
    quitif(ja > pa,
        _fail, "expected %d, found %d", ja, pa);
    quitif(ja < pa,
        _wa, "expected %d, found %d", ja, pa);
    
    quitf(_ok, "answer is %d", ja);
}

Если выведено нечетное число в файл с ответом, то будет _fail, а если в вывод участника — то _wa.

Стандартные чекеры/валидаторы

В стандартные поставляемые чекеры были добавлены два чекера: caseicmp.cpp и casencmp.cpp, которые работают в случае стандартной для ACM-ICPC Finals разметки multitestcase. Первый из них поможет, если надо проверять одно целое число на testcase, а второй — если последовательность чисел.

Тестирование

Новый код усиленно тестировался, в частности в полуавтоматическом режиме на большом количестве тестов. Сравнивалось, что stdout/stderr и exitcode чекера не изменился после его компиляции с новым testlib.h.

  • Vote: I like it
  • +111
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can you try to translate it to English? I can only read the sample code...