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

#include

#include

#include

#include

#include

#include

#include

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 v;

  v.reserve(data_points);

  generate_n(back_inserter(v), data_points,

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

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

  vector 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 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 Distance, class UniformRandomBitGenerator>

OutIterator sample(InIterator first, InIterator last,

                   SampleIterator out, Distance n,

                   UniformRandomBitGenerator&& g);

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

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