Представьте, что вам нужно перебрать много случайных перестановок строки и выполнить какую-то быструю проверку для каждой. Проверка настолько быстрая, что узким местом в вашем решении становится шаффл. Для простоты, в сниппетах я ускорил проверку до no-op и добавил печать финальной строки.
Реализация с 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';
}
Бенчмаркать будем на случайной строке [a-zA-Z0-9] длины $$$2 \cdot 10^5$$$.
Скомпилируем код с g++ 14.2.1 со стандартным для большинства тестирующих систем флагом -O2. На моём ноутбуке процессорное время работы составило $$$26.78$$$ секунд.
Реализация с shuffle
Возможно вы читали статью или обратили внимание на warning компилятора. Действительно, уже давно никто не использует random_shuffle, ведь есть модная замена shuffle.
#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';
}
Процессорное время работы такой реализации в тех же условиях составило $$$7.73$$$ секунд. Круто! В рамках этой заметки мы не будем погружаться в детали реализации и анализировать причину такого ускорения.
Реализация с strfry
Обратимся к наследию C. В стандартной библиотеке иногда встречаются полезные функции, например strtok, не имеющие аналогов в современном C++. Если же заглянуть за _GNU_SOURCE, можно обнаружить куда более удивительные вещи.
Внезапно на сцену выходит glibc. С нашей задачей нам поможет strfry. Функция принимает 0-терминированную строку и шаффлит её. При этом глобальное состояние ГПСЧ не меняется, а от запуска к запуску перестановка будет меняться. Под капотом функция использует getrandom в стандартном линейном алгоритме со свопами.
#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$$$ секунд. Ура, мы нашли победителя!
