Tôi có thể lấy n phần tử ngẫu nhiên từ một mảng Perl như thế nào?

Question

Tôi có một mảng, A = [a1,a2,a3,...aP] với kích thước P. Tôi phải lấy mẫu q các yếu tố từ mảng A.

Tôi dự định sử dụng vòng lặp với các lần lặp q và chọn ngẫu nhiên một elment từ A tại mỗi lần lặp. Nhưng làm cách nào tôi có thể đảm bảo rằng số được chọn sẽ khác nhau ở mỗi lần lặp?

Answer 1

Những câu trả lời khác đều liên quan đến việc xáo trộn các mảng, đó là O(n). Nó có nghĩa là sửa đổi mảng ban đầu (phá hoại) hoặc sao chép mảng ban đầu (bộ nhớ chuyên sâu).

Cách đầu tiên để làm cho bộ nhớ hiệu quả hơn là không trộn các mảng gốc gốc nhưng để trộn một mảng chỉ mục.

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

Ít nhất là độc lập với nội dung của @deck, nhưng hiệu suất O (nlogn) và bộ nhớ O (n) vẫn còn.

Thuật toán hiệu quả hơn (không nhất thiết phải nhanh hơn, phụ thuộc vào mảng lớn của bạn) là xem xét từng phần tử của mảng và quyết định xem nó có biến thành mảng không. Điều này tương tự như how you select a random line from a file without reading the whole file into memory, mỗi dòng có 1/N cơ hội được chọn trong đó N là số dòng. Vì vậy, dòng đầu tiên có một cơ hội 1/1 (nó luôn luôn được chọn). Tiếp theo có 1/2. Sau đó, 1/3 và như vậy. Mỗi lựa chọn sẽ ghi đè lựa chọn trước đó. Điều này dẫn đến mỗi dòng có cơ hội 1/total_lines.

Bạn có thể tự mình làm việc đó. Một tập tin một dòng có một cơ hội 1/1 để người đầu tiên luôn được chọn. Một tập tin hai dòng ... dòng đầu tiên có một 1/1 sau đó một cơ hội sống sót 1/2, đó là 1/2, và dòng thứ hai có một cơ hội 1/2. Đối với một tập tin ba dòng ... dòng đầu tiên có một cơ hội 1/1 được chọn, sau đó một 1/2 * 2/3 cơ hội sống sót là 2/6 hoặc 1/3. Và cứ thế.

Thuật toán là O (n) cho tốc độ, nó lặp qua một mảng không có thứ tự một lần và không tiêu thụ nhiều bộ nhớ hơn mức cần thiết để lưu trữ các lựa chọn.

Với một chút sửa đổi, điều này phù hợp với nhiều lựa chọn. Thay vì một cơ hội 1/$position, đó là $picks_left/$position. Mỗi lần chọn thành công, bạn giảm $ picks_left. Bạn làm việc từ vị trí cao đến vị trí thấp. Không giống như trước đây, bạn không ghi đè lên.

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

Đây là how perl5i implements its pick method (sắp phát hành tiếp theo).

Để hiểu nội tại vì lý do này hoạt động, hãy lấy ví dụ về chọn 2 từ danh sách 4 phần tử. Mỗi cần có một cơ hội 1/2 được chọn.

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

Đủ đơn giản. Phần tử tiếp theo có một phần cơ hội là một phần tử đã được chọn, trong trường hợp đó nó có thể là 1/3. Nếu không thì cơ hội của nó là 2/3. Làm toán học ...

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

Tiếp theo có 1/4 cơ hội cả hai phần tử đã được chọn (1/2 * 1/2), khi đó sẽ không có cơ hội; 1/2 cơ hội chỉ có một người được chọn, sau đó nó có 1/2; và 1/4 còn lại không có vật phẩm nào được chọn trong trường hợp đó là 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 

Cuối cùng, đối với mặt hàng cuối cùng, có 1/2 số trước đã chọn lần cuối.

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

Không chính xác là bằng chứng, nhưng tốt để thuyết phục bản thân nó hoạt động.

Answer 2

Bạn có thể tạo mảng thứ hai, boolean với kích thước P và lưu trữ đúng cho số được chọn. Và khi số được chọn, kiểm tra bảng thứ hai; trong trường hợp "true" bạn phải chọn tiếp theo.

Answer 3

Bạn có thể sử dụng Fisher-Yates shuffle algorithm để hoán vị ngẫu nhiên mảng của mình và sau đó sử dụng một phần của các phần tử q đầu tiên. Dưới đây là mã từ 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 

Bạn có thể tối ưu hóa điều này bằng cách dừng ngẫu nhiên sau khi nó có q yếu tố ngẫu nhiên được chọn. (Cách này được viết, bạn muốn các yếu tố q cuối cùng .)

Answer 4

Từ perldoc perlfaq4:

Làm thế nào để xáo trộn một mảng ngẫu nhiên?

Nếu bạn hoặc đã Perl 5.8.0 hoặc mới hơn được cài đặt, hoặc nếu bạn có Scalar-List-Utils 1,03 hay muộn cài đặt, bạn có thể nói:

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

Nếu không, bạn có thể sử dụng một Fisher-Yates xáo trộn.

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; 

---

Bạn cũng có thể sử dụng List::Gen:

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