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

Question

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

perl

10

我有一个大小为P的数组A =[a1,a2,a3,...aP]。我需要从数组A中随机选出q个元素。

我计划使用一个循环进行q次迭代，在每次迭代中随机选择一个A中的元素。但是我该如何确保在每次迭代中选择的数字都不同？

- bit-question

对于比洗牌更快的方法，请搜索实现无重复随机抽样的代码（例如，我记得Python Cookbook中有相关内容）。此外，还可以参考Donald Knuth的《计算机程序设计艺术》，第3.4.2节。 - FMc

4个回答

8

From perldoc perlfaq4:

How do I shuffle an array randomly?

If you either have Perl 5.8.0 or later installed, or if you have Scalar-List-Utils 1.03 or later installed, you can say:

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

If not, you can use a 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

- Zaid

1

List::Gen非常缓慢，每秒只能完成几千个选择，这是由于其速度低效的惰性洗牌算法所致。List::Util::shuffle快了三个数量级，每秒可以完成几十万个选择。我已经通知了List::Gen的作者。 - Schwern

@Schwern => List::Gen的->pick的重点在于它是惰性计算的。这使得从非常大、变化、难以访问或无限数据源中随机选择元素成为可能。这必然会带来性能上的成本。当以列表上下文调用->pick($n)时，我将考虑使用急切算法，因为这种用法需要一次性计算所有元素，可以更加优化。 - Eric Strom

4

你可以使用Fisher-Yates shuffle algorithm来随机排列你的数组，然后使用前q个元素的切片。以下是PerlMonks的代码示例：

# randomly permutate @array in place
sub fisher_yates_shuffle
{
    my $array = shift;
    my $i = @$array;
    while ( --$i )
    {
        my $j = int rand( $i+1 );
        @$array[$i,$j] = @$array[$j,$i];
    }
}

fisher_yates_shuffle( \@array );    # permutes @array in place

你可以通过在选择了q个随机元素后停止洗牌来优化此操作。(按照现在的写法，你需要选择最后的q个元素。)

- Ted Hopp

该算法可在List::Util::shuffle中使用。 - ikegami

@ikegami - 确实如此。但是，如果您使用List::Util::shuffle，则无法使用我提到的优化；如果P非常大而q要小得多，则可能会成为一个因素。 - Ted Hopp

-1

你可以构造一个大小为P的布尔类型二维数组，并将选中的数字存储为true。当选择数字时，请检查第二个表格；如果是“true”，则必须选择下一个。

- theWalker

1

如果"q"接近"P"，尤其是当这两个数字很大时，那将会非常慢。如果q > P，它将进入一个无限循环。解决这个问题的标准算法在我的答案中有描述。 - Alex D

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Schwern · Accepted Answer

其他答案都涉及到对数组进行洗牌，这是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 @picks, $deck->[$idx];
        $picks_left--;
    }

    $num_left--;
    $idx++;
}

这是perl5i如何实现其pick方法（即将发布的版本）。

为了深入理解为什么它有效，以从4个元素列表中选出2个为例。每个元素应该有1/2的机会被选中。

1. (2 picks, 4 items):         2/4 = 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

Next有1/4的机会两个元素已经被选中（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

虽然不是严格的证明，但这足以让您相信它是有效的。