Wyzwanie dotyczy odczytu losowych linii z potencjalnie dużego pliku bez wczytywania całego pliku do pamięci.

Wejście

Liczba całkowita ni nazwa pliku tekstowego.

Wynik

n wiersze pliku tekstowego wybrane losowo równomiernie bez zamiany.

Możesz założyć, że nmieści się w zakresie od 1 do liczby linii w pliku.

Zachowaj ostrożność, próbkując nlosowo liczby z zakresu, w którym odpowiedź jest jednorodna. rand()%nna przykład w C nie jest jednolity. Każdy wynik musi być równie prawdopodobny.

Zasady i ograniczenia

Każda linia pliku tekstowego będzie miała tę samą liczbę znaków i nie będzie więcej niż 80.

Twój kod nie może czytać żadnej zawartości pliku tekstowego, z wyjątkiem:

• Linie, które wyprowadza.
• Pierwszy wiersz, aby sprawdzić, ile znaków w wierszu znajduje się w pliku tekstowym.

Możemy założyć, że każdy znak w pliku tekstowym zajmuje dokładnie jeden bajt.

Zakłada się, że separatory linii mają długość 1 bajta. Rozwiązania mogą korzystać z 2-bajtowych separatorów długich linii tylko wtedy, gdy określają to. Możesz również założyć, że ostatnia linia jest zakończona separatorem linii.

Twoja odpowiedź powinna być kompletnym programem, ale możesz podać dane wejściowe w dowolny dogodny sposób.

Języki i biblioteki

Możesz użyć dowolnego języka lub biblioteki.

Notatki

Wystąpił problem z obliczeniem liczby linii w pliku. Jak oni wskazują w komentarzach, możesz wywnioskować to na podstawie rozmiaru pliku i liczby znaków w wierszu.

Motywacja

Na czacie niektórzy pytali, czy to naprawdę pytanie „Wykonaj X bez Y”. Tłumaczę to, aby zapytać, czy ograniczenia są niezwykle sztuczne.

Zadanie losowego próbkowania linii z dużych plików nie jest rzadkie i w rzeczywistości muszę je czasem wykonać. Jednym ze sposobów na to jest bash:

shuf -n <num-lines>

Jest to jednak bardzo wolne w przypadku dużych plików, ponieważ odczytuje się w całym pliku.

Dyalog APL , 63 bajty

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

Monituje o nazwę pliku, a następnie o liczbę pożądanych linii losowych.

Wyjaśnienie

⍞Monituj o wprowadzenie tekstu (nazwa pliku)
⎕NTIE 0Przywiąż plik, używając następnego dostępnego numeru remisu (-1 w czystym systemie)
t←Zapisz wybrany numer remisu jako t
83 80,⍨Dołącz [83,80], uzyskując [-1,83,80]
⎕NREADPrzeczytaj pierwsze 80 bajtów pliku -1 jako liczby całkowite 8-bitowe (kod konwersji 83)
10⍳⍨Znajdź indeks pierwszej liczby 10 (LF)
l←Zapisz długość linii jako l
(⎕NSIZE t)÷Podziel rozmiar pliku -1 za pomocą długości linii
⎕Monit o wprowadzenie danych liczbowych (żądana liczba linii )
?X losowych wyborów (bez zamiany) pierwszych Y liczb naturalnych Y
¯1+Dodaj -1, aby uzyskać numery linii 0-początkowe *
l×Pomnóż przez długość linii, aby uzyskać bajty początkowe
t 82l∘,¨Przyłóż [-1,82, Długość linii] do każdego bajtu początkowego (tworzy lista argumentów za ⎕NREAD)
⎕NREAD¨ Czytaj każdy wiersz jako znak 8-bitowy (kod konwersji 82)

Praktyczny przykład

Plik /tmp/records.txt zawiera:

Hello
Think
12345
Klaus
Nilad

Spraw, aby program RandLines zawierał powyższy kod dosłownie, wprowadzając następujące dane do sesji APL:

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

W typie sesji APL RandLinesnaciśnij klawisz Enter.

System przesuwa kursor do następnego wiersza, który jest pytaniem o długość 0 dla danych znakowych; wchodzić /tmp/records.txt.

System wysyła teraz dane wyjściowe ⎕:i oczekuje na wprowadzenie numeryczne; wchodzić 4.

System generuje cztery losowe linie.

Prawdziwe życie

W rzeczywistości możesz podać nazwę pliku i policzyć jako argumenty, a wynik otrzymać w postaci tabeli. Można to zrobić, wprowadzając:

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

Teraz sprawisz, że MyLines zawiera trzy losowe linie z:

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

A może zwrócisz tylko jedną losową linię, jeśli nie określono liczby:

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

Teraz możesz zrobić oba:

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

oraz (zauważ brak lewego argumentu):

MyLine←RandL'/tmp/records.txt'

Czytanie kodu

Jednoliniowe golfa APL to zły pomysł. Oto jak napisałbym w systemie produkcyjnym:

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
}

^{* Mogę zapisać bajt uruchamiając w trybie 0 pochodzenia, co jest standardem w niektórych systemach APL: Wyjmij ¯1+i włóż 1+wcześniej 10.}

Rubin, 104 94 92 90 bajtów

Nazwa pliku i liczba wierszy są przekazywane do wiersza poleceń. Na przykład, jeśli program ma shuffle.rbnazwę pliku a.txt, uruchomruby shuffle.rb a.txt 3 trzy losowe linie.

-4 bajty od odkrycia openskładni w Rubim zamiastFile.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}

Oto 85-bajtowe rozwiązanie funkcji anonimowej, które jako argument przyjmuje ciąg i liczbę.

->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 bajtów

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

Odczytuje nazwę pliku in ze standardowego wejścia.

Jak to działa:

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

Uruchomienie tego programu w przypadku plików z wieloma wierszami zajmuje dużo czasu i pamięci z powodu okropnej nieefektywności shuffle funkcji.

Edycja: Brakowało mi części „losowo bez wymiany” (dziękuję @feersum za zauważenie!).

PowerShell v2 +, 209 bajtów

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}

Pobiera dane wejściowe $ajako nazwę pliku i $nliczbę wierszy. Zauważ, że$a musi to być pełna ścieżka pliku i zakłada się, że jest to kodowanie ANSI.

Następnie konstruujemy nowy FileStreamobiekt i mówimy mu, aby uzyskał dostęp do pliku za $apomocąOpen uprawnieniami.

forPętla .Read()s przez pierwszą linię, aż trafiliśmy na \ncharakter, zwiększając nasz licznik linia długości każdego znaku. Następnie ustawiamy $trówny rozmiar pliku (tj. Długość strumienia) podzielony przez liczbę znaków w wierszu (plus jeden, więc zlicza terminator), minus jeden (ponieważ mamy indeksowane zero). Następnie budujemy nasz bufor$z aby był również długością linii.

Ostatnia linia konstruuje tablicę dynamiczną z ..operatorem zakresu. ¹ rura takim, że matryca do Get-Randomz -Count z $nlosowo wybierać $nnumery linii bez powtarzania. Szczęśliwe liczby są połączone w pętlę z |%{...}. Każdą iterację przechodzimy .Seekdo określonej lokalizacji, a następnie .Readw postaci znaków zapisanych w linii $z. Przerzucamy ponownie $zjako tablicę -joinznaków i razem, pozostawiając wynikowy ciąg w potoku, a dane wyjściowe są niejawne na końcu programu.

Technicznie powinniśmy zakończyć $f.Close()wezwaniem do zamknięcia pliku, ale to kosztuje bajty! : p

Przykład

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 

_{¹ Technicznie oznacza to, że możemy obsłużyć maksymalnie 50 000 linii, ponieważ jest to największy zakres, który można dynamicznie utworzyć w ten sposób. : - / Ale nie możemy po prostu zapętlić czasów Get-Randompoleceń $n, odrzucając duplikaty każdej pętli, ponieważ nie jest to deterministyczne ...}

Python 3, 146 139 bajtów

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^

Dane wejściowe: [nazwa pliku] \ n [wiersze] \ n

To rozwiązanie mocno ukradło z @pppery, ale jest tylko python3.5 i jest kompletnym programem.

Edycja: Dzięki @Mego za zakres wbudowany i kompatybilność z python3.x. Edycja2: Wyjaśnienie, gdzie jest wydruk, ponieważ otrzymałem dwa komentarze na jego temat. (Komentarz oczywiście nie jest częścią kodu ani liczby bajtów).

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

Wykorzystuje 2 bajty do podziału linii. Zmień 2 na 1 dla 1. Mam go tylko jako 2, ponieważ taki był mój plik testowy.

Znalazłem się pod wpisem PHP, ale nadal 2 miejsce (obecnie). Przeklnij, Ruby, wejdź!

Bash (cóż, coreutils), 100 bajtów

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

Wyjaśnienie

Pozwala to uniknąć odczytu całego pliku przy użyciu dd do wyodrębnienia potrzebnych fragmentów pliku bez odczytu pliku, niestety kończy się dość duży ze wszystkimi opcjami, które musimy określić:

ifto plik wejściowy
bsto rozmiar bloku (tutaj ustawiamy, do $nktórego jest długość pierwszego wiersza
skipustawiana na losowe liczby całkowite wyodrębnione z shufi jest równa ibswartości pomijającej skip* ibsbajtów
countliczbę ibsodcinków długości do zwrócenia
status=none jest potrzebna do usunięcia informacje zwykle wysyłane przezdd

Otrzymujemy długość linii za pomocą head -1 $2|wc -ci rozmiar pliku za pomocą stat -c%s $2.

Stosowanie

Zapisz powyżej jako file.shi uruchom przy użyciu file.sh n filename.

Czasy

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

Razy powyżej dla pliku 68 MB wygenerowanego przy użyciu seq 1000000 9999999 > test.txt.

Dzięki @PeterCordes za jego wskazówkę -1!

Python 3 - 161 160 149 bajtów

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

Ten kod definiuje funkcję, która jest wywoływana jak f(10,'input.txt')

C # 259 bajtów bez duplikatów

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

Nie golfił

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 jest leniwy. Ma to dodatkową zaletę, że wszystkie linie mogą mieć różną długość.

Uruchomienie byłoby:

sample.exe a.txt 10000

C # 206 bajtów z duplikatami

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

Nie golfił

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 bajtów)

Utrzymuje każdą linię z jednakowym prawdopodobieństwem, użyj również z rurami. Nie odpowiada to jednak ograniczeniu pytania z wyprzedzeniem ...

Zastosowanie cat largefile | python randxlines.py 100lub python randxlines 100 < largefile(jak wskazano @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))