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$$$.
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 or noticed the compiler warning. Indeed, no one uses random_shuffle 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 runtime 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
Обратимся к наследию C. В стандартной библиотеке иногда встречаются полезные функции, например strtok, не имеющие аналогов в современном C++. Если же заглянуть за _GNU_SOURCE, можно обнаружить куда более удивительные вещи.
Внезапно на сцену выходит glibc. С нашей задачей нам поможет strfry. Функция принимает 0-терминированную строку и шаффлит её. При этом глобальное состояние ГПСЧ не меняется, а от запуска к запуску перестановка будет меняться. Под капотом функция использует getrandom в стандартном линейном алгоритме со свопами. Кстати, согласно стандарту C++11, наша строка 0-терминированная.
#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';
}
Процессорное время работы в тех же условиях составило $$$5.54$$$ секунд. Ура, мы нашли победителя!
