仅在Ruby ONCE中从数组中选取随机元素

Question

我知道我可以使用样本方法从数组中选择一个随机元素,但这样就可以不止一次地拾取元素.我可以先将数组洗牌,然后按顺序从第一个元素到最后一个元素,但我知道这是内存密集型的,如果可能的话,我正在寻找一种不太密集的方法!

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).