Imagine you need to iterate through many random permutations of a string and perform some quick check for each one. The check is so fast that the bottleneck in your solution becomes the shuffling. *For simplicity, in the snippets, I've sped up the check to a no-op and added printing the final string.*↵
↵
#### Implementation with `random_shuffle`↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define ITER 10000↵
↵
int main() {↵
string s; cin >> s;↵
for (int i = 0; i < ITER; ++i) {↵
random_shuffle(s.begin(), s.end());↵
// do_something(s);↵
}↵
cout << s << '\n';↵
}↵
~~~~~↵
↵
We'll benchmark this on a random `[a-zA-Z0-9]` string of length $2 \cdot 10^5$.↵
↵
<spoiler summary="How to generate such a string on Unix?"><pre>tr -dc '[:alnum:]' < /dev/urandom | head -c 200000 > stroka.txt</pre>↵
</spoiler>↵
↵
Compile the code with **g++ 14.2.1** using the standard `-O2` flag common in most judging systems. On my laptop, the user CPU time was $26.78$ seconds.↵
↵
#### Implementation with `shuffle`↵
↵
Perhaps you've read the well-known [article about random](https://mirror.codeforces.com/blog/entry/61587) or noticed the compiler warning. Indeed, no one uses [random_shuffle](https://en.cppreference.com/w/cpp/algorithm/random_shuffle.html) anymore, as there's a modern replacement. How will it perform in the benchmark?↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define ITER 10000↵
↵
int main() {↵
string s; cin >> s;↵
mt19937 rng(42); // reproducibility↵
for (int i = 0; i < ITER; ++i) {↵
shuffle(s.begin(), s.end(), rng);↵
// do_something(s);↵
}↵
cout << s << '\n';↵
}↵
~~~~~↵
↵
The user CPU time for this implementation under the same conditions was $7.73$ seconds. Cool! *In this note, we won't dive into implementation details or analyze the reason for this speedup.*↵
↵
#### Implementation with `strfry`↵
↵
Let's turn to C's legacy. The standard library contains some useful functions, like [strtok](https://man7.org/linux/man-pages/man3/strtok.3.html), which have no modern C++ equivalents. And if you look under `_GNU_SOURCE`, you can find even more surprising things.↵
↵
Suddenly, [glibc](https://www.gnu.org/software/libc) enters the stage. For our task, [strfry](https://www.gnu.org/software/libc/manual/2.22/html_node/strfry.html) can help. This function takes a null-terminated string and shuffles it. The global state of the PRNG remains unchanged, and the permutation will vary between runs. Under the hood, the function uses [getrandom](https://man7.org/linux/man-pages/man2/getrandom.2.html) in the standard linear swap algorithm. By the way, according to the [C++11 standard](https://en.cppreference.com/w/cpp/string/basic_string.html), our string is null-terminated.↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define ITER 10000↵
↵
int main() {↵
string s; cin >> s;↵
for (int i = 0; i < ITER; ++i) {↵
strfry(s.data());↵
// do_something(s);↵
}↵
cout << s << '\n';↵
}↵
~~~~~↵
↵
The user CPU time under the same conditions was $5.54$ seconds. Congratulations, we've found the winner!
↵
#### Implementation with `random_shuffle`↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define ITER 10000↵
↵
int main() {↵
string s; cin >> s;↵
for (int i = 0; i < ITER; ++i) {↵
random_shuffle(s.begin(), s.end());↵
// do_something(s);↵
}↵
cout << s << '\n';↵
}↵
~~~~~↵
↵
We'll benchmark this on a random `[a-zA-Z0-9]` string of length $2 \cdot 10^5$.↵
↵
<spoiler summary="How to generate such a string on Unix?"><pre>tr -dc '[:alnum:]' < /dev/urandom | head -c 200000 > stroka.txt</pre>↵
</spoiler>↵
↵
Compile the code with **g++ 14.2.1** using the standard `-O2` flag common in most judging systems. On my laptop, the user CPU time was $26.78$ seconds.↵
↵
#### Implementation with `shuffle`↵
↵
Perhaps you've read the well-known [article about random](https://mirror.codeforces.com/blog/entry/61587) or noticed the compiler warning. Indeed, no one uses [random_shuffle](https://en.cppreference.com/w/cpp/algorithm/random_shuffle.html) anymore, as there's a modern replacement. How will it perform in the benchmark?↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define ITER 10000↵
↵
int main() {↵
string s; cin >> s;↵
mt19937 rng(42); // reproducibility↵
for (int i = 0; i < ITER; ++i) {↵
shuffle(s.begin(), s.end(), rng);↵
// do_something(s);↵
}↵
cout << s << '\n';↵
}↵
~~~~~↵
↵
The user CPU time for this implementation under the same conditions was $7.73$ seconds. Cool! *In this note, we won't dive into implementation details or analyze the reason for this speedup.*↵
↵
#### Implementation with `strfry`↵
↵
Let's turn to C's legacy. The standard library contains some useful functions, like [strtok](https://man7.org/linux/man-pages/man3/strtok.3.html), which have no modern C++ equivalents. And if you look under `_GNU_SOURCE`, you can find even more surprising things.↵
↵
Suddenly, [glibc](https://www.gnu.org/software/libc) enters the stage. For our task, [strfry](https://www.gnu.org/software/libc/manual/2.22/html_node/strfry.html) can help. This function takes a null-terminated string and shuffles it. The global state of the PRNG remains unchanged, and the permutation will vary between runs. Under the hood, the function uses [getrandom](https://man7.org/linux/man-pages/man2/getrandom.2.html) in the standard linear swap algorithm. By the way, according to the [C++11 standard](https://en.cppreference.com/w/cpp/string/basic_string.html), our string is null-terminated.↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define ITER 10000↵
↵
int main() {↵
string s; cin >> s;↵
for (int i = 0; i < ITER; ++i) {↵
strfry(s.data());↵
// do_something(s);↵
}↵
cout << s << '\n';↵
}↵
~~~~~↵
↵
The user CPU time under the same conditions was $5.54$ seconds. Congratulations, we've found the winner!
