Представьте, что вам нужно перебрать много случайных перестановок строки и выполнить какую-то быструю проверку для каждой. Проверка настолько быстрая, что узким местом в вашем решении становится шаффл. *Для простоты, в сниппетах я ускорил проверку до 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$.↵
↵
<spoiler summary="Как получить такую строку на Unix?"><pre>tr -dc '[:alnum:]' < /dev/urandom | head -c 200000 > stroka.txt</pre>↵
</spoiler>↵
↵
Скомпилируем код с **g++ 14.2.1** со стандартным для большинства тестирующих систем флагом `-O2`. На моём ноутбуке процессорное время работы составило $26.78$ секунд.↵
↵
#### Реализация с `shuffle`↵
↵
Возможно вы читали известную [статью про рандом](https://codeforces.me/blog/entry/61587) или обратили внимание на warning компилятора. Действительно, уже давно никто не использует [random_shuffle](https://en.cppreference.com/w/cpp/algorithm/random_shuffle.html), ведь есть современная замена. Как она покажет себя в бенчмарке?↵
↵
~~~~~↵
#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](https://man7.org/linux/man-pages/man3/strtok.3.html), не имеющие аналогов в современном C++. Если же заглянуть за `_GNU_SOURCE`, можно обнаружить куда более удивительные вещи.↵
↵
Внезапно на сцену выходит [glibc](https://www.gnu.org/software/libc). С нашей задачей нам поможет [strfry](https://www.gnu.org/software/libc/manual/2.22/html_node/strfry.html). Функция принимает 0-терминированную строку и шаффлит её. При этом глобальное состояние ГПСЧ не меняется, а от запуска к запуску перестановка будет меняться. Под капотом функция использует [getrandom](https://man7.org/linux/man-pages/man2/getrandom.2.html) в стандартном линейном алгоритме со свопами. Кстати, согласно [стандарту C++11](https://en.cppreference.com/w/cpp/string/basic_string.html), наша строка 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$ секунд. Ура, мы нашли победителя!
↵
#### Реализация с `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$.↵
↵
<spoiler summary="Как получить такую строку на Unix?"><pre>tr -dc '[:alnum:]' < /dev/urandom | head -c 200000 > stroka.txt</pre>↵
</spoiler>↵
↵
Скомпилируем код с **g++ 14.2.1** со стандартным для большинства тестирующих систем флагом `-O2`. На моём ноутбуке процессорное время работы составило $26.78$ секунд.↵
↵
#### Реализация с `shuffle`↵
↵
Возможно вы читали известную [статью про рандом](https://codeforces.me/blog/entry/61587) или обратили внимание на warning компилятора. Действительно, уже давно никто не использует [random_shuffle](https://en.cppreference.com/w/cpp/algorithm/random_shuffle.html), ведь есть современная замена. Как она покажет себя в бенчмарке?↵
↵
~~~~~↵
#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](https://man7.org/linux/man-pages/man3/strtok.3.html), не имеющие аналогов в современном C++. Если же заглянуть за `_GNU_SOURCE`, можно обнаружить куда более удивительные вещи.↵
↵
Внезапно на сцену выходит [glibc](https://www.gnu.org/software/libc). С нашей задачей нам поможет [strfry](https://www.gnu.org/software/libc/manual/2.22/html_node/strfry.html). Функция принимает 0-терминированную строку и шаффлит её. При этом глобальное состояние ГПСЧ не меняется, а от запуска к запуску перестановка будет меняться. Под капотом функция использует [getrandom](https://man7.org/linux/man-pages/man2/getrandom.2.html) в стандартном линейном алгоритме со свопами. Кстати, согласно [стандарту C++11](https://en.cppreference.com/w/cpp/string/basic_string.html), наша строка 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$ секунд. Ура, мы нашли победителя!
