对大vector进行采样

有时我们需要处理非常庞大的数据量，不可能在短时间内处理完这些数据。这样的话，数据可能就需要采样来减少要处理的数据量，从而加速整个处理过程。另一些情况下，不减少数据量也能加快程序处理的速度，不过这需要对一些数据进行存储或变换。

采样最原始的方式是每隔N个数据点，采样一次。在大多数情况下这样做没有问题，但是在信号处理中，其会引发一种称为混淆的数学情况。当减少两个随机采样点的距离时，这种现象会减弱。我们看一下下面的图，这张图就很能说明问题——当原始信号为一个sin波时，图例为三角的曲线就表示对这个曲线进行每隔100个点的取样。

对大vector进行采样 - 图1

不幸的是，其采样得到的值都是同一个Y值！连接起来就是与X轴平行的一条线。平方点采样，其每隔100+random(-15, +15)个值进行采样。不过，这样连接起来的曲线看起来和原始的曲线还是相差很远，所以在这个例子中就不能以固定的步长进行采样。

std::sample函数不会添加随机值来改变采样的步长，而是采用完全随机的点进行采样。所以其工作方式与上图所显示的大为不同。

How to do it…

我们将对一个具有随机值的大vector进行采样。随机数据符合正态分布。采样结果也要符合正态分布，来让我们看下代码：

  1. 首先包含必要的头文件，以及声明所使用的命名空间。

    1. #include <iostream>
    2. #include <vector>
    3. #include <random>
    4. #include <algorithm>
    5. #include <iterator>
    6. #include <map>
    7. #include <iomanip>
    9. using namespace std;

  2. 使用常数直接对变量进行初始化。第一个值代表了vector的的长度，第二个数代表了采样的步长：

    1. int main()
    2. {
    3.     const size_t data_points {100000};
    4.     const size_t sample_points {100};

  3. 我们要使用符合正态分布的随机值生成器来将vector填满。这里先来确定正太分布的平均值和标准差：

    1.     const int mean {10};
    2.     const size_t dev {3};

  4. 现在，我们来设置随机数生成器。首先，我们实例化一个随机设备，然后给定一个随机种子，对生成器进行初始化。然后，就可以得到对应分布的随机生成器：

    1.     random_device rd;
    2.     mt19937 gen {rd()};
    3.     normal_distribution<> d {mean, dev};

  5. 对vector进行初始化，并用随机值将vector进行填充。这里会使用到std::generate_n算法，其会将随机值，通过back_inserter迭代器插入vector中。生成函数对象包装成了d(gen)表达式，其能生成符合分布的随机值：

    1.     vector<int> v;
    2.     v.reserve(data_points);
    4.     generate_n(back_inserter(v), data_points,
    5.         [&] { return d(gen); });

  6. 我们再实例化另一个vector，其来放采样过后的数值：

    1.     vector<int> samples;
    2.     v.reserve(sample_points);

  7. std::sample算法与std::copy的原理类似，不过其需要两个额外的参数：采样数量和随机值生成对象。前者确定输入范围，后者去确定采样点：

    1.     sample(begin(v), end(v), back_inserter(samples),
    2.         sample_points, mt19937{random_device{}()});

  8. 这样就完成了采样。代码的最后展示一下我们的采样结果。输入数据符合正态分布，如果采样算法可行，那么其采样的结果也要符合正态分布。为了展示采样后的值是否符合正态分布，我们将数值的直方图进行打印：

    1.     map<int, size_t> hist;
    3.     for (int i : samples) { ++hist[i]; }

  9. 最后，我们使用循环打印出直方图：

    1.     for (const auto &[value, count] : hist) {
    2.         cout << setw(2) << value << " "
    3.             << string(count, '*') << '\n';
    4.     }
    5. }

  10. 编译并运行程序，我们将看到采样后的结果，其也符合正态分布：对大vector进行采样 - 图2

How it works…

std::sample算法是C++17添加的。其函数签名如下：

  1. template<class InIterator, class OutIterator,
  2. class Distance, class UniformRandomBitGenerator>
  3. OutIterator sample(InIterator first, InIterator last,
  4.                  SampleIterator out, Distance n,
  5.                  UniformRandomBitGenerator&& g);

其输入范围有first和last迭代器确定，out迭代器作为采样输出。这些迭代器对于该函数来说和std::copy类似，元素从一个容器拷贝到另一个。std::sample算法只会拷贝输入中的一部分，因为采样结果只有n个元素。其在内部使用均匀分布，所以能以相同的概率选择输入范围中的每个数据点。