Leia n linhas aleatórias de um arquivo potencialmente grande

16

Esse desafio é ler linhas aleatórias de um arquivo potencialmente enorme sem ler o arquivo inteiro na memória.

Entrada

Um número inteiro ne o nome de um arquivo de texto.

Resultado

n linhas do arquivo de texto escolhidas uniformemente aleatoriamente sem substituição.

Você pode assumir que nestá no intervalo de 1 ao número de linhas no arquivo.

Tenha cuidado ao amostrar nnúmeros aleatoriamente no intervalo em que a resposta que você obtém é uniforme. rand()%nem C não é uniforme, por exemplo. Todo resultado deve ser igualmente provável.

Regras e restrições

Cada linha do arquivo de texto terá o mesmo número de caracteres e não terá mais que 80.

Seu código não deve ler nenhum conteúdo do arquivo de texto, exceto:

  • Aquelas linhas que produz.
  • A primeira linha a descobrir quantos caracteres por linha existem no arquivo de texto.

Podemos assumir que cada caractere no arquivo de texto ocupa exatamente um byte.

Supõe-se que os separadores de linha tenham 1 byte de comprimento. As soluções podem usar separadores de linha longa de 2 bytes apenas se especificarem essa necessidade. Você também pode assumir que a última linha é encerrada por um separador de linhas.

Sua resposta deve ser um programa completo, mas você pode especificar a entrada da maneira que for mais conveniente.

Línguas e bibliotecas

Você pode usar qualquer idioma ou biblioteca que desejar.

Notas

Havia uma preocupação em calcular o número de linhas no arquivo. Como nimi aponta nos comentários, você pode inferir isso do tamanho do arquivo e do número de caracteres por linha.

Motivação

No bate-papo, algumas pessoas perguntaram se essa é realmente uma pergunta "Faça X sem Y". Interpreto isso para perguntar se as restrições são extraordinariamente artificiais.

A tarefa de amostragem aleatória de linhas de arquivos enormes não é incomum e é de fato uma que às vezes tenho que fazer. Uma maneira de fazer isso é no bash:

shuf -n <num-lines>

No entanto, isso é muito lento para arquivos grandes, pois ele lê o arquivo inteiro.


fonte
Por que o voto negativo?
3
Isso é trivial em idiomas como o C fseek, e impossível em outros. Além disso, e se nfor maior que o número de linhas no arquivo?
Mego 5/05
4
@Mego: em relação ao seu ponto b): você pode calcular o número de linhas dividindo o tamanho do arquivo pelo comprimento de uma linha.
N
8
Fazer X sem Y é um aviso que começa com "Isso nem sempre é ruim". O principal problema são restrições artificiais como "não use +", o que dá vantagem aos idiomas que possuem um sum(). Não ler um arquivo na memória é uma restrição clara e consistente que não é de forma alguma arbitrária. Ele pode ser testado com um arquivo maior que a memória, que não pode ser contornado por diferenças de idioma. Também tem aplicativos do mundo real (embora isso não seja necessário para um golfe ...).
Trichoplax #
1
Parece que este é realmente um código de complexidade restrito, em que o uso da memória é limitado, apesar de arquivos potencialmente grandes. Não se trata de não ter certas coisas no seu código, mas uma limitação de como o código pode agir.
Xnor

Respostas:

5

Dyalog APL , 63 bytes

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

Solicita o nome do arquivo e, em seguida, quantas linhas aleatórias são desejadas.

Explicação

Solicitar entrada de texto (nome do arquivo)
⎕NTIE 0Amarre o arquivo usando o próximo número de empate disponível (-1 em um sistema limpo)
t←Armazene o número de empate escolhido como t
83 80,⍨Anexar [83,80] produzindo [-1,83,80]
⎕NREADLeia os primeiros 80 bytes do arquivo -1 como números inteiros de 8 bits (código de conversão 83)
10⍳⍨Encontre o índice do primeiro número 10 (LF)
l←Armazene o comprimento da linha como l
(⎕NSIZE t)÷Divida o tamanho do arquivo -1 com o comprimento da linha
Solicitar entrada numérica (número de linhas desejado) )
? X seleções aleatórias (sem substituição) dos primeiros números naturais Y
¯1+Adicione -1 para obter números de linha com origem 0 *
Multiplique pelo comprimento da linha para obter os bytes iniciais
t 82l∘,¨Prefixo [-1,82, LineLength] a cada byte inicial (cria lista de argumentos para ⎕NREAD)
⎕NREAD¨ Leia cada linha como caractere de 8 bits (código de conversão 82)

Exemplo prático

O arquivo /tmp/records.txt contém:

Hello
Think
12345
Klaus
Nilad

Faça com que o programa RandLines contenha o código acima literalmente, inserindo o seguinte na sessão da APL:

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

Na sessão APL, digite RandLinese pressione Enter.

O sistema move o cursor para a próxima linha, que é um prompt de comprimento 0 para dados de caracteres; entrar/tmp/records.txt .

O sistema agora produz ⎕: e aguarda entrada numérica; entra 4.

O sistema gera quatro linhas aleatórias.

Vida real

Na realidade, você pode querer dar o nome do arquivo e contar como argumentos e receber o resultado como uma tabela. Isso pode ser feito digitando:

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

Agora você cria MyLines que contém três linhas aleatórias com:

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

Que tal retornar apenas uma única linha aleatória se count não for especificado:

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

Agora você pode fazer as duas coisas:

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

e (observe a ausência de argumento à esquerda):

MyLine←RandL'/tmp/records.txt'

Tornando o código legível

APLs de golfe são uma má idéia. Aqui está como eu escreveria em um sistema de produção:

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
}

* Eu poderia salvar um byte executando no modo de origem 0, o que é padrão em alguns sistemas APL: remova ¯1+e insira 1+antes 10.

Adão
fonte
Ahh .. APL :) Existe alguma maneira de testar esse código no linux?
@Lembik Claro, esse código é multiplataforma. Faça o download de dyalog.com
Adám
Como não leio APL, você poderia explicar o código? As partes complicadas são amostras de linhas sem substituição e saltam diretamente para o lugar certo no arquivo para ler as linhas.
@Lembik Essa parte é fácil. O argumento de NREAD é TieNumber ConversionCode BytesToRead [StartByte]. Ele lê apenas os bytes necessários. O resto é apenas descobrir o que ler.
Adám
@Embembik Estou curioso para saber por que minha resposta não ganhou a recompensa.
Adám 14/05
7

Ruby, 104 94 92 90 bytes

O nome do arquivo e o número de linhas são passados ​​para a linha de comando. Por exemplo, se o programa é shuffle.rbe o nome do arquivo é a.txt, execute ruby shuffle.rb a.txt 3por três linhas aleatórias.

-4 bytes da descoberta da opensintaxe no Ruby em vez 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}

Além disso, aqui está uma solução de função anônima de 85 bytes que usa uma string e um 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}}
Value Ink
fonte
Abaixo de 100 bytes! Talvez Ruby seja a melhor linguagem de golfe, afinal. 'Amostra' evita repetições?
@Lembik ruby-doc.org/core-2.2.0/Array.html#method-i-sample Evita repetições. Não me diga ... eu deveria ter repetições?
Value Ink
Sem você é perfeito :)
Você pode salvar bytes lendo no stdin? ruby shuffle.rb 3 < a.txtdá-lhe um stdin procurável. IDK Ruby, no entanto.
Peter Cordes
1
@ PeterCordes Isso faz sentido, mas como mencionado, o ponto de falha é que Ruby não consegue ler o tamanho do arquivo stdin, por isso não deu certo.
Value Ink
5

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

Lê o nome do arquivo en do stdin.

Como 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

Leva muito tempo e memória para executar este programa para arquivos com muitas linhas, devido a uma shufflefunção ineficiente horrível .

Edit: Eu perdi a parte "aleatória sem substituição" (obrigado @feersum por perceber!).

nimi
fonte
Haskell rochas :)
1
Como evitar escolher uma linha que já foi escolhida?
feersum
@feersum: oh, eu perdi essa parte. Fixo.
nimi
Vejo stackoverflow.com/questions/13779630/… é um pouco detalhado!
1
Talvez deva haver um desafio separado na amostragem sem substituição em espaço pequeno.
3

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}

Aceita entrada $acomo o nome do arquivo e $ncomo o número de linhas. Observe que $adeve ser um nome de arquivo de caminho completo e considerado como codificação ANSI.

Em seguida, construímos um novo FileStreamobjeto e pedimos que ele acesse o arquivo $acom Openprivilégio.

O forloop .Read()percorre a primeira linha até atingirmos um \ncaractere, incrementando nosso contador de comprimento de linha para cada caractere. Em seguida, definimos $tigual ao tamanho do arquivo (ou seja, quanto tempo o fluxo é) dividido por quantos caracteres por linha (mais um para contar o terminador), menos um (já que somos indexados a zero). Em seguida, construímos nosso buffer$z para também ter comprimento de linha.

A linha final constrói uma matriz dinâmica com o ..operador range. Um tubo Nós que a matriz Get-Randomcom um -Count de $npara seleccionar aleatoriamente $nnúmeros de linha sem repetição. Os números da sorte são canalizados em um loop com |%{...}. Cada iteração é armazenada em um .Seeklocal específico e, .Readem seguida, no valor de uma linha de caracteres $z. Nós re-convertemos $zcomo um array de caracteres e -joinjuntos, deixando a sequência resultante no pipeline e a saída está implícita no final do programa.

Tecnicamente , devemos terminar com uma $f.Close()chamada para fechar o arquivo, mas isso custa bytes! : p

Exemplo

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 

1 Tecnicamente, isso significa que podemos suportar apenas um máximo de 50.000 linhas, pois esse é o maior intervalo que pode ser criado dinamicamente dessa maneira. : - / Mas não podemos simplesmente repetir um Get-Randomcomando $nvezes, descartando duplicatas de cada loop, pois isso não é determinístico ...

AdmBorkBork
fonte
2

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: [nome do arquivo] \ n [linhas] \ n

Essa solução roubou muito do @pppery, mas é apenas python3.5 e é um programa completo.

Edit: Obrigado ao @Mego pelo intervalo inline e compatibilidade com python3.x. Edit2: Esclarecimento onde está a impressão, porque eu tenho dois comentários sobre isso. (Obviamente, o comentário não faz parte do código ou da contagem de bytes.)

Alexander Nigl
fonte
Obrigado! Qual parte é apenas python 3.5?
2
r=range(f.seek(0,2)//l)funcionará, eliminando 3 bytes e eliminando a necessidade de 3,5. Melhor ainda, reduza mais 3 bytes, inserindo a rangechamada na samplechamada. Além disso, este não é um programa completo - você precisa realmente imprimir a lista.
Mego
@Lembik: Era 3,5 apenas porque eu usei r=[*range(f.seek(0,2)//l)]porque eu pensei que não poderia sampleum gerador. Acontece que eu poderia. @Mega: É completo porque ele imprime uma cada linha dentro da compreensão de listaprint(f.read(l))
Alexander Nigl
Você precisa de uma declaração impressa.
a impressão está dentro da compreensão da lista.
Alexander Nigl
2

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

Usa 2 bytes para quebras de linha. Mude o 2 para 1 para 1. Eu só o tenho como 2 porque é isso que meu arquivo de teste tinha.

Entrei na entrada do PHP, mas ainda estou em segundo lugar (atualmente). Maldito seja, entrada Ruby!

Blab
fonte
1
Lua foi a primeira linguagem de programação que aprendi e, mesmo com tudo o que aprendi desde então, ainda é a minha favorita. É tão versátil por sua facilidade de escrever.
Blab
2

Bash (bem, 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>&-

Explicação

Isso evita a leitura de todo o arquivo usando ddpara extrair as partes do arquivo que precisamos sem a leitura completa do arquivo; infelizmente, ele acaba sendo muito grande com todas as opções que precisamos especificar:

ifé o arquivo de entrada
bsé o tamanho do bloco (aqui o definimos como $no comprimento da primeira linha
skipé definido como os números inteiros aleatórios extraídos deshuf e equivale ao ibsvalor pulando skip* ibsbytes)
counto número de ibsseções de comprimento a serem retornadas
status=noneé necessário para remover a informação normalmente emitida pordd

Nós obtemos o comprimento da linha usando head -1 $2|wc -ce o tamanho do arquivo com stat -c%s $2.

Uso

Salve acima como file.she execute usando file.sh n filename.

Horários

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

Tempos acima para um arquivo de 68MiB gerado usando seq 1000000 9999999 > test.txt.

Obrigado a @PeterCordes por sua dica -1!

Dom Hastings
fonte
1
Eu sempre amo uma resposta do bash, mas você pode explicar como isso não lê o arquivo inteiro?
2
@Lembik adicionou uma explicação!
Dom Hastings
1
Você pode, em bs=vez de ibs=, já que a configuração obstambém é boa. Eu acho que você não pode substituir if=$2por isso <$2, pois essa ainda xargsé a linha de comando. \<$2também não funciona (xargs usa exec diretamente, sem um shell).
Peter Cordes
Espero que isso não seja demais, mas eu meio que adoro essa resposta :) Apenas testei com um arquivo de 1 GB.
1
re: redirecionando o stderr para o stdin: Você também pode fechar o stderr com 2>&-, para que não haja perigo da saída ir a lugar algum (por exemplo, se o stdin for um descritor de arquivo de leitura / gravação). Ele funciona com o GNU dd: Ele ainda o produz stdoutantes de tentar e deixar de escrever stderr.
Peter Cordes
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 uma função que é chamada como f(10,'input.txt')

pppery
fonte
1
O desafio requer um programa completo, portanto, receio que uma definição de função não seja suficiente.
nimi
Para economizar um byte, remova o espaço entre import e *.
Mriklojn
1
@nimi Exigindo um programa completo para este desafio parece ser arbitrariamente substituindo as regras de formatação de código padrão
pppery
@ppperry: sim, talvez, mas é assim que as coisas são.
nimi
Para obter o tamanho do arquivo, você pode f.seek (0,2) , que torna obsoletos os e os.stat de importação.
Alexander Nigl
1

C # 259 bytes sem duplicatas

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

Ungolfed

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

O File.ReadLines está lento. Isso tem o benefício adicional de que todas as linhas podem ter comprimentos diferentes.

Executá-lo seria:

sample.exe a.txt 10000

C # 206 bytes com duplicatas

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

Ungolfed

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());
    }
}
Master117
fonte
Eu não sigo completamente sua solução. Se todas as linhas tiverem comprimentos diferentes, a tarefa será impossível. Além disso, como você está amostrando linhas aleatoriamente sem substituição exatamente? Peço desculpas meu C # não é bom o suficiente.
@Lembik Você está certo, eu não pensei em duplicatas. E posso contar a quantidade de linhas e extrair linhas por número de roupa, e é por isso que as linhas podem ter um comprimento variável.
Master117
Mas você precisa pular para um local no arquivo apenas sabendo o número da linha, não é? Você não pode dizer onde está, a menos que todas as linhas tenham o mesmo comprimento.
@Lembik File.ReadLines ("pathToFile") cria uma enumeração lenta em todas as linhas do arquivo, File.ReadLines ("pathToFile"). ElementAt (19) retorna a 19ª linha do arquivo. Como um mapa de todos os Linestarts.
Master117
Eu não acho que a enumeração Lazy salte (ou busque) no arquivo infelizmente. Portanto, ele não se encaixa nas regras atualmente.
1

Python (141 bytes)

Mantém cada linha com igual probabilidade, use também com tubos. Porém, ele não responde à limitação da pergunta à frente ...

Uso cat largefile | python randxlines.py 100ou python randxlines 100 < largefile(como @petercordes apontou)

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))
topkara
fonte
3
O ponto principal desta questão é que você deve procurar no fluxo de entrada. Você provavelmente deve dizer que essa é a parte das restrições da pergunta que está ignorando (embora o exemplo de uso de leitura em um tubo deixe isso bem claro). Ler de stdin com python ./randxlines.py 100 < largefileseria bom para uma resposta adequada, no entanto: nesse caso stdin, será procurável.
Peter Cordes