Diberikan file L dengan satu bilangan bulat non-negatif per baris dan file teks F, apa yang akan menjadi cara cepat untuk menjaga hanya baris-baris di F, yang nomor barisnya muncul di file L?
Contoh:
$ cat L.txt
1
3
$ cat F.txt
Hello World
Hallo Welt
Hola mundo
$ command-in-question -x L.txt F.txt
Hello World
Hola mundo
Saya mencari perintah yang dapat menangani file L dengan 500 juta atau lebih entri; File L diurutkan secara numerik.
Catatan: Saya setengah jalan dalam implementasi untuk command-in-question
tetapi saya hanya bertanya-tanya, apakah orang mungkin dapat menggunakan beberapa alat Unix di sini juga.
Pembaruan: Terima kasih atas semua jawaban, saya belajar banyak hari ini! Saya ingin menerima lebih banyak satu jawaban, tetapi itu tidak mungkin.
Jawaban:
Dengan
C
menghilangkan pesan kesalahan yang bermakna:sumber
xsel -bo | cc -xc - -o cselect
. Dan itu hanya berhasil - itu hanya membutuhkan dua lib.LINE_MAX
dalam versi Anda, jadi Anda mungkin bekerja dengan garis yang sangat besar di file Anda. Saya telah memperbarui A dengan versi yang digunakangetline()
untuk menghapus batas ukuran garis.LINE_MAX
, jadigetline
sepertinya tepat.Saya akan menggunakan
awk
, tetapi tidak menyimpan seluruh kontenL.txt
dalam memori dan melakukan hash look up yang tidak perlu ;-).sumber
n
, jika tidak (as-is) itu meleset1
diL.txt
command-in-question
skrip, maka Anda tidak bisa memasukkan nama file dalam kode tersebut.-v list="$opt_x"
tidak bekerja karena proses backslash yang dilakukan oleh awk di atasnya. Itulah sebabnya saya menggunakan ENVIRON sebagai gantinya di sini.grep -n | sort | sed | cut
Itu harus bekerja cukup cepat (beberapa tes waktunya termasuk di bawah ini) dengan input ukuran berapa pun. Beberapa catatan tentang caranya:
export LC_ALL=C
./F
ditumpuk sejajar dengan./L
file lineno -nya , satu-satunya karakter yang benar-benar perlu kita khawatirkan adalah[0-9]
digit ASCII dan:
titik dua.grep -n ''
LINENO:
ke kepala setiap baris di stdin - atau<./F
.sort -t: -nmk1,1 ./L -
sort
sama sekali tidak menyortir file-file inputnya, dan sebaliknya (dengan benar) mengira file-file itu di --m
presort dan menyesuaikannya dalam-numerically
urutan yang diurutkan, pada dasarnya mengabaikan apa pun yang melampaui karakter usus besar yang mungkin-k1,1
terjadi-t:
.sort
akan menampilkan aliran tunggal di mana setiap lineno./L
akan segera mendahului baris yang sesuai di./F
../L
Garis selalu didahulukan karena lebih pendek.sed /:/d\;n
/:/
titik dua,d
hilangkan itu dari output. Lain, cetak otomatis jalur saat ini dann
ext.sed
pangkassort
output hanya untuk pasangan garis berurutan yang tidak cocok dengan titik dua dan baris berikut - atau, hanya untuk satu baris dari./L
dan kemudian berikutnya.cut -sd: -f2-
cut
-s
uppresses dari output mereka dari jalur input yang tidak mengandung setidaknya satu dari-d:
string elimiter - dan begitu juga./L
garis dipangkas sepenuhnya.:
dibatasi usus besar pertama mereka-f
adacut
- dan begitu juga semuagrep
lineno yang dimasukkan.uji input kecil
... menghasilkan 5 baris input sampel. Kemudian...
... mencetak ...
tes waktunya lebih besar
Saya membuat beberapa file yang cukup besar:
... yang memasukkan 5 mil garis
/tmp/F
dan 1,5 mil garis yang dipilih secara acak ke dalam/tmp/L
. Saya kemudian melakukan:Itu dicetak:
(Saya menambahkan garis miring terbalik di sana)
Di antara solusi yang saat ini ditawarkan di sini, ini adalah yang tercepat dari mereka semua tetapi satu ketika diadu dengan dataset yang dihasilkan di atas pada mesin saya. Yang lainnya hanya satu yang hampir bersaing untuk tempat kedua, dan itu meuh di
perl
sini .Ini sama sekali bukan solusi asli yang ditawarkan - ia telah menjatuhkan sepertiga dari waktu pelaksanaannya berkat saran / inspirasi yang ditawarkan oleh orang lain. Lihat riwayat kiriman untuk solusi yang lebih lambat (tapi mengapa?) .
Juga, perlu dicatat bahwa beberapa jawaban lain mungkin akan berpendapat lebih baik jika bukan karena arsitektur multi-CPU dari sistem saya dan eksekusi bersamaan dari setiap proses dalam pipa itu. Mereka semua bekerja pada saat yang sama - masing-masing pada inti prosesor sendiri - melewati data dan melakukan bagian kecil mereka secara keseluruhan. Itu sangat keren.
tetapi solusi tercepat adalah ...
Tetapi ini bukan solusi tercepat. Solusi tercepat yang ditawarkan di sini, tangan-down, adalah program C . Saya menyebutnya
cselect
. Setelah menyalinnya ke clipboard X saya, saya mengompilasinya seperti:Saya kemudian melakukannya:
... dan hasilnya adalah ...
sumber
sed -ne'/:/!{n;p;}' | cut -d: -f2-
bukansed -ne'/:/!N;/\n/s/[^:]*://p'
sed
s - yangsed
saya gunakan adalah pusakased
- Anda dapat melihatalias
nilai dalamtime
hasil. Paket pusaka saya, by the way, secara statis dikompilasi melawan libc musl - implementasi regex yang didasarkan pada TRE . Ketika saya beralih ke GNUsed
- dan menjalankannya tanpacut
- itu menambahkan satu detik penuh ke waktu penyelesaian (2,8 detik) - senyawa itu lebih dari sepertiga. Dan itu hanya 0,3 detik lebih cepat daripada milik Anda di sistem saya.sort -mn
sebagai lawansort -nmk1,1
mungkin lebih baik karena Anda tidak perlu melakukan pemisahan di sini (tidak diuji)-n
adalah spec'd hanya untuk melakukan string numerik pertama pada sebuah baris jadi saya pikir, ok-mn
atau-nm
dan, untuk alasan apa pun satu-satunya kali itu dicelupkan di bawah 2sec dalam waktu penyelesaian adalah ketika saya menambahkan semua opsi apa adanya. Ini aneh - dan itu alasannya kemarin saya tidak memakainya-m
- saya tahu apa yang saya maksud, tetapi sepertinya hanya berhasil sebagai semacam optimasi otomatis. Menariknya, heirloomsort
memiliki-z
opsi string-length yang hanya berlaku untuk-[cm]
....-n
bukan string numerik pertama di telepon . Itu hanya menganggap garis sebagai angka sehinggaabc 123
akan menjadi 0. Jadi tidak bisa kurang efisien daripada dengan-t: -k1,1
Saya akan menggunakan
awk
:Pembaruan: Saya telah melakukan pengukuran kinerja; tampaknya versi ini menskala lebih baik dengan set data yang sangat besar (seperti halnya dengan persyaratan yang dinyatakan), karena perbandingannya sangat cepat dan mengkompensasi upaya yang diperlukan untuk membangun tabel hash.
sumber
awk
s dapat menangani set data sebesar itu. - Saya menggunakan GNUawk
dan tidak ada masalah; tes dengan 500 juta baris data diperlukan 7 menit.real 16m3.468s
-user 15m48.447s
-sys 0m10.725s
. Ini digunakan 3,3 GB RAM pengujian ukuran 1/10L
dengan 50.000.000 baris; danF
dengan 500.000.000 baris - vs waktu untuk Stéphane Chazelas 'awk anser:real 2m11.637s
-user 2m2.748s
-sys 0m6.424s
- Saya tidak menggunakan kotak cepat, tetapi perbandingannya menarik.seq
output dan kemudian yang lebih kecil, bagian yang dipilih secara acak dari yang sama di L .Hanya untuk kelengkapan: kita dapat menggabungkan skrip awk yang sangat baik dalam jawaban oleh Stéphane Chazelas, dan skrip perl dalam jawaban dengan kos tetapi tanpa menyimpan seluruh daftar dalam memori, dengan harapan perl mungkin lebih cepat daripada awk. (Saya telah mengubah urutan argumen agar sesuai dengan pertanyaan awal).
sumber
awk
. Ini hampir secepat milik saya - Saya menguji keduanya tiga kali sekarang dan setiap kali saya menangani testset garis 5mil saya dalam 1,8 ... detik dan Anda 1,9 ... detik setiap kali. Kode gen testset ada dalam jawaban saya jika Anda peduli, tetapi intinya sangat bagus. Terlebih lagi, hasilnya benar - saya masih tidak bisaawk
bekerja ... Meski begitu, kedua jawaban kami dipermalukan oleh FloHimself .awk
s yang berbeda . Pada sampel Anda, saya mendapatkan 1.4s dengan gawk (4s untuk Janis '), 0.9s dengan mawk, 1.7s dengan solusi perl ini, 2.3s dengan kos', 4.5s dengan milik Anda (sed GNU), dan 1.4s dengan milik Anda ( GNU sed) dan perbaikan yang saya sarankan (dan 0,5s untuk solusi C).Saya menulis skrip Perl sederhana untuk melakukan itu:
Usage: script.pl inputfile_f inputfile_f
F.txt
L.txt
L.txt
dalam sebuah arrayF.txt
baris demi baris, melacak nomor baris saat ini dan indeks array saat ini; meningkatkanF.txt
nomor baris saat ini; jikaF.txt
nomor baris saat ini cocok dengan konten array di indeks array saat ini, itu mencetak baris saat ini dan meningkatkan indeksPertimbangan biaya dan kompleksitas :
Mempertimbangkan biaya untuk membuat penugasan, biaya untuk membuat perbandingan dan biaya untuk mencetak garis, diberikan N 1 sebagai jumlah baris
F.txt
dan N 2 sebagai jumlah barisL.txt
,while
loop berjalan paling banyak N 1 kali, mengarah ke penugasan 2N 1 + N 2 (jelas dengan asumsi N 1 > N 2 ), untuk perbandingan 2N 1 dan ke cetakan N 2 ; diberikan sebagai sama dengan biaya setiap operasi, total biaya untuk menjalankanwhile
loop adalah 4N 1 + 2N 2 , yang mengarah pada kompleksitas skrip O (N).Tes pada file input 10 juta baris :
Menggunakan file 10-juta-baris yang
F.txt
berisi 50-karakter-panjang baris acak dan 10-juta-barisL.txt
file yang berisi angka 1 hingga 10.000000 (skenario terburuk):sumber
Solusi perl ini lebih cepat daripada solusi awk atau perl lainnya sebesar 20% atau lebih, tetapi sebelumnya tidak secepat solusi dalam C.
sumber
Karena L.txt diurutkan Anda dapat menggunakan gabung. Cukup beri nomor pada setiap baris di F.txt, gabungkan dua file, lalu hapus nomor baris. Tidak diperlukan file perantara yang besar.
Sebenarnya, di atas akan memotong-motong garis data Anda dengan mengganti semua ruang putih dengan satu ruang. Agar garis tetap utuh, Anda harus memilih sebagai pembatas beberapa karakter yang tidak muncul dalam data Anda, mis. "|". Cmd kemudian
Sed pertama menghapus spasi utama dari output "cat -n" dan menggantikan tab. Sed kedua menghapus nomor baris dan "|".
sumber
join L.txt <(nl F.txt )
tetapi tidak akan bekerja pada file besar. Selamat datang di situs ini, omong-omong, jarang kita mendapatkan jawaban yang jelas dan terformat dengan baik dari pengguna baru!join
/comm
tidak bisa bekerja dengan masukan numerik diurutkan.join -t' ' <(<L.txt awk '{printf("%010s\n",$0)}') <(<F.txt awk '{printf("%010s %s\n",NR,$0)}') | cut -d' ' -f2-
- Itu lambat! - dan bahkan ketika sayajoin -t' ' L.txt F.txt | cut -d' ' -f2-
memasukkan file yang sudah disiapkan dengan kunci 0-padded yang cocok , masih lambat (tidak termasuk waktu persiapan) - lebih lambat dariawk
jawaban oleh @Janis (di mana saya telah mengirim komentar tentang waktu aktual yang diambil untuk kedua jawabannya dan @ StéphaneChazelas 'join
+ adalah vs Stéphane Chazelas ' menggunakan 50 juta baris, 500 juta baris.awk printf
real 20m11.663s user 19m35.093s sys 0m10.513s
real 2m11.637s user 2m2.748s sys 0m6.424s
L
F
Untuk kelengkapan, upaya lain untuk
join
solusi:Ini berfungsi dengan memformat kolom nomor baris yang bergabung bekerja sebagai panjang tetap dengan nol di depan, sehingga angka-angka selalu panjang 15 digit. Ini menghindari masalah bergabung tidak menyukai urutan urutan numerik yang normal, karena kolom sekarang secara efektif telah dipaksa menjadi semacam kamus.
nl
digunakan untuk menambahkan nomor baris dalam format ini ke F.txt. Sayangnyased
perlu digunakan untuk memformat ulang penomoran dalam L.txt.Pendekatan ini tampaknya berfungsi baik pada data uji yang dihasilkan menggunakan metode @ mikeserv. Tetapi masih sangat lambat - solusi c 60x lebih cepat pada mesin saya. sekitar 2/3 dari waktu dihabiskan di
sed
dan 1/3 dijoin
. Mungkin ada ekspresi sed yang lebih baik ...sumber
nl
sangat keren, tetapi Anda tidak dapat menggunakannya dengan kuat pada input yang belum diuji. Salah satu hal yang membuatnya sangat keren adalah penghapus halaman-d
logisnya. Secara default jika ada baris dalam input yang hanya terdiri dari string:\`
(tapi tanpa jejak trailing) 1, 2, 3 atau tiga kali berturut-turut, hitungan Anda akan menjadi sedikit gila. Eksperimen dengan itu - cukup rapi. Terutama melihat apa yang terjadi ketika nl` membaca baris dengan 1 pembatas string dan kemudian lain w / 3 atau 2Karena jawaban yang diterima adalah dalam C, saya pikir tidak masalah untuk melempar solusi python di sini:
Jika menggunakan perpustakaan eksternal seperti numpy, solusi akan terlihat lebih elegan:
sumber