如何从Perl数组中随机取出n个元素？

Question

我有一个A = [a1,a2,a3,...aP]大小的阵列P.我必须q从数组A中采样元素.

我计划使用带q迭代的循环,并在每次迭代时从A中随机选择一个元素.但是,我怎样才能确保每次迭代时拾取的数字都不同？

Answer 1

其他答案都涉及改组阵列,这是O(n).这意味着修改原始数组(破坏性)或复制原始数组(内存密集型).

提高内存效率的第一种方法不是对原始数组进行混洗,而是对一系列索引进行混洗.

# Shuffled list of indexes into @deck
my @shuffled_indexes = shuffle(0..$#deck);

# Get just N of them.
my @pick_indexes = @shuffled_indexes[ 0 .. $num_picks - 1 ];  

# Pick cards from @deck
my @picks = @deck[ @pick_indexes ];

它至少独立于@deck的内容,但它仍然是O(nlogn)性能和O(n)内存.

一个更有效的算法(不一定更快,取决于你的数组现在很大)是查看数组的每个元素,并决定它是否会进入数组.这类似于如何从文件中选择随机行而不将整个文件读入内存,每行有1/N的机会被选中,其中N是行号.所以第一行有1/1的机会(它总是被选中).下一个是1/2.然后是1/3,依此类推.每个选择都将覆盖之前的选择.这导致每一行具有1/total_lines机会.

你可以自己解决.一行文件有1/1的机会,所以第一个文件总是被选中.一个双行文件......第一行有1/1然后是1/2的幸存机会,即1/2,第二行有1/2机会.对于三行文件......第一行有1/1的机会被选中,然后有1/2*2/3的幸存机会,即2/6或1/3.等等.

该算法的速度为O(n),它迭代一次无序数组,并且不会消耗比存储选择所需的更多的内存.

稍作修改,这适用于多个选择.不是1/$position机会,而是机会$picks_left / $position.每次选择成功时,您都会减少$ picks_left.你从高位到低位工作.与以前不同,您不会覆盖.

my $picks_left = $picks;
my $num_left = @$deck;
my @picks;
my $idx = 0;
while($picks_left > 0 ) {  # when we have all our picks, stop
    # random number from 0..$num_left-1
    my $rand = int(rand($num_left));

    # pick successful
    if( $rand < $picks_left ) {
        push @result, $deck->[$idx];
        $picks_left--;
    }

    $num_left--;
    $idx++;
}

这就是perl5i如何实现其pick方法(即将发布的下一个版本).

为了理解其中的原因,请以4元素列表中的选择2为例.每个人应该有1/2的机会被选中.

1. (2 picks, 4 items):         2/4 = 1/2

很简单.下一个元素有一个1/2的机会,一个元素已经被选中,在这种情况下,它有可能是1/3.否则它的机会是2/3.做数学......

2. (1 or 2 picks,  3 items):   (1/3 * 1/2) + (2/3 * 1/2) = 3/6 = 1/2

接下来有四分之一的机会,两个元素都已经被挑选(1/2*1/2),那么它就没有机会; 只有一个将被挑选的1/2机会,然后它有1/2; 剩下的1/4没有任何物品被挑选,在这种情况下它是2/2.

3. (0, 1 or 2 picks, 2 items): (0/2 * 1/4) + (1/2 * 2/4) + (2/2 * 1/4) = 2/8 + 1/4 = 1/2

最后,对于最后一个项目,有一个前一个选择的1/2.

4. (0 or 1 pick, 1 items):     (0/1 * 2/4) + (1/1 * 2/4) = 1/2

不完全是一个证据,但有利于说服自己有效.

Answer 2

来自perldoc perlfaq4:

如何随机随机播放一个数组？

如果您安装了Perl 5.8.0或更高版本,或者安装了Scalar-List-Utils 1.03或更高版本,您可以说:

use List::Util 'shuffle';
@shuffled = shuffle(@list);

如果没有,你可以使用Fisher-Yates shuffle.

sub fisher_yates_shuffle {

    my $deck = shift;  # $deck is a reference to an array
    return unless @$deck; # must not be empty!

    my $i = @$deck;
    while (--$i) {
        my $j = int rand ($i+1);
        @$deck[$i,$j] = @$deck[$j,$i];
    }
}


# shuffle my mpeg collection
# 

my @mpeg = <audio/*/*.mp3>;
fisher_yates_shuffle( \@mpeg );    # randomize @mpeg in place
print @mpeg;

你也可以使用List::Gen:

my $gen = <1..10>;
print "$_\n" for $gen->pick(5);  # prints five random numbers