Este desafío se trata de leer líneas aleatorias de un archivo potencialmente enorme sin leer todo el archivo en la memoria.

Entrada

Un entero ny el nombre de un archivo de texto.

Salida

n líneas del archivo de texto elegidas uniformemente al azar sin reemplazo.

Puede suponer que nestá en el rango 1 al número de líneas en el archivo.

Tenga cuidado al muestrear nnúmeros al azar del rango de que la respuesta que obtiene es uniforme. rand()%nen C no es uniforme, por ejemplo. Cada resultado debe ser igualmente probable.

Reglas y restricciones

Cada línea del archivo de texto tendrá el mismo número de caracteres y no tendrá más de 80.

Su código no debe leer ninguno de los contenidos del archivo de texto, excepto:

• Esas líneas que emite.
• La primera línea para calcular cuántos caracteres por línea hay en el archivo de texto.

Podemos suponer que cada carácter en el archivo de texto toma exactamente un byte.

Se supone que los separadores de línea tienen 1 byte de longitud. Las soluciones pueden usar separadores de línea larga de 2 bytes solo si especifican esta necesidad. También puede suponer que la última línea termina con un separador de línea.

Su respuesta debe ser un programa completo, pero puede especificar la entrada de cualquier manera que sea conveniente.

Idiomas y bibliotecas

Puede usar cualquier idioma o biblioteca que desee.

Notas

Había una preocupación sobre el cálculo del número de líneas en el archivo. Como nimi señala en los comentarios, puede inferir esto a partir del tamaño del archivo y el número de caracteres por línea.

Motivación

En el chat, algunas personas preguntaron si esta es realmente una pregunta de "Hacer X sin Y". Interpreto esto para preguntar si las restricciones son inusualmente artificiales.

La tarea de muestrear aleatoriamente líneas de grandes archivos no es infrecuente y, de hecho, es algo que a veces tengo que hacer. Una forma de hacerlo es en bash:

shuf -n <num-lines>

Sin embargo, esto es muy lento para archivos grandes, ya que se lee en todo el archivo.

Dyalog APL , 63 bytes

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

Solicita el nombre del archivo, luego cuántas líneas aleatorias se desean.

Explicación

⍞Solicitar ingreso de texto (nombre de archivo)
⎕NTIE 0Empate el archivo usando el siguiente número de enlace disponible (-1 en un sistema limpio)
t←Almacene el número de enlace elegido como t
83 80,⍨Anexar [83,80] produciendo [-1,83,80]
⎕NREADLea los primeros 80 bytes del archivo -1 como enteros de 8 bits (código de conversión 83)
10⍳⍨Encuentre el índice del primer número 10 (LF)
l←Almacene la longitud de la línea como l
(⎕NSIZE t)÷Divida el tamaño del archivo -1 con la longitud de la línea
⎕Solicite la entrada numérica (número deseado de líneas )
?X selecciones aleatorias (sin reemplazo) con los primeros números naturales Y
¯1+ Agregue -1 para obtener números de línea de origen 0 *
l×Multiplique por la longitud de la línea para obtener los bytes de inicio
t 82l∘,¨Prepend [-1,82, LineLength] a cada byte de inicio (crea lista de argumentos para ⎕NREAD)
⎕NREAD¨ Lea cada línea como carácter de 8 bits (código de conversión 82)

Ejemplo práctico

El archivo /tmp/records.txt contiene:

Hello
Think
12345
Klaus
Nilad

Haga que el programa RandLines contenga el código anterior literalmente ingresando lo siguiente en la sesión APL:

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

En la sesión APL, escriba RandLinesy presione Entrar.

El sistema mueve el cursor a la siguiente línea, que es una solicitud de longitud 0 para datos de caracteres; entrar /tmp/records.txt.

El sistema ahora emite ⎕:y espera entrada numérica; entrar 4.

El sistema genera cuatro líneas aleatorias.

Vida real

En realidad, es posible que desee dar nombre de archivo y contar como argumentos y recibir el resultado como una tabla. Esto se puede hacer ingresando:

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

Ahora haces que MyLines contenga tres líneas aleatorias con:

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

¿Qué tal devolver solo una línea aleatoria si no se especifica el recuento:

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

Ahora puedes hacer ambas cosas:

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

y (observe la ausencia de argumento izquierdo):

MyLine←RandL'/tmp/records.txt'

Hacer el código legible

Las frases de golf APL son una mala idea. Así es como escribiría en un sistema de producción:

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
}

^{* Podría guardar un byte ejecutándolo en modo de origen 0, que es estándar en algunos sistemas APL: eliminar ¯1+e insertar 1+antes 10.}

Ruby, 104 94 92 90 bytes

El nombre del archivo y el número de líneas se pasan a la línea de comando. Por ejemplo, si el programa es shuffle.rby el nombre del archivo es a.txt, ejecute ruby shuffle.rb a.txt 3tres líneas aleatorias.

-4 bytes desde el descubrimiento de la opensintaxis en Ruby en lugar 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}

Además, aquí hay una solución de función anónima de 85 bytes que toma una cadena y un número como argumentos.

->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 bytes

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

Lee el nombre de archivo yn de stdin.

Cómo funciona:

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

Se necesita mucho tiempo y memoria para ejecutar este programa para archivos con muchas líneas, debido a una shufflefunción horrible e ineficiente .

Editar: me perdí la parte "aleatorio sin reemplazo" (¡gracias @feersum por notarlo!).

PowerShell v2 +, 209 bytes

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}

Toma la entrada $acomo el nombre del archivo y $ncomo el número de líneas. Tenga en cuenta que $adebe ser un nombre de archivo de ruta completa y se supone que es una codificación ANSI.

Luego construimos un nuevo FileStreamobjeto y le decimos que acceda al archivo $acon Openprivilegios.

El forbucle .Read()atraviesa la primera línea hasta que llegamos a un \npersonaje, incrementando nuestro contador de longitud de línea para cada personaje. Luego establecemos $tigual al tamaño del archivo (es decir, cuánto dura la secuencia) dividido por cuántos caracteres por línea (más uno para que cuente el terminador), menos uno (ya que estamos indexados a cero). Luego construimos nuestro buffer $zpara que también sea la longitud de la línea.

La línea final construye una matriz dinámica con el ..operador de rango. ¹ Canalizamos esa matriz Get-Randomcon la -Cposibilidad de $nseleccionar aleatoriamente $nnúmeros de línea sin repetición. Los números de la suerte se canalizan en un bucle con |%{...}. Cada iteración nos lleva .Seeka la ubicación particular, y luego .Readen el valor de una línea de caracteres, almacenados en $z. Lo relanzamos $zcomo un conjunto de caracteres y -joinlo juntamos, dejando la cadena resultante en la tubería y la salida está implícita al final del programa.

Técnicamente deberíamos terminar con una $f.Close()llamada para cerrar el archivo, ¡pero eso cuesta bytes! :pag

Ejemplo

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 

_{¹ Técnicamente, esto significa que solo podemos admitir un máximo de 50,000 líneas, ya que ese es el rango más grande que se puede crear dinámicamente de esta manera. : - / Pero, no podemos simplemente repetir un Get-Randomcomando $nveces, descartando duplicados en cada ciclo, ya que eso no es determinista ...}

Python 3, 146 139 bytes

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^

Entrada: [nombre de archivo] \ n [líneas] \ n

Esta solución robó mucho de @pppery, pero solo es python3.5 y es un programa completo.

Editar: Gracias a @Mego por el rango en línea y la compatibilidad con python3.x. Edit2: Aclaración de dónde está la impresión porque recibí dos comentarios al respecto. (El comentario obviamente no es parte del código o el recuento de bytes).

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

Utiliza 2 bytes para saltos de línea. Cambie el 2 a 1 por 1. Solo lo tengo como 2 porque eso es lo que tenía mi archivo de prueba.

Me metí debajo de la entrada de PHP, pero aún estoy en segundo lugar (actualmente). ¡Maldito seas, Ruby, entrada!

Bash (bueno, coreutils), 100 bytes

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>&-

Explicación

Esto evita leer todo el archivo usando ddpara extraer las partes del archivo que necesitamos sin leerlo por completo, desafortunadamente termina siendo bastante grande con todas las opciones que tenemos que especificar:

ifes el archivo de entrada
bses el tamaño de bloque (aquí lo establecemos en $ncuál es la longitud de la primera línea
skipse establece en los enteros aleatorios extraídos de shufy equivale al ibsvalor omitido skip* ibsbytes)
countel número de ibssecciones de longitud a devolver
status=nonees necesario para eliminar la información que normalmente generadd

Obtenemos la longitud de la línea usando head -1 $2|wc -cy el tamaño del archivo con stat -c%s $2.

Uso

Guardar arriba como file.shy ejecutar usando file.sh n filename.

Tiempos

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

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

vs.

time shuf -n4 test.txt
1204350
3496441
3472713
3985479

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

Tiempos anteriores para un archivo de 68MiB generado usando seq 1000000 9999999 > test.txt.

¡Gracias a @PeterCordes por su punta -1!

Python 3 - 161 160 149 bytes

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

Este código define una función que se llama como f(10,'input.txt')

C # 259 bytes sin duplicados

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());}}

Sin 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 es perezoso. Esto tiene el beneficio adicional de que todas las líneas pueden tener una longitud diferente.

Ejecutarlo sería:

sample.exe a.txt 10000

C # 206 bytes con duplicados

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());}}

Sin 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 bytes)

Mantiene cada línea con la misma probabilidad, use también con tuberías. Sin embargo, no responde la limitación de omisión de la pregunta ...

Uso cat largefile | python randxlines.py 100o python randxlines 100 < largefile(como señaló @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))