Как я могу произвольно взять n элементов из массива Perl?

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 реализует свой метод выбора (следующий выпуск).

Чтобы понять, почему это работает, возьмите пример выбора 2 из списка из 4 элементов. Каждый должен иметь 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/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

Не совсем доказательство, но хорошо, чтобы убедить себя, что это работает.

Answer 2

С perldoc perlfaq4:

Как случайным образом перемешать массив?

Если у вас установлен Perl 5.8.0 или новее, или если у вас Scalar-List-Utils 1.03 или более поздней версии, вы можете сказать:

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

Если нет, вы можете использовать тасовку Фишера-Йейтса.

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

Answer 3

Вы можете использовать алгоритм случайного перемешивания Фишера-Йейтса , чтобы случайным образом переставить ваш массив, а затем использовать часть первых 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 элементов.)

Answer 4

Вы можете создать второй массив, логический с размером P и сохранить true для выбранных чисел. И когда выбран номер, проверьте вторую таблицу; в случае «true» вы должны выбрать следующий.