Как я могу получить ровно n случайных строк из файла с Perl? - PullRequest
Новая
       37

Как я могу получить ровно n случайных строк из файла с Perl?

6 голосов
/ 13 мая 2009

В ответ на этот вопрос мне нужно получить ровно n строк в произвольном порядке из файла (или stdin). Это будет похоже на head или tail, за исключением того, что я хочу немного из середины.

Теперь, кроме перебора файла с решениями связанного вопроса, как лучше всего получить ровно n строк за один прогон?

Для справки, я попробовал это: 

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

где $ratio - приблизительный процент строк, которые я хочу. Например, если я хочу 1 в 10 строках: 

random_select 10 a.list

Однако, это не дает мне точную сумму: 

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

Еще одна мысль, которая у меня возникла, - это хлюпать входной файл, а затем произвольно выбирать n из массива, но это проблема, если у меня действительно большой файл.

Есть идеи?

Редактировать: Это точная копия этого вопроса.

Ответы [ 7 ]

5 голосов
/ 13 мая 2009

Вот хороший однопроходный алгоритм, который я только что придумал, имеющий O (N) временную сложность и O (M) пространственную сложность, для чтения M строк из N-строкового файла.

Предположим, М <= N. </p>

  1. Пусть S будет набором выбранных линий. Инициализируйте S до первых M строк файла. Если порядок конечного результата важен, перетасуйте S сейчас.
  2. Читайте в следующей строке l. Пока что мы прочитали n = M + 1 всего строк. Следовательно, вероятность того, что мы хотим выбрать l в качестве одной из наших последних строк, равна M/n.
  3. Принять l с вероятностью M/n; используйте RNG, чтобы решить, принимать или отклонять l.
  4. Если l было принято, случайным образом выберите одну из строк в S и замените ее на l.
  5. Повторяйте шаги 2-4, пока файл не будет исчерпан строками, увеличивая n с каждой новой прочитанной строкой.
  6. Вернуть набор S выбранных строк.
2 голосов
/ 13 мая 2009

Это принимает единственный аргумент командной строки, который является номером строки, которую вы хотите, N. Первые N строк удерживаются, так как вы можете больше не видеть. После этого вы случайно решить, следует ли взять следующую строку. И если вы это сделаете, вы случайным образом решите, какая строка в текущем списке-N перезаписать. 

#!/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;
1 голос
/ 14 мая 2009

Нет необходимости знать фактический номер строки в файле. Просто найдите случайное место и сохраните строку next . (Текущая строка, скорее всего, будет частичной.)

Этот подход должен быть очень быстрым для больших файлов, но он не будет работать для STDIN. Черт возьми, ничто вроде кэширования всего файла в памяти не будет работать для STDIN. Так что, если у вас есть STDIN, я не понимаю, как вы можете быть быстрым / дешевым для больших файлов.

Вы можете обнаружить STDIN и переключиться на кешированный подход, иначе будьте быстры. 

#!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 $_;
}
1 голос
/ 13 мая 2009 
@result = ();

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

print for @result;
1 голос
/ 13 мая 2009

Возможное решение:

  1. сканирование один раз для подсчета количества строк
  2. решить, какой номер строки выбрать случайным образом
  3. Сканирование еще раз, выберите строку
0 голосов
/ 14 мая 2009

Вот подробный Perl-код, который должен работать с большими файлами.

Суть этого кода в том, что он не хранит весь файл в памяти, а сохраняет только смещения в файле.

Используйте tell, чтобы получить смещения. Затем seek в соответствующие места, чтобы восстановить линии.

Лучшее указание целевого файла и количества строк, которые нужно получить, оставлено в качестве упражнения для тех, кто менее ленив, чем я. Эти проблемы хорошо решены. 

#!/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>;
}
0 голосов
/ 13 мая 2009

В псевдокоде: 

use List::Util qw[shuffle];

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

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

Это самая тривиальная реализация, но сначала вам нужно прочитать весь файл, что потребует достаточной памяти.

...