Baca n baris acak dari file yang berpotensi besar

16

Tantangan ini adalah tentang membaca garis acak dari file yang berpotensi besar tanpa membaca keseluruhan file ke dalam memori.

Memasukkan

Integer ndan nama file teks.

Keluaran

n baris file teks dipilih secara acak secara acak tanpa penggantian.

Anda dapat mengasumsikan bahwa nberada dalam kisaran 1 hingga jumlah baris dalam file.

Berhati-hatilah saat mengambil sampel nangka secara acak dari rentang jawaban yang Anda dapatkan seragam. rand()%ndi C tidak seragam misalnya. Setiap hasil harus memiliki kemungkinan yang sama.

Aturan dan batasan

Setiap baris file teks akan memiliki jumlah karakter yang sama dan itu tidak akan lebih dari 80.

Kode Anda tidak boleh membaca isi file teks kecuali:

  • Garis-garis itu menghasilkan.
  • Baris pertama yang menentukan jumlah karakter per baris dalam file teks.

Kita dapat mengasumsikan setiap karakter dalam file teks tersebut membutuhkan tepat satu byte.

Pemisah garis dianggap panjang 1 byte. Solusi dapat menggunakan pemisah garis panjang 2 byte hanya jika mereka menentukan kebutuhan ini. Anda juga dapat menganggap baris terakhir diakhiri oleh pemisah baris.

Jawaban Anda harus merupakan program yang lengkap tetapi Anda dapat menentukan input dengan cara apa pun yang nyaman.

Bahasa dan perpustakaan

Anda dapat menggunakan bahasa atau perpustakaan apa pun yang Anda suka.

Catatan

Ada kekhawatiran tentang menghitung jumlah baris dalam file. Seperti nimi tunjukkan dalam komentar, Anda dapat menyimpulkan ini dari ukuran file dan jumlah karakter per baris.

Motivasi

Dalam obrolan, beberapa orang bertanya apakah ini benar-benar pertanyaan "Lakukan X tanpa Y". Saya menafsirkan ini untuk menanyakan apakah pembatasan itu buatan luar biasa.

Tugas pengambilan sampel secara acak dari file-file besar bukanlah hal yang tidak biasa dan bahkan kadang harus saya lakukan. Salah satu cara untuk melakukan ini adalah di bash:

shuf -n <num-lines>

Namun ini sangat lambat untuk file besar karena membaca di seluruh file.


sumber
Mengapa downvote?
3
Ini sepele dalam bahasa seperti C yang dimiliki fseek, dan tidak mungkin dalam bahasa lain. Selain itu, bagaimana jika nlebih besar dari jumlah baris dalam file?
Mego
4
@Mego: tentang poin Anda b): Anda dapat menghitung jumlah baris dengan membagi ukuran file dengan panjang satu baris.
nimi
8
Do X without Y adalah peringatan yang dimulai dengan "Ini tidak selalu buruk". Masalah utama adalah pembatasan buatan seperti "jangan gunakan +" yang memberikan keuntungan untuk bahasa yang memiliki sum(). Tidak membaca file ke dalam memori adalah pembatasan yang jelas dan konsisten yang sama sekali tidak sewenang-wenang. Ini dapat diuji dengan file yang lebih besar dari memori, yang tidak dapat diselesaikan dengan perbedaan bahasa. Itu juga kebetulan memiliki aplikasi dunia nyata (walaupun itu tidak diperlukan untuk golf ...).
trichoplax
1
Sepertinya ini sebenarnya adalah kode golf kompleksitas terbatas di mana penggunaan memori terbatas meskipun file berpotensi besar. Ini bukan tentang tidak memiliki hal-hal tertentu dalam kode Anda tetapi batasan pada bagaimana kode tersebut dapat bertindak.
xnor

Jawaban:

5

Dyalog APL , 63 byte

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

Meminta nama file, lalu untuk berapa banyak garis acak yang diinginkan.

Penjelasan

Prompt untuk input teks (nama file)
⎕NTIE 0Ikat file menggunakan nomor ikat berikutnya yang tersedia (-1 pada sistem bersih)
t←Simpan nomor ikat yang dipilih sebagai t
83 80,⍨Tambah [83,80] menghasilkan [-1,83,80]
⎕NREADBaca 80 byte pertama dari file -1 sebagai bilangan bulat 8-bit (kode konversi 83)
10⍳⍨Temukan indeks dari angka pertama 10 (LF)
l←Simpan panjang baris sebagai l
(⎕NSIZE t)÷Membagi ukuran file -1 dengan panjang baris
Prompt untuk input numerik (jumlah baris yang diinginkan )
?X pilihan acak (tanpa penggantian) keluar dari bilangan Y alami pertama
¯1+Tambahkan -1 untuk mendapatkan nomor garis asal-0 *
Kalikan dengan panjang garis untuk mendapatkan byte awal
t 82l∘,¨Prepend [-1,82, LineLength] untuk setiap byte awal (membuat daftar argumen untuk ⎕NREAD)
⎕NREAD¨ Baca setiap baris sebagai karakter 8-bit (kode konversi 82)

Contoh praktis

File /tmp/records.txt berisi:

Hello
Think
12345
Klaus
Nilad

Buat program RandLines berisi kode di atas kata demi kata dengan memasukkan yang berikut ke dalam sesi APL:

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

Dalam jenis sesi APL RandLinesdan tekan Enter.

Sistem memindahkan kursor ke baris berikutnya, yang merupakan prompt 0-length untuk data karakter; masuk /tmp/records.txt.

Sistem sekarang menampilkan ⎕:dan menunggu input numerik; masuk 4.

Sistem mengeluarkan empat garis acak.

Kehidupan nyata

Pada kenyataannya, Anda mungkin ingin memberikan nama file dan menghitung sebagai argumen dan menerima hasilnya sebagai tabel. Ini dapat dilakukan dengan memasukkan:

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

Sekarang Anda membuat MyLines berisi tiga garis acak dengan:

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

Bagaimana mengembalikan hanya satu baris acak jika penghitungan tidak ditentukan:

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

Sekarang Anda dapat melakukan keduanya:

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

dan (perhatikan tidak adanya argumen kiri):

MyLine←RandL'/tmp/records.txt'

Membuat kode dapat dibaca

APL golf satu baris adalah ide yang buruk. Inilah cara saya menulis dalam sistem produksi:

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
}

* Saya bisa menyimpan byte dengan menjalankan dalam mode 0-origin, yang merupakan standar pada beberapa sistem APL: hapus ¯1+dan masukkan 1+sebelumnya 10.

Adám
sumber
Ahh .. APL :) Apakah ada cara untuk menguji kode ini di linux?
@Lembik Tentu, kode ini adalah platform silang. Unduh dari dyalog.com
Adám
Karena saya tidak membaca APL, bisakah Anda menjelaskan kodenya? Bagian yang sulit adalah garis pengambilan sampel tanpa penggantian dan melompat langsung ke tempat yang tepat dalam file untuk membaca garis.
@Lembik Bagian itu mudah. Argumen RENREAD adalah TieNumber ConversionCode BytesToRead [StartByte]. Bunyinya hanya byte yang diperlukan. Sisanya hanya mencari tahu apa yang harus dibaca.
Adám
@Lembik Saya ingin tahu mengapa jawaban saya tidak memenangkan hadiah.
Adám
7

Ruby, 104 94 92 90 byte

Nama file dan jumlah baris dilewatkan ke baris perintah. Misalnya, jika programnya shuffle.rbdan nama file-nya a.txt, jalankan ruby shuffle.rb a.txt 3untuk tiga baris acak.

-4 byte dari menemukan opensintaks di Ruby, bukanFile.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}

Juga, inilah solusi fungsi anonim 85-byte yang menggunakan string dan angka sebagai argumennya.

->f,l{f=open f;puts [*0..f.size/n=f.gets.size+1].sample(l).map{|e|f.seek n*e;f.gets}}
Nilai Tinta
sumber
Di bawah 100 byte! Mungkin Ruby adalah bahasa golf terbaik. Apakah 'sampel' menghindari pengulangan?
@Lembik ruby-doc.org/core-2.2.0/Array.html#method-i-sample Ini memang menghindari pengulangan. Jangan bilang ... apakah saya harus melakukan pengulangan?
Value Ink
Tidak, Anda sempurna :)
Bisakah Anda menyimpan byte dengan membaca dari stdin? ruby shuffle.rb 3 < a.txtmemberi Anda stdin dicari. Namun, IDK Ruby.
Peter Cordes
1
@PeterCordes Itu masuk akal, tetapi seperti yang disebutkan, titik kegagalannya adalah Ruby tidak dapat membaca ukuran file stdin, jadi itu tidak berhasil.
Nilai Tinta
5

Haskell, 240 224 236 byte

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

Membaca nama file dan n dari stdin.

Bagaimana itu bekerja:

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

Membutuhkan banyak waktu dan memori untuk menjalankan program ini untuk file dengan banyak baris, karena shufflefungsi yang tidak efisien yang mengerikan .

Sunting: Saya melewatkan bagian "acak tanpa penggantian" (terima kasih @feersum karena memperhatikan!).

nimi
sumber
Batu Haskell :)
1
Bagaimana cara menghindari memilih garis yang sudah dipilih?
feersum
@feersum: oh, saya merindukan bagian itu. Tetap.
nimi
Saya melihat stackoverflow.com/questions/13779630/… agak bertele-tele!
1
Mungkin harus ada tantangan terpisah dalam pengambilan sampel tanpa penggantian di ruang kecil.
3

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}

Mengambil input $asebagai nama file dan $njumlah baris. Perhatikan bahwa $anama file harus path lengkap, dan dianggap sebagai pengkodean ANSI.

Kami kemudian membangun FileStreamobjek baru , dan menyuruhnya mengakses file $adengan Openhak istimewa.

The forLoop .Read()s melalui baris pertama sampai kita mencapai \nkarakter, incrementing kami line-panjang kontra masing-masing karakter. Kami kemudian mengatur $tsama dengan ukuran file (yaitu, berapa lama aliran) dibagi dengan berapa banyak karakter per baris (ditambah satu sehingga menghitung terminator), minus satu (karena kami diindeks nol). Kami kemudian membangun buffer kami $zjuga menjadi panjang garis.

Baris terakhir membangun array dinamis dengan ..operator jangkauan. 1 Kami mem-pipe array itu Get-Randomdengan -Count of $nuntuk secara acak memilih $nnomor baris tanpa pengulangan. Angka keberuntungan disalurkan ke dalam lingkaran dengan |%{...}. Setiap iterasi kita .Seekke lokasi tertentu, dan kemudian .Readdalam karakter garis, disimpan ke dalam $z. Kami kembali melemparkan $zsebagai array-char dan -joinbersama-sama, meninggalkan string yang dihasilkan pada pipa dan output tersirat pada akhir program.

Secara teknis kita harus mengakhiri dengan $f.Close()panggilan untuk menutup file, tetapi itu biaya byte! : p

Contoh

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 Secara teknis, ini berarti kami hanya dapat mendukung maksimal 50.000 baris, karena itulah rentang terbesar yang dapat dibuat secara dinamis dengan cara ini. : - / Tapi, kita tidak bisa hanya mengulang kali Get-Randomperintah $n, membuang duplikat setiap loop, karena itu tidak deterministik ...

AdmBorkBork
sumber
2

Python 3, 146 139 byte

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^

Input: [nama file] \ n [baris] \ n

Solusi ini sangat dicuri dari @pppery tetapi hanya python3.5 dan merupakan program yang lengkap.

Sunting: Terima kasih kepada @Mego untuk kisaran inline dan kompatibilitas python3.x. Sunting2: Klarifikasi di mana hasil cetak karena saya mendapat dua komentar tentang hal itu. (Komentar jelas bukan bagian dari kode atau jumlah byte.)

Alexander Nigl
sumber
Terima kasih! Bagian mana yang hanya python 3.5?
2
r=range(f.seek(0,2)//l)akan bekerja, yang memangkas 3 byte dan menghilangkan kebutuhan untuk 3.5. Bahkan lebih baik, mencukur 3 byte lebih banyak dengan memasukkan rangepanggilan dalam samplepanggilan. Selain itu, ini bukan program lengkap - Anda harus benar-benar mencetak daftar.
Mego
@ Lembik: Itu 3.5 hanya karena saya menggunakan r=[*range(f.seek(0,2)//l)]karena saya pikir saya tidak bisa samplegenerator. Ternyata saya bisa. @Mega: Lengkap karena mencetak setiap baris di dalam daftar pemahamanprint(f.read(l))
Alexander Nigl
Anda memang membutuhkan pernyataan cetak.
cetak ada di dalam daftar pemahaman.
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

Menggunakan 2 byte untuk jeda baris. Ubah 2 menjadi 1 untuk 1. Saya hanya memilikinya sebagai 2 karena itulah yang dimiliki file pengujian saya.

Mendapat diriku di bawah entri PHP, tetapi masih menempati posisi ke-2 (saat ini). Terkutuklah kamu, entri Ruby!

Pengobrol
sumber
1
Lua adalah bahasa pemrograman pertama yang saya pelajari, dan bahkan dengan semua yang saya pelajari sejak saat itu, itu masih menjadi favorit saya. Sangat fleksibel untuk kemudahan menulis.
Blab
2

Bash (well, coreutils), 100 byte

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

Penjelasan

Ini menghindari membaca seluruh file menggunakan dduntuk mengekstrak bagian dari file yang kita butuhkan tanpa membaca file seluruhnya, sayangnya itu berakhir cukup besar dengan semua opsi yang harus kita tentukan:

ifadalah file input
bsadalah ukuran blok (di sini kita mengaturnya $nyang merupakan panjang dari baris pertama
skipdiatur ke bilangan bulat acak yang diekstraksi dari shufdan sama dengan ibsnilai melompati skip* ibsbyte
countjumlah ibsbagian panjang untuk kembali
status=nonediperlukan untuk menghapus) informasi biasanya dihasilkan olehdd

Kami mendapatkan panjang garis menggunakan head -1 $2|wc -cdan filesize dengan stat -c%s $2.

Pemakaian

Simpan di atas sebagai file.shdan jalankan menggunakan file.sh n filename.

Pengaturan waktu

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

Waktu di atas untuk file 68MiB dibuat menggunakan seq 1000000 9999999 > test.txt.

Terima kasih kepada @PeterCordes untuk -1 tipnya!

Dom Hastings
sumber
1
Saya selalu menyukai jawaban bash tetapi dapatkah Anda menjelaskan bagaimana ini tidak membaca keseluruhan file?
2
@Lembik menambahkan penjelasan!
Dom Hastings
1
Anda dapat bs=melakukannya ibs=, karena pengaturan obsjuga baik-baik saja. Saya kira Anda tidak dapat mengganti if=$2dengan <$2, karena ini masih xargsbaris perintah. \<$2juga tidak berfungsi (xargs menggunakan exec secara langsung, tanpa shell).
Peter Cordes
Saya harap ini tidak terlalu banyak tapi saya suka jawaban ini :) Hanya mengujinya dengan file 1GB.
1
re: redirect stderr ke stdin: Anda juga bisa menutup stderr dengan 2>&-, jadi tidak ada bahaya output pergi ke mana pun (misalnya jika stdin kebetulan menjadi deskriptor file baca-tulis). Ini bekerja dengan GNU dd: Masih menghasilkan stdoutsebelum mencoba dan gagal menulis stderr.
Peter Cordes
1

Python 3 - 161 160 149 byte

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

Kode ini mendefinisikan fungsi yang disebut seperti f(10,'input.txt')

pppery
sumber
1
Tantangannya membutuhkan program lengkap, jadi saya khawatir definisi fungsi tidak cukup.
nimi
Untuk menghemat byte, hapus ruang antara impor dan *.
mriklojn
1
@nimi Membutuhkan program lengkap untuk tantangan ini tampaknya secara arbiter mengesampingkan aturan format kode default
pppery
@pperry: ya, mungkin, tapi begitulah adanya.
nimi
Untuk mendapatkan panjang file Anda bisa f.seek (0,2) , yang membuat impor os dan os.stat usang.
Alexander Nigl
1

C # 259 byte tanpa duplikat

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

Tidak disatukan

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 adalah Malas. Ini memiliki manfaat tambahan bahwa semua lini dapat memiliki panjang yang berbeda.

Menjalankannya adalah:

sample.exe a.txt 10000

C # 206 byte dengan duplikat

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

Tidak disatukan

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
sumber
Saya tidak sepenuhnya mengikuti solusi Anda. Jika semua garis memiliki panjang yang berbeda maka tugas tersebut tidak mungkin. Juga, bagaimana tepatnya Anda mengambil sampel secara acak tanpa penggantian? Saya minta maaf C # saya tidak cukup baik.
@Lembik Anda benar, saya tidak memikirkan duplikat. Dan saya bisa menghitung jumlah baris dan mengekstrak baris dengan linenumber, yang mengapa garis mungkin variabel panjang.
Master117
Tetapi Anda harus melompat ke lokasi di file hanya mengetahui nomor baris bukan? Anda tidak bisa tahu di mana itu kecuali semua garis memiliki panjang yang sama.
@Lembik File.ReadLines ("pathToFile") membuat enumerasi Malas pada semua Baris File, File.ReadLines ("pathToFile"). ElementAt (19) mengembalikan Baris ke-19 File. Agak seperti Peta dari semua Linestarts.
Master117
Saya tidak berpikir enumerasi Malas melompat (atau mencari) dalam file dengan sedih. Jadi tidak sesuai dengan aturan saat ini.
1

Python (141 byte)

Mempertahankan setiap baris dengan probabilitas yang sama, gunakan dengan pipa juga. Itu tidak menjawab batasan pertanyaan selanjutnya ...

Penggunaan cat largefile | python randxlines.py 100atau python randxlines 100 < largefile(seperti yang ditunjukkan oleh @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))
topkara
sumber
3
Inti dari pertanyaan ini adalah Anda harus mencari di aliran input. Anda mungkin harus mengatakan bahwa itu adalah bagian dari batasan pertanyaan yang Anda abaikan (meskipun penggunaan contoh read-from-a-pipe membuatnya cukup jelas). Membaca dari stdin dengan python ./randxlines.py 100 < largefileakan baik-baik saja untuk jawaban yang tepat, dalam hal stdinini akan dicari.
Peter Cordes