Come posso prendere n elementi a caso da un array Perl?

Question

Ho un array, A = [a1,a2,a3,...aP] con dimensione P. Devo campionare gli elementi q dall'array A.

Ho intenzione di utilizzare un ciclo con le iterazioni q e selezionare a caso un elemento da A ad ogni iterazione. Ma come posso assicurarmi che il numero selezionato sarà diverso ad ogni iterazione?

Answer 1

Le altre risposte tutte coinvolgere mischiare la matrice, che è O(n). Significa modificare l'array originale (distruttivo) o copiare l'array originale (intensivo della memoria).

Il primo modo per rendere più efficiente la memoria non è mescolare l'array originale ma mischiare una serie di indici.

# 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 ]; 

È almeno indipendente dal contenuto del @deck, ma la sua ancora O (nlogn) prestazioni e (n) O memoria.

Un algoritmo più efficiente (non necessariamente più veloce, dipende da quanto grande è l'array) è quello di esaminare ogni elemento dell'array e decidere se farlo diventare nell'array. Questo è simile a how you select a random line from a file without reading the whole file into memory, ogni linea ha una possibilità 1/N di essere scelta dove N è il numero di linea. Quindi la prima linea ha una possibilità di 1/1 (viene sempre selezionata). Il prossimo ha un 1/2. Quindi 1/3 e così via. Ogni prelievo sarà sovrascrivere la scelta precedente. Ciò si traduce in ogni linea che ha una possibilità 1/total_lines.

Si può lavorare per te. Un file a una riga ha una probabilità di 1/1, quindi il primo viene sempre selezionato. Un file a due righe ... la prima riga ha una probabilità di sopravvivenza di 1/1 e 1/2, che è 1/2, e la seconda linea ha una possibilità di 1/2. Per un file di tre righe ... la prima riga ha una probabilità di 1/1 di essere prelevata, quindi una possibilità di sopravvivenza di 1/2 * 2/3 che è 2/6 o 1/3. E così via.

L'algoritmo è O (n) per velocità, itera su un array non ordinato una volta e non consuma più memoria di quanto sia necessario per memorizzare i plettri.

Con una piccola modifica, questo funziona per più scelte. Invece di una possibilità 1/$position, è $picks_left/$position. Ogni volta che un plettro ha successo, decrementi $ picks_left. Lavori dalla posizione alta a quella bassa. Diversamente da prima, non si sovrascrive.

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++; 
} 

Questo è how perl5i implements its pick method (prossimo rilascio).

Per comprendere visceralmente il motivo per cui questo funziona, prendere l'esempio del prelievo 2 da un elenco di 4 elementi. Ognuno dovrebbe avere una probabilità 1/2 di essere scelto.

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

Abbastanza semplice. Il prossimo elemento ha una probabilità di 1/2 che un elemento sarà già stato scelto, nel qual caso è probabile che sia 1/3. Altrimenti le sue possibilità sono 2/3. Facendo due conti ...

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

successivo ha un 1/4 di possibilità che entrambi gli elementi saranno già raccolti (1/2 * 1/2), quindi non ha alcuna possibilità; 1/2 possibilità che venga selezionato solo uno, quindi ha 1/2; e il rimanente 1/4 che nessun elemento sarà scelto, nel qual caso è 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 

Infine, per l'ultimo elemento, c'è un 1/2 il precedente ha preso l'ultima scelta.

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

Non esattamente una prova, ma buono per convincere se stesso che funziona.

Answer 2

È possibile costruire il secondo array, booleano con dimensione P e memorizzare true per i numeri selezionati. E quando viene selezionato il numero, controlla la seconda tabella; nel caso "true" devi scegliere il prossimo.

Answer 3

È possibile utilizzare lo Fisher-Yates shuffle algorithm per permutare in modo casuale la matrice e quindi utilizzare una porzione dei primi q elementi. Ecco il codice da 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 

Probabilmente si può ottimizzare questo avendo la fermata riordino dopo che ha q elementi casuali selezionati. (Il modo in cui questo è stato scritto, che ci si vuole ultimi elementi q.)

Answer 4

Da perldoc perlfaq4:

Come mescolo un array in modo casuale?

Se hai i Perl 5.8.0 o versione successiva, o se hai Scalar-List-Utils 1.03 o versione successiva, si può dire:

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

In caso contrario, è possibile utilizzare un Fisher-Yates mescola.

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; 

---

Si potrebbe anche usare List::Gen:

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