Làm thế nào tôi có thể nhận được chính xác n dòng ngẫu nhiên từ một tệp với Perl?

Question

Theo dõi trên this câu hỏi, tôi cần có chính xác n dòng ngẫu nhiên trong một tệp (hoặc stdin). Điều này sẽ tương tự như head hoặc tail, ngoại trừ tôi muốn một số từ giữa.

Bây giờ, ngoài việc lặp lại tệp với các giải pháp cho câu hỏi được liên kết, cách tốt nhất để có được chính xác n dòng trong một lần chạy là gì?

Để tham khảo, tôi đã cố gắng này:

#!/usr/bin/perl -w 
use strict; 
my $ratio = shift; 
print $ratio, "\n"; 
while() { 
    print if ((int rand $ratio) == 1); 
} 

nơi $ratio là tỷ lệ thô của dòng tôi muốn. Ví dụ, nếu tôi muốn 1 trong 10 dòng:

random_select 10 a.list 

Tuy nhiên, điều này không cung cấp cho tôi một số tiền chính xác:

aaa> foreach i (0 1 2 3 4 5 6 7 8 9) 
foreach? random_select 10 a.list | wc -l 
foreach? end 
4739 
4865 
4739 
4889 
4934 
4809 
4712 
4842 
4814 
4817 

Ý nghĩ khác tôi đã được slurping tập tin đầu vào và sau đó chọn n ngẫu nhiên từ mảng, nhưng đó là một vấn đề nếu tôi có một tập tin thực sự lớn.

Bất kỳ ý tưởng nào?

Chỉnh sửa: Đây là bản sao chính xác của câu hỏi this.

Answer 1

Đây là thuật toán một lần tuyệt vời mà tôi đã đưa ra, có độ phức tạp thời gian O (N) và độ phức tạp không gian O (M), để đọc M dòng từ tệp N-line.

Giả sử M < = N.

1. Hãy S là tập hợp của các dòng chọn. Khởi tạo S thành M dòng đầu tiên của tệp. Nếu thứ tự của kết quả cuối cùng là quan trọng, hãy trộn ngẫu nhiên S ngay bây giờ.
2. Đọc ở dòng tiếp theo l. Cho đến nay, chúng tôi đã đọc tổng số n = M + 1 dòng. Xác suất mà chúng tôi muốn chọn l là một trong những dòng cuối cùng của chúng tôi là M/n.
3. Chấp nhận l với xác suất M/n; sử dụng RNG để quyết định có chấp nhận hay từ chối l.
4. Nếu l đã được chấp nhận, hãy chọn ngẫu nhiên một trong các dòng trong S và thay thế bằng l.
5. Lặp lại các bước 2-4 cho đến khi tệp đã hết dòng, tăng n với mỗi dòng mới được đọc.
6. Trả lại tập hợp S của các dòng đã chọn.

Answer 2

Có thể giải pháp:

1. quét một thời gian để đếm số dòng
2. quyết định số dòng để chọn ngẫu nhiên
3. quét một lần nữa, chọn dòng

Answer 3

Trong pseudo- mã:

use List::Util qw[shuffle]; 

# read and shuffle the whole file 
@list = shuffle(<>); 

# take the first 'n' from the list 
splice(@list, ...); 

Đây là triển khai nhỏ nhất, nhưng trước tiên bạn phải đọc toàn bộ tập tin, điều này sẽ yêu cầu bạn có đủ bộ nhớ.

Answer 4

@result =(); 

$k = 0; 
while(<>) { 
    $k++; 
    if (scalar @result < $n) { 
     push @result, $_; 
    } else { 
     if (rand <= $n/$k) { 
      $result[int rand $n] = $_; 
     } 
    } 
} 

print for @result; 

Answer 5

này có một đối số dòng lệnh duy nhất, đó là số dòng mà bạn muốn, N. N dòng đầu tiên được tổ chức, như bạn có thể không nhìn thấy nữa. Sau đó, bạn ngẫu nhiên quyết định xem có nên thực hiện dòng tiếp theo hay không. Và nếu bạn làm thế, bạn ngẫu nhiên quyết định dòng nào trong danh sách-N-N hiện tại để ghi đè.

#!/usr/bin/perl 
my $bufsize = shift; 
my @list =(); 

srand(); 
while (<>) 
{ 
    push(@list, $_), next if (@list < $bufsize); 
    $list[ rand(@list) ] = $_ if (rand($./$bufsize) < 1); 
} 
print foreach @list; 

Answer 6

Đây là một số mã Perl dài dòng nên hoạt động với các tệp lớn.

Trung tâm của mã này là nó không lưu toàn bộ tệp trong bộ nhớ, nhưng chỉ lưu trữ bù trừ trong tệp.

Sử dụng tell để nhận bù trừ. Sau đó, seek đến các địa điểm thích hợp để khôi phục các dòng.

Đặc điểm kỹ thuật tốt hơn của tệp mục tiêu và số dòng để có được còn lại như là một bài tập cho những người ít lười hơn I. Những vấn đề đó đã được giải quyết tốt.

#!/usr/bin/perl 

use strict; 
use warnings; 

use List::Util qw(shuffle); 

my $GET_LINES = 10; 

my @line_starts; 
open(my $fh, '<', 'big_text_file') 
    or die "Oh, fudge: $!\n"; 

do { 
    push @line_starts, tell $fh 
} while (<$fh>); 

my $count = @line_starts; 
print "Got $count lines\n"; 

my @shuffled_starts = (shuffle @line_starts)[0..$GET_LINES-1]; 

for my $start (@shuffled_starts) { 

    seek $fh, $start, 0 
     or die "Unable to seek to line - $!\n"; 

    print scalar <$fh>; 
} 

Answer 7

Không cần biết số dòng thực trong tệp. Chỉ cần tìm một địa điểm ngẫu nhiên và giữ dòng tiếp theo. (Dòng hiện tại rất có thể là một phần.)

Cách tiếp cận này sẽ rất nhanh đối với các tệp lớn, nhưng nó sẽ không hoạt động đối với STDIN. Heck, không có gì loại bộ nhớ đệm toàn bộ tập tin trong bộ nhớ sẽ làm việc cho STDIN. Vì vậy, nếu bạn phải có STDIN, tôi không thấy làm thế nào bạn có thể được nhanh chóng/giá rẻ cho các tập tin lớn.

Bạn có thể phát hiện STDIN và chuyển sang phương pháp được lưu trong bộ nhớ cache, nếu không sẽ nhanh.

 
#!perl 
use strict; 

my $file='file.txt'; 
my $count=shift || 10; 
my $size=-s $file; 

open(FILE,$file) || die "Can't open $file\n"; 

while ($count--) { 
    seek(FILE,int(rand($size)),0); 
    $_=readline(FILE);       # ignore partial line 
    redo unless defined ($_ = readline(FILE)); # catch EOF 
    print $_; 
}