Skip to content

Generator

Generator, i.e., data generator. When the data is large and manual creation is exhausting, we need it to help us automatically generate data.

Simple Example

Generate two integers in the range \([1,n]\):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
// clang-format off

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

using namespace std;

int main(int argc, char* argv[]) {
  registerGen(argc, argv, 1);
  int n = atoi(argv[1]);
  cout << rnd.next(1, n) << " ";
  cout << rnd.next(1, n) << endl;
}

Why Use Testlib?

Some say that writing a generator does not require Testlib, and it is useless here. Actually, this is an incorrect idea. A good generator should satisfy this: Under any environment, for the same input, it gives the same output. Writing a generator inevitably involves generating random values. The rand() we usually use or C++11's mt19937/uniform_int_distribution may produce different outputs under different operating systems, when compiled with different compilers, or run at different times (for the commonly used srand(time(nullptr)), this is obvious), which introduces uncertainty into data generation.

It is important to note that once Testlib is used, you cannot use standard library random functions like srand(), rand(), etc., otherwise a compilation error will occur. Therefore, ensure that all random-related functions use Testlib instead of those provided by the standard library.

The random value generation functions in Testlib guarantee that the same call will output the same value, independent of the generator itself or the platform. Additionally, it provides great convenience for generating random values with various requirements, such as rnd.next("[a-z]{1,10}"), which generates a string of length in \([1,10]\), with each character from a to z. Very convenient, right?

What Can Testlib Do?

Before anything else, execute registerGen(argc, argv, 1) to initialize Testlib (where 1 is the generator version used, usually kept unchanged). Then we can use the rnd object to generate random values. The random seed is taken from the hash of the command-line arguments. For a generator g.cpp, g 100 (Unix-Like) and g.exe "100" (Windows) will have the same output, while g 100 0 will differ from them.

The type of the rnd object is random_t. You can create a new random value generation object, but usually you don't need to do this.

This object has many useful member functions. Here are some examples:

Call Meaning
rnd.next(4) Equally likely generates an integer in the range \([0,4)\)
rnd.next(4, 100) Equally likely generates an integer in the range \([4,100]\)
rnd.next(10.0) Equally likely generates a floating-point number in the range \([0,10.0)\)
rnd.next("one | two | three") Equally likely returns one of the three strings: one, two, three
rnd.wnext(4, t) wnext() is a function that generates a non-uniform distribution (with a shifted expectation)1. \(t\) indicates the number of times next() is called, and the maximum of the generated values is taken. For example, rnd.wnext(3, 1) is equivalent to max({rnd.next(3), rnd.next(3)}); rnd.wnext(4, 2) is equivalent to max({rnd.next(4), rnd.next(4), rnd.next(4)}). If \(t<0\), it calls next() \(-t\) times and takes the minimum; if \(t=0\), it is equivalent to next().
rnd.any(container) Equally likely returns a reference to an element within a container with random-access iterators (such as std::vector and std::string)

Appendix: Formal definition of rnd.wnext(i,t):

\[ \operatorname{wnext}(i,t)= \begin{cases} \operatorname{next}(i) & t=0 \\ \max(\operatorname{next}(i),\operatorname{wnext}(i,t-1)) & t>0 \\ \min(\operatorname{next}(i),\operatorname{wnext}(i,t+1)) & t<0 \end{cases} \]

Also, do not use std::random_shuffle(); use shuffle() from Testlib instead, which also accepts a pair of iterators. It uses rnd to shuffle the sequence, thus satisfying the requirement of a "good generator" as mentioned above.

Example: Generating a Tree

Below is the main code for generating a tree. It accepts two parameters—the number of vertices and the "spread" factor. For example, when \(n=10,t=1000\), it might generate a chain; when \(n=10,t=-1000\), it might generate a star.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#define forn(i, n) for (int i = 0; i < int(n); i++)

registerGen(argc, argv, 1);

int n = atoi(argv[1]);
int t = atoi(argv[2]);

vector<int> p(n);

/* Set parents for nodes 1..n-1 */
forn(i, n) if (i > 0) p[i] = rnd.wnext(i, t);

printf("%d\n", n);

/* Shuffle nodes 1..n-1 */
vector<int> perm(n);
forn(i, n) perm[i] = i;
shuffle(perm.begin() + 1, perm.end());

/* Add edges according to the shuffled node order */
vector<pair<int, int>> edges;
for (int i = 1; i < n; i++)
  if (rnd.next(2))
    edges.push_back(make_pair(perm[i], perm[p[i]]));
  else
    edges.push_back(make_pair(perm[p[i]], perm[i]));

/* Shuffle edges */
shuffle(edges.begin(), edges.end());

for (int i = 0; i + 1 < n; i++)
  printf("%d %d\n", edges[i].first + 1, edges[i].second + 1);

Generating Multiple Test Cases at Once

As when writing without Testlib, simply redirect the output stream before each output. However, Testlib provides a helper function startTest(test_index), which helps you redirect the output stream to the file test_index.

Some Notes

  • Strictly follow the problem's format requirements, such as spaces and newlines. Note that the file should end with a newline.
  • For large data, prefer printf over cout for better performance. (It is not recommended to disable stream synchronization when using Testlib.)
  • Do not use UB (Undefined Behavior). For example, in the example at the beginning of this article, if the output is written as cout << rnd.next(1, n) << " " << rnd.next(1, n) << endl;, the order of calls to rnd.next() is undefined.

New Feature: Parsing Command-Line Arguments

Previously, we often used code like int n = atoi(argv[3]);, but this is not ideal for several reasons:

  • It is unsafe when the third command-line argument does not exist;
  • The third command-line argument might not be a valid 32-bit integer.

Now, you can write: int n = opt<int>(3). At the same time, you can also use int64_t m = opt<int64_t>(1);, bool t = opt<bool>(2);, and string s = opt(4);, etc.

Additionally, testlib also supports named arguments. If there are many parameters, g 10 20000 a true is less readable than g -n10 -m200000 -t=a -increment.

In this case, you can now use the following code in your generator:

1
2
3
4
int n = opt<int>("n");
long long n = opt<long long>("m");
string t = opt("t");
bool increment = opt<bool>("increment");

You can freely mix reading parameters by index and by name.

The supported schemes for writing named arguments are as follows:

  • --key=value or -key=value;
  • --key value or -key value—if value does not start a new argument (does not start with a hyphen - or does not have a letter following one/two hyphens);
  • --k12345 or -k12345—if the key k is a single letter and is followed by a number;
  • -prop or --prop—enables a boolean property.

Here are some examples:

1
2
3
4
g1 -n1
g2 --len=4 --s=oops
g3 -inc -shuffle -n=5
g4 --length 5 --total 21 -ord

More Examples

You can find more examples on GitHub.

This article is mainly translated from Генераторы на testlib.h - Codeforces. The new feature is translated from Testlib: Opts—parsing command line options. The GitHub repository for testlib.h is MikeMirzayanov/testlib.

  1. In fact, when i is a floating-point number, rnd.wnext(i, t) follows a Beta distribution on \([0,i)\): when \(t>0\), it follows \(i\cdot \mathrm{Beta}(t+1,1)\); when \(t<0\), it follows \(i\cdot \mathrm{Beta}(1,t+1)\). ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用