C++17 STL Стандартная библиотека шаблонов - Яцек Галовиц

имеет одинаковое значение по оси Y во всех точках! График, получаемый путем соединения этих точек, выглядит как идеальная прямая горизонтальная линия. Квадратные точки, однако, показывают, что мы получим, если будем брать образец каждые 100+random(-15, +15) точек. Полученный сигнал все еще значительно отличается от оригинального, но уже не пропадает полностью, как это было в случае с выборкой с фиксированным шагом.

Функция std::sample не добавляет случайные значения к пробным точкам с фиксированным шагом, она выбирает полностью случайные точки; поэтому в рамках данного примера работает несколько по-другому.

Как это делается

В этом примере мы создадим выборку для очень большого вектора, содержащую случайные данные. Они имеют нормальное распределение. После завершения выборки полученные результаты все еще будут показывать нормальное распределение, что мы и проверим.

1. Сначала включим все заголовочные файлы, которые будем применять, а также объявим об использовании пространства имен std, чтобы сэкономить немного времени на вводе текста:

#include <iostream>

#include <vector>

#include <random>

#include <algorithm>

#include <iterator>

#include <map>

#include <iomanip>

using namespace std;

2. С кодом работать будет гораздо проще, если мы сконфигурируем конкретные характеристики нашего алгоритма с помощью константных переменных. Укажем размер большого вектора случайных чисел, а также количество точек:

int main()

{

  const size_t data_points {100000};

  const size_t sample_points {100};

3. Большой вектор, заполненный случайными числами, должен наполняться с помощью генератора случайных чисел, выдающего числа, которые будут иметь нормальное распределение. Любое нормальное распределение характеризуется математическим ожиданием и квадратическим отклонением:

  const int mean {10};

  const size_t dev {3};

4. Теперь настроим генератор случайных чисел. Сначала создадим экземпляр random_device и вызовем его один раз, чтобы получить исходное значение для конструктора генератора случайных чисел. Далее создадим объект распределения, который применяет нормальное распределение к полученным случайным числам:

  random_device rd;

  mt19937 gen {rd()};

  normal_distribution<> d {mean, dev};

5. Создадим экземпляр вектора, содержащего целые числа, и заполним его случайными числами. Это можно сделать с помощью алгоритма std::generate_n, который вызовет объект функции генератора, чтобы передать его возвращаемое значение в наш вектор благодаря итератору back_inserter. Объект функции генератора оборачивает выражение d(gen), получающее случайное число от случайного устройства и передает его в объект распределения:

  vector<int> v;

  v.reserve(data_points);

  generate_n(back_inserter(v), data_points,

    [&] { return d(gen); });

6. Теперь создадим еще один вектор, который содержит гораздо меньший диапазон точек:

  vector<int> samples;

  v.reserve(sample_points);

7. Алгоритм std::sample работает аналогично алгоритму std::copy, но при этом принимает два дополнительных параметра — количество точек, получаемых из входного диапазона данных, и объект генератора случайных чисел, к которому он будет обращаться, чтобы получить случайные позиции пробных точек:

  sample(begin(v), end(v), back_inserter(samples),

         sample_points, mt19937{random_device{}()});

8. С выборкой мы закончили. Остальная часть кода посвящена отображению данных. Входные данные имеют нормальное распределение, и если алгоритм выборки отработал хорошо, то полученный вектор тоже должен иметь такое же распределение. Чтобы увидеть, насколько распределение отклоняется от нормального, выведем на экран гистограмму значений:

  map<int, size_t> hist;

  for (int i : samples) { ++hist[i]; }

9. Наконец, пройдем в цикле по всем элементам, чтобы вывести нашу гистограмму на экран:

  for (const auto &[value, count] : hist) {

    cout << setw(2) << value << " "

         << string(count, '*') << 'n';

  }

}

10. После компиляции и запуска программы мы видим, что полученный вектор имеет характеристики нормального распределения (рис. 5.5):

Как это работает

Алгоритм std::sample — это новый алгоритм, который появился в версии С++17. Его сигнатура выглядит следующим образом:

template<class InIterator, class OutIterator,

         class Distance, class UniformRandomBitGenerator>

OutIterator sample(InIterator first, InIterator last,

                   SampleIterator out, Distance n,

                   UniformRandomBitGenerator&& g);

Входной диапазон данных обозначается итераторами first и last, в то время как out — итератор вывода. Эти итераторы выполняют ту же функцию, что и для функции std::copy; элементы копируются из одного диапазона в другой. Алгоритм std::sample является особенным с той точки зрения, что копирует только часть входного диапазона, поскольку делает выборку только n элементов. Он использует равномерное распределение внутри системы, поэтому каждая точка на графике во входном диапазоне данных может быть выбрана с одинаковой вероятностью. 

Выполняем перестановки во входных последовательностях

 При тестировании кода, который должен работать с последовательностями входных данных, где порядок аргументов не так важен, полезно проверять, получаем ли мы одинаковый результат во всех возможных перестановках для этих входных данных. Такой тест может, например, проверять, корректно ли работает ваш собственный алгоритм сортировки.

Независимо от того, зачем нужны все перестановки для какого-то диапазона значений, std::next_permutation позволит это реализовать. Можно вызвать эту функцию для изменяемого диапазона, и она изменит порядок его элементов на следующую лексикографическую перестановку.

Как это делается

В данном примере мы напишем программу, которая считывает несколько строк, содержащих слова, из стандартного потока ввода, а затем применим функцию std::next_permutation, чтобы сгенерировать и вывести на экран все перестановки для этих строк.

1. Как и обычно, сначала включим все необходимые заголовочные файлы и объявим об использовании пространства имен std:

#include <iostream>

#include <vector>

#include <string>

#include <iterator>

#include <algorithm>

using namespace std;

2. Мы начнем с вектора строк, который заполним из стандартного потока ввода. Затем отсортируем вектор:

int main()

{

  vector<string> v {istream_iterator<string>{cin}, {}};

  sort(begin(v), end(v));

3. Далее выведем содержимое вектора на консоль. Затем вызовем функцию std::next_permutation. Она систематически перемешивает содержимое вектора, чтобы сгенерировать перестановки этих элементов, которое мы снова выведем на экран. Вызов next_permutation вернет значение false, когда будет сгенерирована последняя перестановка.

  do {

    copy(begin(v), end(v),

         ostream_iterator<string>{cout, ", "});

    cout << 'n';

  } while (next_permutation(begin(v), end(v)));

}

4. Скомпилируем и запустим функцию, передав ей какие-нибудь данные:

$ echo "a b c" | ./input_permutations

a, b, c,