ruby - 仅从 Ruby 中的数组中选择随机元素

Question

我知道我可以使用 sample 方法从数组中选择一个随机元素，但这会留下一个元素被多次选择的可能性。我可以先打乱数组，然后按顺序从第一个元素到最后一个元素，但我知道这是内存密集型的，如果可能的话，我正在寻找一种不那么密集的方法！

Answer 1

sample接受一个论点：

[*(1..10)].sample(5) #=>[3, 4, 1, 8, 9] 

没有元素会被选择两次。

Answer 2

洗牌数组不是内存密集型的。Ruby 有一个默认的 shuffle 实现，它被称为Array.shuffle!. 查看源代码，您可以看到（它是 C）：

rb_ary_shuffle_bang(ary)
    VALUE ary;
{
    long i = RARRAY(ary)->len;

    rb_ary_modify(ary);
    while (i) {
        long j = rb_genrand_real()*i;
        VALUE tmp = RARRAY(ary)->ptr[--i];
        RARRAY(ary)->ptr[i] = RARRAY(ary)->ptr[j];
        RARRAY(ary)->ptr[j] = tmp;
    }
    return ary;
}

此实现遵循经典的Fisher-Yates 算法。

所以：

1. 使用shuffle!. 时间复杂度是O(n)，不需要额外的内存。
2. 遍历数组。时间复杂度是O(n)，不需要额外的内存（只需要一个整数来保存当前索引）。

总体而言，您拥有所需的一切，无需额外的内存和时间复杂度O(n)。

Answer 3

如果数组元素非常大，您可以尝试简单地打乱索引列表并对其进行迭代：

a = %w{a b c d e f g h}

[*0...a.size].shuffle.each do |index|
  puts a[index]
end

Answer 4

您必须跟踪您已经选择的那些元素；你打算怎么做，把它们放在自己的数组中？

洗牌和迭代。这不会比跟踪那些已经选择的元素占用更多的内存。