Блог пользователя ifsmirnov

Универсальный генератор тестов ­– вброс идей
Автор ifsmirnov, история, 9 лет назад, По-русски

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

sscanf(argv[1], "%d", &maxn);
n = rnd.next(2, maxn);
printf("%d\n", n);
for (int i = 2; i <= n; ++i) {
    printf("%d %d\n", rnd.next(1, i-1), i);
}

Если я хочу пошаффлить рёбра, геморроя чуть больше, если хочу добавить веса, надо добавлять ещё параметр командной строки... С массивами, графами, строками и т.д. не сильно проще. Не сложно, но рутина. testlib, не считая генерации случайных чисел разных типов на интервале, может только генерировать строку по паттерну. А хочется уметь писать как-то так:

int maxn, maxc;
parseCmdParams(maxn, maxc);
cout << Tree().random(1, maxn).addWeight(1, maxc).shuffleEdges();

Соответственно, два вопроса к сообществу. Знаете ли вы что-нибудь подобное, работающее и удобное? И какие у вас самих были бы требования к такой системе? Я начал делать достаточно универсальную библиотеку для создания генераторов, и какие-то разумные советы (а через некоторое время и фидбек) сильно увеличат вероятность того, что штука будет закончена и ей можно будет адекватно и удобно пользоваться.

Вот чего хочется достичь в качестве proof-of-concept:

  • возможность писать идентичный код на C++ (11) и Python, выдающий одинаковые тесты
  • гибкая генерация чего бы то ни было через chaining (как в сниппете)
  • генерация стандартных структур (простое дерево, простая матрица, простой граф) за минимум кода
  • поддержка тесткейсов и файлов с тестами

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

  • Проголосовать: нравится
  • +121
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Возможно, тебе будет интересно посмотреть в сторону QuickCheck. Правда, это больше, чем описание генераторов; фактически, это концепция "умных" стресс-тестов. Цитируя документацию к реализации QuickCheck на питоне:

Hypothesis lets you write tests which instead look like this:

  • For all data matching some specification.
  • Perform some operations on the data.
  • Assert something about the result.

It works by generating random data matching your specification and checking that your guarantee still holds in that case. If it finds an example where it doesn’t, it takes that example and cuts it down to size, simplifying it until it finds a much smaller example that still causes the problem. It then saves that example for later, so that once it has found a problem with your code it will not forget it in future.

В википедии есть ссылки на реализацию QuickCheck для большинства ЯП, но я не знаю, насколько они полные/качественные.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Интересная штука, спасибо. То, что я предлагаю, как понял, у них называется hypothesis.strategies. Надо будет покопаться и посмотреть, как оно устроено.

    Мне для использования на контестах оно показалось слишком громоздким. Ты пытался реально это использовать?

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Не пытался. Собственно, я и предлагаю не обязательно использовать уже существующее решение, а

      покопаться и посмотреть, как оно устроено.

      Например, в дополнение к генераторам были бы полезны комбинаторы генераторов.

      → Ответить
»
9 лет назад, # |
  Проголосовать: нравится +48 Проголосовать: не нравится

Я довольно много думал о подобной библиотеке и пришел к выводу, что совсем хорошо это работать не будет. Дело в том, что постоянно в зависимости от задачи нужны какие-то модификации структуры. Скажем, делаешь задачу про дерево и понимаешь, что хорошо бы добавить не просто дерево, а такую длинную палку у которой на конце разветвление на k вершин. А потом хочешь добавить полное бинарное дерево, а потом кособокое дерево, а потом еще какое-нибудь этакое. И при внимательном составлении тестов такое происходит постоянно.

Написать генераторы стандартных структур так, чтобы их было легко/удобно расширять и модифицировать случайному автору задач мне кажется очень сложно — у каждого свой стиль, свои паттерны для генерации, зачастую проще окажется написать самому с нуля, чем модифицировать существующий код.

ИМХО, полезно было бы просто иметь подборку в публичном репозитории 50 хорошо написанных и документированных генераторов на большинство случаев жизни. Чтобы все они были простые и самодостаточные, каждый из них легко можно было прочесть и что-то в него вписать/поправить. Чтобы они были классифицированы по темам и имели внятный единообразный naming.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +23 Проголосовать: не нравится

    Михаил, спасибо за разумный комментарий!

    Да, безусловно, в каждой задаче нужны свои тесты, свои виды деревьев и т.д. Но большое количество кода всё равно повторяется. Взять те же кособокие и бинарные деревья: говоря о гибкости, я имел в виду как раз возможность генерировать деревья разных стандартных типов. Бамбуки, высокие-низкие, кособокие-пушистые и всё такое. Чтобы можно было написать Tree().random(n, elongation) или Tree().bamboo(n/2).connect(v_in_bamboo, Tree().fluffy(n/2), v_in_fluffy). Конечно, есть задачи, в которых нужны специальные тесты, но, кажется, даже если 70% тестов можно будет сгенерировать более простым способом, будет удобнее.

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

    builder.addVertex(0, 0);
for (int i = 0; i < n; ++i) {
    addVertex(i, i+1);
    addVertex(i+1, i+1);
}
builder.turnCW(n, n);
for (...)
    ...
builder.print(-maxC, maxC);

    Условно говоря, подаём последовательный список вершин, если удобно — переходим к другой системе координат, потом печатаем со случайно раскиданными координатами и случайным поворотом. И тут уже не важно, какие именно тесты нужны для задачи, штука в любом случае облегчает создание.

    Иными словами, я не предлагаю хардкодить всевозможные тесты. Я предлагаю сделать некоторый конструктор или фреймворк, из которого можно либо быстро склепать простые тесты, либо выполнить рутину (поворот на случайный угол, шаффл вершин в графе и т.д., добавление антихэштеста по разным модулям) при генерации сложных.

    → Ответить
»
9 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Согласен, кажется, такая штука была бы удобной. Если фантазировать по-крупному, то, как мне кажется, к ней было бы здорово прикрутить еще визуализацию: часто бывает так, что я генерирую в цикле кучу тестов и либо сравниваю с наивным решением либо пытаюсь поймать рантайм. В таком случае возможность в том же цикле записывать картинку и мгновенно посмотреть тесткейс экономит время по сравнению с вырисовыванием его на бумажке. С помощью graphViz это должно реализовываться просто, как минимум в случае графов.

→ Ответить