Tantangan ini adalah tentang membaca garis acak dari file yang berpotensi besar tanpa membaca keseluruhan file ke dalam memori.
Memasukkan
Integer n
dan nama file teks.
Keluaran
n
baris file teks dipilih secara acak secara acak tanpa penggantian.
Anda dapat mengasumsikan bahwa n
berada dalam kisaran 1 hingga jumlah baris dalam file.
Berhati-hatilah saat mengambil sampel n
angka secara acak dari rentang jawaban yang Anda dapatkan seragam. rand()%n
di 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.
fseek
, dan tidak mungkin dalam bahasa lain. Selain itu, bagaimana jikan
lebih besar dari jumlah baris dalam file?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 ...).Jawaban:
Dyalog APL , 63 byte
Meminta nama file, lalu untuk berapa banyak garis acak yang diinginkan.
Penjelasan
⍞
Prompt untuk input teks (nama file)⎕NTIE 0
Ikat file menggunakan nomor ikat berikutnya yang tersedia (-1 pada sistem bersih)t←
Simpan nomor ikat yang dipilih sebagait
83 80,⍨
Tambah [83,80] menghasilkan [-1,83,80]⎕NREAD
Baca 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 sebagail
(⎕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 *l×
Kalikan dengan panjang garis untuk mendapatkan byte awalt 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:
Buat program RandLines berisi kode di atas kata demi kata dengan memasukkan yang berikut ke dalam sesi APL:
Dalam jenis sesi APL
RandLines
dan 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; masuk4
.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:
Sekarang Anda membuat MyLines berisi tiga garis acak dengan:
Bagaimana mengembalikan hanya satu baris acak jika penghitungan tidak ditentukan:
Sekarang Anda dapat melakukan keduanya:
dan (perhatikan tidak adanya argumen kiri):
Membuat kode dapat dibaca
APL golf satu baris adalah ide yang buruk. Inilah cara saya menulis dalam sistem produksi:
* Saya bisa menyimpan byte dengan menjalankan dalam mode 0-origin, yang merupakan standar pada beberapa sistem APL: hapus
¯1+
dan masukkan1+
sebelumnya10
.sumber
Ruby,
104949290 byteNama file dan jumlah baris dilewatkan ke baris perintah. Misalnya, jika programnya
shuffle.rb
dan nama file-nyaa.txt
, jalankanruby shuffle.rb a.txt 3
untuk tiga baris acak.-4 byte dari menemukan
open
sintaks di Ruby, bukanFile.new
Juga, inilah solusi fungsi anonim 85-byte yang menggunakan string dan angka sebagai argumennya.
sumber
ruby shuffle.rb 3 < a.txt
memberi Anda stdin dicari. Namun, IDK Ruby.Haskell,
240224236 byteMembaca nama file dan n dari stdin.
Bagaimana itu bekerja:
Membutuhkan banyak waktu dan memori untuk menjalankan program ini untuk file dengan banyak baris, karena
shuffle
fungsi yang tidak efisien yang mengerikan .Sunting: Saya melewatkan bagian "acak tanpa penggantian" (terima kasih @feersum karena memperhatikan!).
sumber
PowerShell v2 +, 209 byte
Mengambil input
$a
sebagai nama file dan$n
jumlah baris. Perhatikan bahwa$a
nama file harus path lengkap, dan dianggap sebagai pengkodean ANSI.Kami kemudian membangun
FileStream
objek baru , dan menyuruhnya mengakses file$a
denganOpen
hak istimewa.The
for
Loop.Read()
s melalui baris pertama sampai kita mencapai\n
karakter, incrementing kami line-panjang kontra masing-masing karakter. Kami kemudian mengatur$t
sama 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$z
juga menjadi panjang garis.Baris terakhir membangun array dinamis dengan
..
operator jangkauan. 1 Kami mem-pipe array ituGet-Random
dengan-C
ount of$n
untuk secara acak memilih$n
nomor baris tanpa pengulangan. Angka keberuntungan disalurkan ke dalam lingkaran dengan|%{...}
. Setiap iterasi kita.Seek
ke lokasi tertentu, dan kemudian.Read
dalam karakter garis, disimpan ke dalam$z
. Kami kembali melemparkan$z
sebagai array-char dan-join
bersama-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! : pContoh
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-Random
perintah$n
, membuang duplikat setiap loop, karena itu tidak deterministik ...sumber
Python 3,
146139 byteInput: [nama file] \ n [baris] \ n
Solusi ini sangat dicuri dari @pppery tetapi
hanya python3.5 danmerupakan 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.)
sumber
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 memasukkanrange
panggilan dalamsample
panggilan. Selain itu, ini bukan program lengkap - Anda harus benar-benar mencetak daftar.r=[*range(f.seek(0,2)//l)]
karena saya pikir saya tidak bisasample
generator. Ternyata saya bisa. @Mega: Lengkap karena mencetak setiap baris di dalam daftar pemahamanprint(f.read(l))
Lua,
126122Menggunakan 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!
sumber
Bash (well, coreutils), 100 byte
Penjelasan
Ini menghindari membaca seluruh file menggunakan
dd
untuk mengekstrak bagian dari file yang kita butuhkan tanpa membaca file seluruhnya, sayangnya itu berakhir cukup besar dengan semua opsi yang harus kita tentukan:if
adalah file inputbs
adalah ukuran blok (di sini kita mengaturnya$n
yang merupakan panjang dari baris pertamaskip
diatur ke bilangan bulat acak yang diekstraksi darishuf
dan sama denganibs
nilai melompatiskip
*ibs
bytecount
jumlahibs
bagian panjang untuk kembalistatus=none
diperlukan untuk menghapus) informasi biasanya dihasilkan olehdd
Kami mendapatkan panjang garis menggunakan
head -1 $2|wc -c
dan filesize denganstat -c%s $2
.Pemakaian
Simpan di atas sebagai
file.sh
dan jalankan menggunakanfile.sh n filename
.Pengaturan waktu
vs.
Waktu di atas untuk file 68MiB dibuat menggunakan
seq 1000000 9999999 > test.txt
.Terima kasih kepada @PeterCordes untuk -1 tipnya!
sumber
bs=
melakukannyaibs=
, karena pengaturanobs
juga baik-baik saja. Saya kira Anda tidak dapat menggantiif=$2
dengan<$2
, karena ini masihxargs
baris perintah.\<$2
juga tidak berfungsi (xargs menggunakan exec secara langsung, tanpa shell).2>&-
, jadi tidak ada bahaya output pergi ke mana pun (misalnya jika stdin kebetulan menjadi deskriptor file baca-tulis). Ini bekerja dengan GNUdd
: Masih menghasilkanstdout
sebelum mencoba dan gagal menulisstderr
.Python 3 -
161 160149 byteKode ini mendefinisikan fungsi yang disebut seperti
f(10,'input.txt')
sumber
C # 259 byte tanpa duplikat
Tidak disatukan
File.ReadLines adalah Malas. Ini memiliki manfaat tambahan bahwa semua lini dapat memiliki panjang yang berbeda.
Menjalankannya adalah:
C # 206 byte dengan duplikat
Tidak disatukan
sumber
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 100
ataupython randxlines 100 < largefile
(seperti yang ditunjukkan oleh @petercordes)sumber
python ./randxlines.py 100 < largefile
akan baik-baik saja untuk jawaban yang tepat, dalam halstdin
ini akan dicari.