Comment puis-je obtenir exactement n lignes aléatoires à partir d'un fichier avec Perl?

Question

Suite à la question this, j'ai besoin d'obtenir exactement n lignes au hasard sur un fichier (ou stdin). Ce serait similaire à head ou tail, sauf que j'en veux du milieu.

Maintenant, en dehors de la boucle sur le fichier avec les solutions à la question liée, quel est le meilleur moyen d'obtenir exactement n lignes en une seule fois?

Pour référence, j'ai essayé ceci:

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

où $ratio est le pourcentage approximatif de lignes que je veux. Par exemple, si je veux 1 à 10 lignes:

random_select 10 a.list 

Cependant, cela ne me donne pas un montant exact:

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 

L'autre pensée que j'avais été siphonage le fichier d'entrée, puis en choisissant n au hasard dans le tableau, mais c'est un problème si j'ai un très gros fichier.

Des idées?

Modifier: Ceci est une copie exacte de la question this.

Answer 1

Voici un bon algorithme à un passage que je viens de créer, ayant une complexité de temps O (N) et une complexité d'espace O (M), pour lire des lignes M à partir d'un fichier N-line.

On suppose M < = N.

1. Soit S le jeu de lignes choisies. Initialiser S aux premières lignes M du fichier. Si l'ordre du résultat final est important, mélangez maintenant S.
2. Lire dans la ligne suivante l. Jusqu'à présent, nous avons lu n = M + 1 lignes totales. La probabilité que nous voulions choisir l comme l'une de nos dernières lignes est donc M/n.
3. Accepter l avec probabilité M/n; utiliser un RNG pour décider d'accepter ou de rejeter l.
4. Si l a été accepté, choisissez au hasard l'une des lignes S et remplacez-la par l.
5. Répétez les étapes 2 à 4 jusqu'à épuisement des lignes, en incrémentant n à chaque nouvelle ligne lue. Retourne l'ensemble S des lignes choisies.

Answer 2

Solution possible:

1. scan une fois pour compter le nombre de lignes
2. décider du numéro de ligne pour choisir au hasard
3. scan à nouveau, choisissez la ligne

Answer 3

En pseudo- code:

use List::Util qw[shuffle]; 

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

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

Ceci est l'implémentation la plus triviale, mais vous devez d'abord lire tout le fichier, ce qui nécessite que vous ayez suffisamment de mémoire disponible.

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

Cela prend un seul argument de ligne de commande, qui est le numéro de la ligne que vous voulez, N. Les premières lignes N sont tenues, comme vous pourriez ne pas voir plus. Par la suite, vous décidez au hasard de prendre la ligne suivante. Et si vous le faites, vous décidez aléatoirement quelle ligne dans la liste-de-N actuelle écraser.

#!/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

Voici un code Perl détaillé qui devrait fonctionner avec des fichiers volumineux.

Le cœur de ce code est qu'il ne stocke pas tout le fichier en mémoire, mais stocke uniquement les décalages dans le fichier. Pour obtenir les compensations, utilisez tell. Puis seek aux endroits appropriés pour récupérer les lignes.

Une meilleure spécification du fichier cible et le nombre de lignes à obtenir est laissé comme un exercice pour ceux qui sont moins paresseux que I. Ces problèmes ont été bien résolus.

#!/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

Vous n'avez pas besoin de connaître le numéro de ligne actuel dans le fichier. Il suffit de chercher à un endroit aléatoire et de garder la ligne suivante. (La ligne courante sera très probablement une ligne partielle.)

Cette approche devrait être très rapide pour les gros fichiers, mais elle ne fonctionnera pas pour STDIN. Heck, aucune sorte de mise en cache du fichier entier en mémoire ne fonctionnera pour STDIN. Donc, si vous devez avoir STDIN, je ne vois pas comment vous pouvez être rapide/bon marché pour les gros fichiers.

Vous pouvez détecter STDIN et passer à une approche en mémoire cache, sinon soyez rapide.

 
#!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 $_; 
}