从真值中随机选择STL向量的索引

Question

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

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创建,我使用这个答案找到索引:

有没有更像STL(或C++ 11)的方法,也许是一个不创建中间数组的方法？在这个例子A中很小,但在我的生产代码中,这个选择过程是在内循环中,A是非静态的,数千个元素是长的.

Answer 1

一个很好的方法是水库采样.

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

然后,继续走阵列.每当你找到一个非零值,你随意可以更改其新的索引是你可能的答案,随概率.

如果您需要来自数组的M个随机索引值,此算法也可以正常工作.

有什么好处的,就是你只走了一次每个元素,而你不需要一个单独的内存结构来记录非零元素.速度为O(N),内存为O(M),在您的情况下,它在内存中为O(1),因为您只需要1个随机值.

另一方面,随机数发生器传统上很慢.因此,您可能希望针对人们在此提出的任何其他想法进行性能测试,以了解速度与内存的权衡对您是否值得.