Ce défi consiste à lire des lignes aléatoires à partir d'un fichier potentiellement énorme sans lire l'intégralité du fichier en mémoire.

Contribution

Un entier net le nom d'un fichier texte.

Production

n lignes du fichier texte choisies uniformément au hasard sans remplacement.

Vous pouvez supposer qu'il nest compris entre 1 et le nombre de lignes du fichier.

Soyez prudent lorsque vous échantillonnez des nnombres au hasard dans la plage où la réponse que vous obtenez est uniforme. rand()%nen C n'est pas uniforme par exemple. Chaque résultat doit être également probable.

Règles et restrictions

Chaque ligne du fichier texte aura le même nombre de caractères et ce ne sera pas plus de 80.

Votre code ne doit pas lire le contenu du fichier texte, sauf:

• Ces lignes qu'il produit.
• La première ligne pour déterminer le nombre de caractères par ligne dans le fichier texte.

Nous pouvons supposer que chaque caractère du fichier texte prend exactement un octet.

Les séparateurs de ligne sont supposés faire 1 octet de long. Les solutions peuvent utiliser des séparateurs de ligne de 2 octets uniquement si elles spécifient ce besoin. Vous pouvez également supposer que la dernière ligne se termine par un séparateur de ligne.

Votre réponse doit être un programme complet mais vous pouvez spécifier l'entrée de la manière qui vous convient.

Langues et bibliothèques

Vous pouvez utiliser n'importe quelle langue ou bibliothèque que vous aimez.

Remarques

Il y avait une préoccupation au sujet du calcul du nombre de lignes dans le fichier. Comme le souligne nimi dans les commentaires, vous pouvez en déduire la taille du fichier et le nombre de caractères par ligne.

Motivation

Dans le chat, certaines personnes ont demandé s'il s'agissait vraiment d'une question "Do X without Y". J'interprète cela pour demander si les restrictions sont inhabituellement artificielles.

La tâche d'échantillonnage aléatoire de lignes à partir de fichiers volumineux n'est pas rare et en fait, je dois parfois le faire. Une façon de le faire est en bash:

shuf -n <num-lines>

Ceci est cependant très lent pour les fichiers volumineux car il lit dans tout le fichier.

Dyalog APL , 63 octets

⎕NREAD¨t 82l∘,¨lׯ1+⎕?(⎕NSIZE t)÷l←10⍳⍨⎕NREAD 83 80,⍨t←⍞⎕NTIE 0

Demande le nom du fichier, puis le nombre de lignes aléatoires souhaitées.

Explication

⍞Demander la saisie de texte (nom de fichier)
⎕NTIE 0Lier le fichier en utilisant le prochain numéro de lien disponible (-1 sur un système propre)
t←Stocker le numéro de lien choisi sous la forme t
83 80,⍨Ajouter [83,80] donnant [-1,83,80]
⎕NREADLire les 80 premiers octets du fichier -1 sous forme d'entiers 8 bits (code de conversion 83)
10⍳⍨Trouver l'index du premier nombre 10 (LF)
l←Stocker la longueur de ligne sous l
(⎕NSIZE t)÷Diviser la taille du fichier -1 avec la longueur de ligne
⎕Demander une entrée numérique (nombre de lignes souhaité )
?X sélections aléatoires (sans remplacement) sur les premiers Y nombres naturels
¯1+Ajoutez -1 pour obtenir des numéros de ligne d'origine 0 *
l×Multipliez par la longueur de ligne pour obtenir les octets de début
t 82l∘,¨Ajoutez [-1,82, LineLength] à chaque octet de début (crée liste des arguments pour ⎕NREAD)
⎕NREAD¨ Lire chaque ligne sous forme de caractère 8 bits (code de conversion 82)

Exemple pratique

Le fichier /tmp/records.txt contient:

Hello
Think
12345
Klaus
Nilad

Faites en sorte que le programme RandLines contienne le code ci-dessus textuellement en entrant ce qui suit dans la session APL:

∇RandLines
⎕NREAD¨t 82l∘,¨lׯ1+⎕?(⎕NSIZE t)÷l←10⍳⍨⎕NREAD 83 80,⍨t←⍞⎕NTIE 0
∇

Dans le type de session APL RandLineset appuyez sur Entrée.

Le système déplace le curseur sur la ligne suivante, qui est une invite de longueur 0 pour les données de caractères; entrez /tmp/records.txt.

Le système sort maintenant ⎕:et attend une entrée numérique; entrez 4.

Le système génère quatre lignes aléatoires.

Vrai vie

En réalité, vous voudrez peut-être donner un nom de fichier et compter comme arguments et recevoir le résultat sous forme de tableau. Cela peut être fait en entrant:

RandLs←{↑⎕NREAD¨t 82l∘,¨lׯ1+⍺?(⎕NSIZE t)÷l←10⍳⍨⎕NREAD 83 80,⍨t←⍵⎕NTIE 0}

Maintenant, vous faites MyLines contenir trois lignes aléatoires avec:

MyLines←3 RandLs'/tmp/records.txt'

Que diriez-vous de renvoyer une seule ligne aléatoire si le nombre n'est pas spécifié:

RandL←{⍺←1 ⋄ ↑⎕NREAD¨t 82l∘,¨lׯ1+⍺?(⎕NSIZE t)÷l←10⍳⍨⎕NREAD 83 80,⍨t←⍵⎕NTIE 0}

Maintenant, vous pouvez faire les deux:

MyLines←2 RandL'/tmp/records.txt'

et (notez l'absence d'argument de gauche):

MyLine←RandL'/tmp/records.txt'

Rendre le code lisible

Les monoplaces APL au golf sont une mauvaise idée. Voici comment j'écrirais dans un système de production:

RandL←{ ⍝ Read X random lines from file Y without reading entire file
    ⍺←1 ⍝ default count
    tie←⍵⎕NTIE 0 ⍝ tie file
    length←10⍳⍨⎕NREAD 83 80,⍨tie ⍝ find first NL
    size←⎕NSIZE tie ⍝ total file length
    starts←lengthׯ1+⍺?size÷length ⍝ beginning of each line
    ↑⎕NREAD¨tie 82length∘,¨starts ⍝ read each line as character and convert list to table
}

^{* Je pourrais enregistrer un octet en exécutant en mode 0 d'origine, ce qui est standard sur certains systèmes APL: supprimez ¯1+et insérez 1+avant 10.}

Rubis, 104 94 92 90 octets

Le nom de fichier et le nombre de lignes sont passés dans la ligne de commande. Par exemple, si le programme est shuffle.rbet le nom de fichier est a.txt, exécutez ruby shuffle.rb a.txt 3pour trois lignes aléatoires.

-4 octets de découverte du open syntaxe dans Ruby au lieu deFile.new

f=open$*[0]
puts [*0..f.size/n=f.gets.size+1].sample($*[1].to_i).map{|e|f.seek n*e;f.gets}

En outre, voici une solution de fonction anonyme de 85 octets qui prend une chaîne et un nombre comme arguments.

->f,l{f=open f;puts [*0..f.size/n=f.gets.size+1].sample(l).map{|e|f.seek n*e;f.gets}}

Haskell, 240 224 236 octets

import Test.QuickCheck
import System.IO
g=hGetLine
main=do;f<-getLine;n<-readLn;h<-openFile f ReadMode;l<-(\x->1+sum[1|_<-x])<$>g h;s<-hFileSize h;generate(shuffle[0..div s l-1])>>=mapM(\p->hSeek h(toEnum 0)(l*p)>>g h>>=putStrLn).take n

Lit le nom de fichier et n depuis stdin.

Comment ça fonctionne:

main=do
  f<-getLine                   -- read file name from stdin
  n<-readLn                    -- read n from stdin
  h<-openFile f ReadMode       -- open the file
  l<-(\x->1+sum[1|_<-x])<$>g h -- read first line and bind l to it's length +1
                               -- sum[1|_<-x] is a custom length function
                               -- because of type restrictions, otherwise I'd have
                               -- to use "toInteger.length"
  s<-hFileSize h               -- get file size
  generate(shuffle[0..div s l-1])>>=
                               -- shuffle all possible line numbers 
  mapM (\->p  ...  ).take n    -- for each of the first n shuffled line numbers 
     hSeek h(toEnum 0).(l*p)>> -- jump to that line ("toEnum 0" is short for "AbsoluteSeek")
     g h>>=                    -- read a line from current position
     putStrLn                  -- and print

Il faut beaucoup de temps et de mémoire pour exécuter ce programme pour les fichiers avec de nombreuses lignes, en raison d'une horrible shufflefonction inefficace .

Edit: j'ai raté la partie "aléatoire sans remplacement" (merci @feersum pour l'avoir remarqué!).

PowerShell v2 +, 209 octets

param($a,$n)
$f=New-Object System.IO.FileStream $a,"Open"
for(;$f.ReadByte()-ne10){$l++}
$t=$f.Length/++$l-1
[byte[]]$z=,0*$l
0..$t|Get-Random -c $n|%{$a=$f.Seek($l*$_,0);$a=$f.Read($z,0,$l-1);-join[char[]]$z}

Prend l'entrée $acomme nom de fichier et $ncomme nombre de lignes. Notez qu'il $adoit s'agir d'un nom de fichier à chemin complet et supposé être un codage ANSI.

Nous construisons ensuite un nouvel FileStreamobjet et lui demandons d'accéder au fichier $aavec Openprivilège.

La forboucle .Read()parcourt la première ligne jusqu'à ce que nous touchions un \ncaractère, en incrémentant notre compteur de longueur de ligne à chaque caractère. Nous avons ensuite mis$t la taille du fichier (c'est-à-dire la durée du flux) divisée par le nombre de caractères par ligne (plus un pour qu'il compte le terminateur), moins un (car nous sommes indexés zéro). Nous construisons ensuite notre tampon $zpour qu'il soit également de longueur de ligne.

La dernière ligne construit un tableau dynamique avec l' ..opérateur de plage. ¹ Nous redirigeons ce tableau vers Get-Randomavec un -Cnombre de $npour sélectionner aléatoirement des $nnuméros de ligne sans répétition. Les numéros porte-bonheur sont placés dans une boucle avec |%{...}. Chaque itération nous .Seekà l'emplacement particulier, puis .Readdans la valeur d'une ligne de caractères, stockés dans $z. Nous avons re-casté $zcomme un tableau de caractères et -joinensemble, laissant la chaîne résultante sur le pipeline et la sortie est implicite à la fin du programme.

Techniquement, nous devrions terminer par un $f.Close()appel pour fermer le fichier, mais cela coûte des octets! : p

Exemple

a.txt:
a0000000000000000000000000000000000000000000000001
a0000000000000000000000000000000000000000000000002
a0000000000000000000000000000000000000000000000003
a0000000000000000000000000000000000000000000000004
a0000000000000000000000000000000000000000000000005
a0000000000000000000000000000000000000000000000006
a0000000000000000000000000000000000000000000000007
a0000000000000000000000000000000000000000000000008
a0000000000000000000000000000000000000000000000009
a0000000000000000000000000000000000000000000000010

PS C:\Tools\Scripts\golfing> .\read-n-random-lines.ps1 "c:\tools\scripts\golfing\a.txt" 5
a0000000000000000000000000000000000000000000000002 
a0000000000000000000000000000000000000000000000001 
a0000000000000000000000000000000000000000000000004 
a0000000000000000000000000000000000000000000000010 
a0000000000000000000000000000000000000000000000006 

_{¹ Techniquement, cela signifie que nous ne pouvons prendre en charge qu'un maximum de 50 000 lignes, car il s'agit de la plus grande gamme pouvant être créée dynamiquement de cette manière. : - / Mais, nous ne pouvons pas simplement boucler une Get-Randomcommande $nfois, en supprimant les doublons de chaque boucle, car ce n'est pas déterministe ...}

Python 3, 146 139 octets

from random import*
i=input
f=open(i())
l=len(f.readline())
[(f.seek(v*l),print(f.read(l)))for v in sample(range(f.seek(0,2)//l),int(i()))]
#print is here^

Entrée: [nom de fichier] \ n [lignes] \ n

Cette solution a volé lourdement à @pppery mais est uniquement en python3.5 et est un programme complet.

Edit: Merci à @Mego pour la gamme en ligne et la compatibilité python3.x. Edit2: Clarification de l'emplacement de l'impression car j'ai reçu deux commentaires à ce sujet. (Le commentaire ne fait évidemment pas partie du code ni du nombre d'octets.)

Lua, 126 122

r=io.read;f=io.open(r())c=2+f:read():len()for i=1,r()do f:seek("set",c*math.random(0,f:seek("end")/c-1))print(f:read())end

Utilise 2 octets pour les sauts de ligne. Remplacez le 2 par 1 pour 1. Je ne l'ai que 2 car c'est ce que mon fichier de test avait.

Je me suis placé sous l'entrée PHP, mais toujours la 2e place (actuellement). Je vous maudis, entrée Ruby!

Bash (enfin, coreutils), 100 octets

n=`head -1 $2|wc -c`;shuf -i0-$[`stat -c%s $2`/$n] -n$1|xargs -i dd if=$2 bs=$n skip={} count=1 2>&-

Explication

Cela évite de lire le fichier entier en utilisant ddpour extraire les parties du fichier dont nous avons besoin sans lire le fichier entièrement, malheureusement cela finit assez grand avec toutes les options que nous devons spécifier:

ifest le fichier d'entrée
bsest la taille du bloc (ici, nous le définissons à $nquelle est la longueur de la première ligne
skipest définie sur les entiers aléatoires extraits deshuf et équivaut à la ibsvaleur sautant skip* ibsoctets
countle nombre de ibssections de longueur à retourner
status=noneest nécessaire pour supprimer les informations normalement produites pardd

Nous obtenons la longueur de ligne en utilisant head -1 $2|wc -cet la taille du fichier avecstat -c%s $2 .

Usage

Enregistrer ci-dessus sous file.shet exécuter en utilisantfile.sh n filename .

Timings

time ~/randlines.sh 4 test.txt
9412647
4124435
7401105
1132619

real    0m0.125s
user    0m0.035s
sys     0m0.061s

contre.

time shuf -n4 test.txt
1204350
3496441
3472713
3985479

real    0m1.280s
user    0m0.287s
sys     0m0.272s

Temps ci-dessus pour un fichier de 68 Mo généré à l'aide de seq 1000000 9999999 > test.txt .

Merci à @PeterCordes pour son -1 conseil!

Python 3 - 161 160 160 149 octets

from random import*;
def f(n,g):f=open(g);l=len(f.readline());r=list(range(f.seek(0,2)/l));shuffle(r);[(f.seek(v*l),print(f.read(l)))for v in r[:k]]

Ce code définit une fonction qui s'appelle comme f(10,'input.txt')

C # 259 octets sans doublons

class Program{static void Main(string[]a){int c=Convert.ToInt32(a[1]);var h=File.ReadLines(a[0]);HashSet<int>n=new HashSet<int>();while(n.Count<c)n.Add(new Random().Next(0,h.Count()));for(;c>0;c--)Console.WriteLine(h.Skip(n.ElementAt(c-1)).Take(1).First());}}

Non golfé

class Program{static void Main(string[] a)
{
        int c = Convert.ToInt32(a[1]);
        var h = File.ReadLines(a[0]);
        HashSet<int> n = new HashSet<int>();
        while (n.Count < c)
            n.Add(new Random().Next(0, h.Count()));           
        for (; c > 0; c--)
            Console.WriteLine(h.Skip(n.ElementAt(c-1)).Take(1).First());
    }
}

File.ReadLines est paresseux. Cela présente l'avantage supplémentaire que toutes les lignes peuvent avoir une longueur différente.

Le faire fonctionner serait:

sample.exe a.txt 10000

C # 206 octets avec doublons

class Program{static void Main(string[]a){var n=new Random();int c=Convert.ToInt32(a[1]);var h=File.ReadLines(a[0]);for(;c>0;c--)Console.WriteLine(h.Skip((int)(n.NextDouble()*h.Count())).Take(1).First());}}

Non golfé

class Program
{
    static void Main(string[] a)
    {
        Random n = new Random();
        int c = Convert.ToInt32(a[1]);
        var h = File.ReadLines(a[0]);
        for (; c > 0; c--)
            Console.WriteLine(h.Skip((int)(n.NextDouble()*h.Count())).Take(1).First());
    }
}

Python (141 octets)

Conserve chaque ligne avec une probabilité égale, à utiliser également avec des tuyaux. Cependant, cela ne répond pas à la limitation de saut de la question ...

Utilisation cat largefile | python randxlines.py 100ou python randxlines 100 < largefile(comme l'a souligné @petercordes)

import random,sys
N=int(sys.argv[1])
x=['']*N
for c,L in enumerate(sys.stdin):
    t=random.randrange(c+1)
    if(t<N):x[t] = L
print("".join(x))