Bei dieser Herausforderung geht es darum, zufällige Zeilen aus einer potenziell großen Datei zu lesen, ohne die gesamte Datei in den Speicher einzulesen.

Eingang

Eine Ganzzahl nund der Name einer Textdatei.

Ausgabe

n Zeilen der Textdatei werden gleichmäßig und ersatzlos zufällig ausgewählt.

Sie können davon ausgehen, dass nder Wert zwischen 1 und der Anzahl der Zeilen in der Datei liegt.

Seien Sie vorsichtig, wenn Sie nzufällig Zahlen aus dem Bereich entnehmen, in dem die Antwort einheitlich ist. rand()%nin C ist zum Beispiel nicht einheitlich. Jedes Ergebnis muss gleich wahrscheinlich sein.

Regeln und Einschränkungen

Jede Zeile der Textdatei hat die gleiche Anzahl von Zeichen und das sind nicht mehr als 80.

Ihr Code darf keinen Inhalt der Textdatei lesen, außer:

• Diese Zeilen gibt es aus.
• Die erste Zeile, in der ermittelt wird, wie viele Zeichen pro Zeile in der Textdatei enthalten sind.

Wir können davon ausgehen, dass jedes Zeichen in der Textdatei genau ein Byte benötigt.

Zeilentrennzeichen werden mit einer Länge von 1 Byte angenommen. Lösungen dürfen nur dann 2 Byte lange Zeilentrennzeichen verwenden, wenn sie dies erfordern. Sie können auch davon ausgehen, dass die letzte Zeile durch einen Zeilentrenner abgeschlossen wird.

Ihre Antwort sollte ein vollständiges Programm sein, aber Sie können die Eingabe auf jede bequeme Weise festlegen.

Sprachen und Bibliotheken

Sie können eine beliebige Sprache oder Bibliothek verwenden.

Anmerkungen

Es gab Bedenken hinsichtlich der Berechnung der Anzahl der Zeilen in der Datei. Wie nimi in den Kommentaren betont, können Sie dies aus der Dateigröße und der Anzahl der Zeichen pro Zeile ableiten.

Motivation

Im Chat wurden einige Leute gefragt, ob dies wirklich eine "Do X without Y" -Frage ist. Ich interpretiere dies, um zu fragen, ob die Beschränkungen ungewöhnlich künstlich sind.

Das zufällige Abtasten von Zeilen aus riesigen Dateien ist keine Seltenheit und wird von mir manchmal ausgeführt. Eine Möglichkeit, dies zu tun, ist in Bash:

shuf -n <num-lines>

Dies ist jedoch bei großen Dateien sehr langsam, da die gesamte Datei eingelesen wird.

Dyalog APL , 63 Bytes

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

Fordert zur Eingabe des Dateinamens auf und gibt an, wie viele zufällige Zeilen gewünscht werden.

Erläuterung

⍞Eingabeaufforderung (Dateiname)
⎕NTIE 0Verknüpfen Sie die Datei mit der nächsten verfügbaren Verknüpfungsnummer (-1 auf einem sauberen System).
t←Speichern Sie die gewählte t
83 80,⍨Verknüpfungsnummer als Anhang [83,80], was [-1,83,80] ergibt. Lesen
⎕NREADSie die ersten 80 Bytes der Datei -1 als 8-Bit-Ganzzahl (Konvertierungscode 83)
10⍳⍨Finden Sie den Index der ersten Zahl 10 (LF)
l←Speichern Sie die Zeilenlänge als l
(⎕NSIZE t)÷Teilen Sie die Größe der Datei -1 mit der Zeilenlänge
⎕Eingabeaufforderung für numerische Eingabe (gewünschte Anzahl von Zeilen )
?X zufällige Auswahlen (ohne Ersetzung) aus den ersten Y natürlichen Zahlen
¯1+Addieren Sie -1, um Zeilennummern mit 0 Ursprung zu erhalten. *
l×Multiplizieren Sie mit der Zeilenlänge, um die
t 82l∘,¨Startbytes zu erhalten Liste der Argumente für ⎕NREAD)
⎕NREAD¨ Lesen Sie jede Zeile als 8-Bit-Zeichen (Konvertierungscode 82)

Praktisches Beispiel

Die Datei /tmp/records.txt enthält:

Hello
Think
12345
Klaus
Nilad

Stellen Sie sicher, dass das Programm RandLines den obigen Code wörtlich enthält, indem Sie Folgendes in die APL-Sitzung eingeben:

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

RandLinesGeben Sie in der APL-Sitzung ein und drücken Sie die Eingabetaste.

Das System bewegt den Cursor in die nächste Zeile, bei der es sich um eine Eingabeaufforderung mit der Länge 0 für Zeichendaten handelt. eintreten /tmp/records.txt.

Das System gibt jetzt ⎕:Zahlen aus und wartet auf deren Eingabe. eintreten 4.

Das System gibt vier zufällige Zeilen aus.

Wahres Leben

In Wirklichkeit möchten Sie möglicherweise Dateinamen und Anzahl als Argumente angeben und das Ergebnis als Tabelle erhalten. Dies kann durch Eingabe von:

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

Jetzt machst du MyLines mit drei zufälligen Zeilen:

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

Wie wäre es, nur eine einzelne zufällige Zeile zurückzugeben, wenn count nicht angegeben ist:

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

Jetzt können Sie beides tun:

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

und (Fehlen des linken Arguments beachten):

MyLine←RandL'/tmp/records.txt'

Code lesbar machen

Golf APL Einzeiler sind eine schlechte Idee. So würde ich in einem Produktionssystem schreiben:

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
}

^{* Ich könnte ein Byte speichern, indem ich im 0-Origin-Modus arbeite, der bei manchen APL-Systemen Standard ist: vorher entfernen ¯1+und einfügen .1+10}

Ruby, 104 94 92 90 Bytes

Dateiname und Zeilenzahl werden in die Kommandozeile übernommen. Zum Beispiel, wenn das Programm ist shuffle.rbund der Dateiname ist a.txt, führt ruby shuffle.rb a.txt 3drei zufällige Linien.

-4 Bytes durch Erkennen der openSyntax in Ruby anstelle vonFile.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}

Hier ist auch eine anonyme 85-Byte-Funktionslösung, deren Argumente eine Zeichenfolge und eine Zahl sind.

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

Liest Dateinamen und n von stdin.

Wie es funktioniert:

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

Es braucht viel Zeit und Speicher, um dieses Programm für Dateien mit vielen Zeilen auszuführen, da die shuffleFunktion fürchterlich ineffizient ist.

Edit: Ich habe den "random without replacement" Teil verpasst (danke @feersum fürs mitbekommen!).

PowerShell v2 +, 209 Byte

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}

Übernimmt die Eingabe $aals Dateiname und $nals Anzahl der Zeilen. Beachten Sie, dass $aes sich um einen Dateinamen mit vollständigem Pfad handeln muss, der als ANSI-Codierung angenommen wird.

Anschließend erstellen wir ein neues FileStreamObjekt und weisen es an, $amit OpenBerechtigungen auf die Datei zuzugreifen .

Die forSchleife .Read()durchläuft die erste Zeile, bis wir ein \nZeichen treffen. Dabei wird der Zeilenzähler für jedes Zeichen erhöht. Wir setzen dann $tgleich der Größe der Datei (dh, wie lang der Stream ist) geteilt durch wie viele Zeichen pro Zeile (plus eins, damit der Terminator zählt), minus eins (da wir null-indiziert sind). Dann konstruieren wir unseren Puffer so $z, dass er auch die Zeilenlänge hat.

Die letzte Zeile erstellt ein dynamisches Array mit dem ..Bereichsoperator. ¹ Wir leiten dieses Array Get-Randommit einer -CAnzahl von $nzufällig ausgewählten $nZeilennummern ohne Wiederholung weiter. Die Glückszahlen werden mit in eine Schleife geleitet |%{...}. Bei jeder Iteration werden wir .Seekan die jeweilige Stelle und dann .Readin einer Zeile Zeichen im Wert von gespeichert $z. Wir wandeln es $zin ein char-Array um und setzen -joines zusammen, wobei die resultierende Zeichenfolge in der Pipeline verbleibt und die Ausgabe am Ende des Programms implizit erfolgt.

Technisch sollten wir mit einem $f.Close()Aufruf zum Schließen der Datei enden , aber das kostet Bytes! : p

Beispiel

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 

_{¹ Technisch bedeutet dies, dass wir nur maximal 50.000 Zeilen unterstützen können, da dies der größte Bereich ist, der auf diese Weise dynamisch erstellt werden kann. : - / Aber wir können nicht einfach eine Get-RandomBefehlsschleife machen $nund doppelte Schleifen verwerfen, da das nicht deterministisch ist ...}

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^

Eingabe: [Dateiname] \ n [Zeilen] \ n

Diese Lösung hat viel von @pppery gestohlen, ist aber nur Python3.5 und ein vollständiges Programm.

Edit: Danke an @Mego für den Inline-Bereich und die Python3.x-Kompatibilität. Edit2: Klarstellung, wo der Druck ist, weil ich zwei Kommentare dazu habe. (Kommentar ist offensichtlich nicht Teil des Codes oder der Byteanzahl.)

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

Verwendet 2 Byte für Zeilenumbrüche. Ändern Sie die 2 in eine 1 für 1. Ich habe es nur als 2, weil das, was meine Testdatei hatte.

Habe mich unter dem PHP-Eintrag aber noch auf Platz 2 (derzeit). Verfluche dich, Ruby Eintrag!

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

Erläuterung

Dadurch wird vermieden, dass die gesamte Datei gelesen wird dd, um die Teile der Datei zu extrahieren, die wir benötigen, ohne die Datei vollständig zu lesen.

ifIst die Eingabedatei
bsdie Blockgröße (hier setzen wir sie auf $ndie Länge der ersten Zeile,
skipdie auf die zufälligen Ganzzahlen festgelegt ist, die aus shufdem ibsWert skipping skip* ibsbytes extrahiert wurden.
countDie Anzahl der zurückzugebenden ibsLängenabschnitte wird zum Entfernen
status=nonebenötigt Die Informationen, die normalerweise von ausgegeben werdendd

Wir bekommen die Zeilenlänge mit head -1 $2|wc -cund die Dateigröße mit stat -c%s $2.

Verwendung

Speichern unter file.shund starten mit file.sh n filename.

Timings

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

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

gegen

time shuf -n4 test.txt
1204350
3496441
3472713
3985479

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

Mal oben für eine 68MiB-Datei, die mit erzeugt wurde seq 1000000 9999999 > test.txt.

Danke an @PeterCordes für seinen -1 Tipp!

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

Dieser Code definiert eine Funktion, die wie folgt aufgerufen wird f(10,'input.txt')

C # 259 Bytes ohne Duplikate

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

File.ReadLines ist faul. Dies hat den zusätzlichen Vorteil, dass alle Leitungen unterschiedlich lang sein können.

Laufen würde es sein:

sample.exe a.txt 10000

C # 206 Bytes mit Duplikaten

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

Python (141 Bytes)

Hält jede Linie mit gleicher Wahrscheinlichkeit, auch bei Rohren. Es ist jedoch keine Antwort auf die Frage, die Sie überspringen müssen ...

Verwendung cat largefile | python randxlines.py 100oder python randxlines 100 < largefile(wie bei @petercordes angegeben)

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