Представьте, что вам нужно перебрать много случайных перестановок строки и выполнить какую-то быструю проверку для каждой. Проверка настолько быстрая, что узким местом в вашем решении становится шаффл. Для простоты, в сниппетах я ускорил проверку до 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$$$.

tr -dc '[:alnum:]' < /dev/urandom | head -c 200000 > stroka.txt

Скомпилируем код с g++ 14.2.1 со стандартным для большинства тестирующих систем флагом -O2. На моём ноутбуке процессорное время работы составило $$$26.78$$$ секунд.

Реализация с shuffle

Возможно вы читали известную статью про рандом или обратили внимание на warning компилятора. Действительно, уже давно никто не использует random_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 в стандартном линейном алгоритме со свопами. Кстати, согласно стандарту 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$$$ секунд. Ура, мы нашли победителя!