c++ - 从长(且合理)稀疏 vector 中选择随机元素的最有效方法是什么？

Question

我有一个长的、相当稀疏的 bool vector ，我想从中迭代地选择随机元素，我想知道这样做最有效的方法是什么。

vector 的长度最多可达 100,000 个元素，并且每 20 个元素中大约有 1 个在任何时候都为“真”。

选择这些元素之一，偶尔会导致其他元素可供选择；所以我不能只做一次 bool vector 的初始传递来获取所有可用元素的索引，然后随机播放该 vector 和弹出元素，因为可用元素列表发生了变化。

我已经想出了几个想法，但不能真正说出哪个是最好的。因此，我们将不胜感激任何见解。

方法一:

given input boolean vector A
create boolean vector B    // to store previously selected elements
create int vector C        // to store currently available element indices 
while stopping condition not met:
    for each element a in A:
        if a is "true":
            append index of a to C
    generate random integer i between 0 and length of A
    set i-th element of C in A to "false"
    set i-th element of C in B to "true"
    compute any new "true" values of A

方法二:

given input boolean vector A
create boolean vector B    // to store previously selected elements
create int vector C        // to store currently available element indices 
for each element a in A:
    if a is "true":
        append index of a to C
shuffle C
while stopping condition not met:
    pop element from back of C
    set i-th element of C in A to "false"
    set i-th element of C in B to "true"
    compute any new "true" values of A
    if new values in A computed:
        append index of new available element to C 
        shuffle C

因为并非 A 中的每个选择都会导致可用元素集发生变化，我认为方法 2 可能会比方法 1 更好，除了我不确定洗牌长 vector 会导致多少工作量这一事实。

方法三:

given input boolean vector A
create boolean vector B    // to store previously selected elements
while stopping condition not met:
    generate random integer i between 0 and length of A
    If i is "true" in A:
        set i in A to "false"
        set i in B to "true"
        compute any new "true" values of A

最后这种方式看起来有点幼稚和简单，但我想如果每20个元素中有1个左右为真(除了最后一组元素，当被选中的元素不能再添加时) , 那么平均来说它只需要大约 20 次尝试就可以找到一个可选元素，这实际上比完全传递输入 vector 或洗牌可用索引的 vector (特别是如果所讨论的 vector 是相当长)。找到最后几个会非常困难，但我可以跟踪已选择的数量，一旦剩余数量低于某个水平，我可以更改最后一批的选择方式。

有没有人知道哪个可能更有效率？如果有任何不同，将使用 C++ 实现。

谢谢你的帮助

Answer 1

您可以将稀疏 vector 的表示更改为以下 -

1. 主要 vector (您现在拥有的 vector )
2. 真 vector (所有“真”索引的列表)

您的操作现在变成了 -

Insert:   
    check if i in Primary Vector
    if false, set to true and add to True Vector

Delete:
    check if i in Primary Vector
    if true, set to false and remove from True Vector by swapping
    with last element and reducing size

(为此您需要从 Primary Vector 到 True Vector 的指针)。

Random:
    Generate random index j from size of (True Vector)
    return True Vector[j]

您的所有操作都可以以 O(1) 复杂度完成。