c++ - 从真值的 STL vector 中随机选择索引

Question

我有一个看起来像这样的 vector :

vector<int> A = {0, 1, 1, 0, 0, 1, 0, 1};

我想从 A 的非零值中选择一个随机索引。使用此示例 A，我想从数组 {1,2,5,7} 中随机选择一个元素。

目前我通过创建另一个数组来做到这一点

vector<int> b;
for(int i=0;i<A.size();i++)
    if(A[i]) 
        b.push_back(i);

创建 b 后，我使用以下答案找到索引:

get random element from container

是否有更类似于 STL(或 C++11)的方式来执行此操作，也许不创建中间数组？在此示例中，A 很小，但在我的生产代码中，此选择过程处于内部循环中，并且 A 是非静态的并且有数千个元素。

Answer 1

一个很好的方法是 Reservoir Sampling .

简而言之，您遍历数组直到找到第一个非零值，并将该索引记录为您可能返回的第一个可能的答案。

然后，你继续走阵。每次找到非零值时，您可能随机更改哪个新索引是您可能的答案，概率会降低。

如果您需要数组中的 M 个随机索引值，此算法也很有效。

这样做的好处在于，您只需遍历每个元素一次，并且不需要单独的内存结构来记录非零元素。速度为 O(N)，内存为 O(M)，在您的情况下，内存为 O(1)，因为您只需要 1 个随机值。

另一方面，随机数生成器传统上非常慢。因此，您可能希望根据人们在这里提出的任何其他想法对此进行性能测试，看看速度与内存之间的权衡对您来说是否值得。