Grep sejumlah besar pola dari file besar

18

Saya memiliki file yang bertambah sekitar 200.000 baris sehari, dan semuanya terbentuk dengan blok tiga baris seperti itu:

1358726575123       # key
    Joseph Muller   # name
    carpenter       # job
9973834728345
    Andres Smith
    student
7836472098652
    Mariah Anthony
    dentist

Sekarang, saya memiliki file lain dari mana saya mengekstrak sekitar 10.000 pola kunci, seperti 1358726575123. Kemudian saya menjalankan forloop dengan pola-pola ini dan harus memeriksanya terhadap file pertama. Jika file tidak mengandung pola seperti itu, saya menyimpan pola di file ketiga untuk diproses lebih lanjut:

for number in $(grep -o '[0-9]\{12\}' file2); do  # finds about 10.000 keys
     if ! grep -q ^$number$ file1; then           # file1 is a huge file
         printf "$number\n" >>file3               # we'll process file3 later
     fi
done

Kode contoh menangkap sebuah file besar 10.000 kali, dan saya menjalankan loop ini sekitar satu menit sekali, sepanjang hari .

Karena file besar terus bertambah, apa yang bisa saya lakukan untuk membuat semua ini lebih cepat dan menghemat CPU? Saya ingin tahu apakah menyortir file dengan kuncinya (jika demikian, bagaimana?) Atau menggunakan db sebagai ganti teks biasa akan membantu ...

Teresa e Junior
sumber

Jawaban:

11

Jawaban ini didasarkan pada awkjawaban yang diposting oleh potong ..
Ini dua kali lebih cepat dari commmetode (pada sistem saya), untuk 6 juta baris yang sama dalam file-utama dan 10 ribu kunci ... (sekarang diperbarui untuk menggunakan FNR, NR)

Meskipun awklebih cepat dari sistem Anda saat ini, dan akan memberi Anda dan komputer Anda ruang bernapas, ketahuilah bahwa ketika pemrosesan data sekuat yang Anda jelaskan, Anda akan mendapatkan hasil keseluruhan terbaik dengan beralih ke basis data khusus; misalnya. SQlite, MySQL ...


awk '{ if (/^[^0-9]/) { next }              # Skip lines which do not hold key values
       if (FNR==NR) { main[$0]=1 }          # Process keys from file "mainfile"
       else if (main[$0]==0) { keys[$0]=1 } # Process keys from file "keys"
     } END { for(key in keys) print key }' \
       "mainfile" "keys" >"keys.not-in-main"

# For 6 million lines in "mainfile" and 10 thousand keys in "keys"

# The awk  method
# time:
#   real    0m14.495s
#   user    0m14.457s
#   sys     0m0.044s

# The comm  method
# time:
#   real    0m27.976s
#   user    0m28.046s
#   sys     0m0.104s

Peter.O
sumber
Ini cepat, tapi saya tidak mengerti banyak tentang awk: seperti apa nama file? Saya mencoba file1 -> mainfiledan file2 -> keysdengan gawk dan mawk, dan menghasilkan kunci yang salah.
Teresa e Junior
file1 memiliki kunci, nama, dan pekerjaan.
Teresa e Junior
'mainfile' adalah file besar (dengan kunci, nama, dan pekerjaan). Saya baru saja menyebutnya "mainfile 'karena saya terus-menerus bingung file mana yang mana (file1 vs file2) ..' kunci 'hanya berisi 10 ribu, atau berapa banyak, kunci .. Untuk situaton Anda JANGAN redirect anyting. .. cukup gunakan file1 file EOF2 Mereka adalah nama file Anda .. "EOF" adalah file 1-baris creadte oleh script untuk menunjukkan akhir dari file pertama (file data utama) dan awal dari file kedua ( . kunci) awkmemungkinkan Anda untuk membaca dalam serangkaian file .. dalam hal ini yang seri memiliki 3 file di dalamnya Output pergi ke.stdout
Peter.O
Script ini akan mencetak kunci apa saja yang ada di dalamnya mainfile, DAN itu juga akan mencetak kunci apa pun dari keysfile yang TIDAK ada di mainfile... Itu mungkin yang terjadi ... (Saya akan melihat sedikit lebih jauh ke dalamnya ...
Peter.O
Terima kasih, @ Peter.O! Karena file bersifat rahasia, saya mencoba membuat file sampel dengan $RANDOMuntuk diunggah.
Teresa e Junior
16

Masalahnya, tentu saja, adalah Anda menjalankan grep pada file besar 10.000 kali. Anda harus membaca kedua file hanya sekali. Jika Anda ingin tetap berada di luar bahasa skrip, Anda dapat melakukannya dengan cara ini:

  1. Ekstrak semua angka dari file 1 dan urutkan
  2. Ekstrak semua angka dari file 2 dan urutkan
  3. Jalankan commpada daftar yang diurutkan untuk mendapatkan apa yang ada di daftar kedua

Sesuatu seperti ini:

$ grep -o '^[0-9]\{12\}$' file1 | sort -u -o file1.sorted
$ grep -o  '[0-9]\{12\}'  file2 | sort -u -o file2.sorted
$ comm -13 file1.sorted file2.sorted > file3

Lihat man comm.

Jika Anda dapat memotong file besar setiap hari (seperti file log), Anda dapat menyimpan cache nomor yang diurutkan dan tidak perlu menguraikannya setiap saat.

angus
sumber
1
Rapi! 2 detik (pada drive yang tidak terlalu cepat) dengan 200.000 entri acak di mainfile (mis. 600.000 baris) dan 143.000 kunci acak (begitulah data pengujian saya berakhir) ... diuji, dan berfungsi (tetapi Anda tahu bahwa: ) ... Saya bertanya-tanya tentang {12}.. OP telah menggunakan 12, tetapi kunci contohnya 13 panjang ...
Peter.O
2
Hanya sedikit catatan, Anda dapat melakukannya tanpa berurusan dengan file sementara dengan menggunakan <(grep...sort)nama file tersebut.
Kevin
Terima kasih, tetapi mengambil dan menyortir file membutuhkan waktu lebih lama daripada loop saya sebelumnya (+ 2 menit.).
Teresa e Junior
@Teresa e Junior. Seberapa besar file utama Anda? ... Anda telah menyebutkan bahwa ia tumbuh pada 200.000 baris per hari, tetapi tidak seberapa besar ... Untuk mengurangi jumlah data yang perlu Anda proses, Anda dapat membaca hanya 200.000 baris hari ini dengan mencatat nomor baris terakhir diproses (kemarin) dan hanya digunakan tail -n +$linenumuntuk menampilkan data terbaru. Dengan begitu Anda hanya akan memproses sekitar 200.000 baris setiap hari .. Saya baru saja mengujinya dengan 6 juta baris dalam file-utama dan 10 ribu kunci ... waktu : 0m0.016s nyata, pengguna 0m0.008s, sys 0m0.008s
Peter.O
Aku benar-benar cukup bingung / ingin tahu tentang bagaimana Anda dapat grep file utama Anda 10.000 kali dan menemukan lebih cepat dari metode ini yang hanya greps itu sekali (dan sekali untuk jauh lebih kecil file1 ) ... Bahkan jika semacam Anda membutuhkan waktu lebih lama dari saya tes, saya hanya tidak bisa mendapatkan kepala saya di sekitar gagasan bahwa membaca file besar yang berkali-kali tidak lebih besar daripada satu jenis (waktu)
Peter.O
8

Ya, pasti menggunakan database. Mereka dibuat persis untuk tugas-tugas seperti ini.

Mika Fischer
sumber
Terima kasih! Saya tidak punya banyak pengalaman dengan database. Database mana yang Anda rekomendasikan? Saya sudah menginstal MySQL dan perintah sqlite3.
Teresa e Junior
1
Keduanya baik untuk ini, sqlite lebih sederhana karena pada dasarnya hanya sebuah file dan SQL API untuk mengaksesnya. Dengan MySQL, Anda perlu mengatur server MySQL untuk menggunakannya. Meskipun itu tidak terlalu sulit, sqlite mungkin yang terbaik untuk memulai.
Mika Fischer
3

Ini mungkin bekerja untuk Anda:

 awk '/^[0-9]/{a[$0]++}END{for(x in a)if(a[x]==1)print x}' file{1,2} >file3

EDIT:

Skrip yang diubah untuk memungkinkan duplikat dan kunci tidak dikenal di kedua file, masih menghasilkan kunci dari file pertama yang tidak ada di file kedua:

 awk '/^[0-9]/{if(FNR==NR){a[$0]=1;next};if($0 in a){a[$0]=2}}END{for(x in a)if(a[x]==1)print x}' file{1,2} >file3
potong
sumber
Ini akan kehilangan kunci baru yang terjadi lebih dari satu kali di file utama (dan dalam hal ini, yang terjadi lebih dari satu kali di file kunci) Tampaknya mengharuskan peningkatan jumlah array dari file utama tidak boleh melebihi 1, atau solusi yang setara (+1 karena cukup dekat dengan tanda)
Peter.O
1
Saya mencoba dengan melongo dan melongo, dan mengeluarkan kunci yang salah ...
Teresa e Junior
@ Peter.OI menganggap file utama memiliki kunci unik dan file 2 adalah subset dari file utama.
potong
@potong Yang kedua bekerja dengan baik dan sangat cepat! Terima kasih!
Teresa e Junior
@Teresa e Junior Apakah Anda yakin ini berfungsi dengan benar? .. Menggunakan data uji yang Anda berikan , yang akan menghasilkan 5.000 kunci, ketika saya menjalankannya, ia menghasilkan 136703 kunci, sama seperti yang saya dapatkan sampai saya akhirnya mengerti apa persyaratan Anda ... @potong Tentu saja! FNR == NR (Saya belum pernah menggunakannya sebelumnya :)
Peter.O
2

Dengan data sebanyak itu, Anda harus benar-benar beralih ke database. Sementara itu, satu hal yang harus Anda lakukan untuk mencapai kinerja yang layak adalah tidak mencari file1secara terpisah untuk setiap kunci. Jalankan tunggal grepuntuk mengekstrak semua kunci yang tidak dikecualikan sekaligus. Karena itu grepjuga mengembalikan garis yang tidak mengandung kunci, filter itu.

grep -o '[0-9]\{12\}' file2 |
grep -Fxv -f - file1 |
grep -vx '[0-9]\{12\}' >file3

( -FxBerarti mencari seluruh baris, secara harfiah -f -berarti membaca daftar pola dari input standar.)

Gilles 'SANGAT berhenti menjadi jahat'
sumber
Kecuali saya salah, ini tidak membahas masalah menyimpan kunci yang tidak ada dalam file besar, ini akan menyimpan kunci yang ada di dalamnya.
Kevin
@Kevin persis, dan ini telah memaksa saya untuk menggunakan loop.
Teresa e Junior
@TeresaeJunior: menambahkan -v( -Fxv) bisa mengurusnya.
Dijeda sampai pemberitahuan lebih lanjut.
@DennisWilliamson Itu akan memilih semua baris dalam file besar yang tidak cocok dengan apa pun di file kunci, termasuk nama, pekerjaan, dll.
Kevin
@ Kevin Terima kasih, saya salah membaca pertanyaan. Saya telah menambahkan filter untuk baris non-kunci, meskipun preferensi saya sekarang digunakancomm .
Gilles 'SANGAT berhenti menjadi jahat'
2

Ijinkan saya untuk memperkuat apa yang dikatakan orang lain, "Bawalah kamu ke database!"

Ada binari MySQL yang tersedia secara bebas untuk sebagian besar platform.

Kenapa tidak SQLite? Berbasis memori, memuat flat-file saat Anda memulainya, lalu menutupnya setelah Anda selesai. Ini berarti bahwa jika komputer Anda rusak atau proses SQLite hilang, demikian juga semua data.

Masalah Anda terlihat seperti hanya beberapa baris SQL, dan akan berjalan dalam milidetik!

Setelah menginstal MySQL (yang saya sarankan di atas pilihan lain), saya akan mengeluarkan $ 40 untuk SQL Cookbook O'Reilly dari Anthony Molinaro, yang memiliki banyak pola masalah, mulai dengan SELECT * FROM tablepertanyaan sederhana , dan melalui agregat dan beberapa gabungan.

Jan Steinman
sumber
Ya, saya akan mulai memigrasi data saya ke SQL dalam beberapa hari, terima kasih! Script awk telah banyak membantu saya sampai saya menyelesaikan semuanya!
Teresa e Junior
1

Saya tidak yakin apakah ini adalah hasil persis yang Anda cari, tetapi mungkin cara termudah adalah:

grep -o '[0-9]\{12\}' file2 | sed 's/.*/^&$/' > /tmp/numpatterns.grep
grep -vf /tmp/numpatterns.grep file1 > file3
rm -f /tmp/numpatterns.grep

Anda juga bisa menggunakan:

sed -ne '/.*\([0-9]\{12\}.*/^\1$/p' file2 > /tmp/numpatterns.grep
grep -vf /tmp/numpatterns.grep file1 > file3
rm -f /tmp/numpatterns.grep

Masing-masing membuat file pola sementara yang digunakan untuk mengumpulkan angka-angka dari file besar ( file1).

Arcege
sumber
Saya percaya ini juga menemukan angka yang ada di file besar, bukan yang tidak.
Kevin
Benar, saya tidak melihat '!' dalam OP. Hanya perlu menggunakan grep -vfsaja grep -f.
Arcege
2
Tidak @arcege, grep -vf tidak akan menampilkan kunci yang tidak cocok, itu akan menampilkan semuanya termasuk nama dan pekerjaan.
Teresa e Junior
1

Saya sepenuhnya setuju dengan Anda mendapatkan database (MySQL cukup mudah digunakan). Sebelum Anda menjalankannya, saya menyukai commsolusi Angus , tetapi begitu banyak orang yang mencoba grepdan membuat kesalahan sehingga saya pikir saya akan menunjukkan (atau setidaknya satu) cara yang benar untuk melakukannya grep.

grep -o '[0-9]\{12\}' keyfile | grep -v -f <(grep -o '^[0-9]\{12\}' bigfile) 

Yang pertama grepmendapatkan kunci. Yang ketiga grep(di <(...)) mengambil semua kunci yang digunakan dalam file besar, dan <(...)melewati seperti file sebagai argumen -fdalam grep kedua. Itu menyebabkan yang kedua grepmenggunakannya sebagai daftar garis yang cocok. Ini kemudian menggunakan ini untuk mencocokkan inputnya (daftar kunci) dari pipa (pertama grep), dan mencetak semua kunci yang diekstrak dari file kunci dan bukan ( -v) file besar.

Tentu saja Anda dapat melakukan ini dengan file sementara Anda harus melacak dan ingat untuk menghapus:

grep -o '[0-9]\{12\}'  keyfile >allkeys
grep -o '^[0-9]\{12\}' bigfile >usedkeys
grep -v -f usedkeys allkeys

Ini mencetak semua baris allkeysyang tidak muncul di usedkeys.

Kevin
sumber
Sayangnya itu lambat , dan saya mendapatkan kesalahan memori setelah 40 detik:grep: Memory exhausted
Peter.O
@ Peter.O Tapi itu benar. Bagaimanapun, itu sebabnya saya menyarankan database atau comm, dalam urutan itu.
Kevin
Ya itu bekerja, tetapi jauh lebih lambat daripada loop.
Teresa e Junior
1

File key tidak berubah? Maka Anda harus menghindari mencari entri lama lagi dan lagi.

Dengan tail -fAnda bisa mendapatkan output dari file yang sedang tumbuh.

tail -f growingfile | grep -f keyfile 

grep -f membaca pola dari file, satu baris sebagai pola.

Pengguna tidak diketahui
sumber
Itu bagus, tetapi file kuncinya selalu berbeda.
Teresa e Junior
1

Tidak akan memposting jawaban saya karena saya pikir jumlah data seperti itu tidak boleh diproses dengan skrip shell, dan jawaban yang tepat untuk menggunakan database sudah diberikan. Namun sejak sekarang ada 7 pendekatan lain ...

Membaca file pertama dalam memori, lalu mencari file kedua untuk angka dan memeriksa apakah nilai disimpan dalam memori. Seharusnya lebih cepat dari beberapa greps, jika Anda memiliki cukup memori untuk memuat seluruh file, yaitu.

declare -a record
while read key
do
    read name
    read job
    record[$key]="$name:$job"
done < file1

for number in $(grep -o '[0-9]\{12\}' file2)
do
    [[ -n ${mylist[$number]} ]] || echo $number >> file3
done
forcefsck
sumber
Saya punya cukup memori, tetapi saya menemukan ini lebih lambat. Terimakasih Meskipun!
Teresa e Junior
1

Saya setuju dengan @ jan-steinman bahwa Anda harus menggunakan database untuk tugas semacam ini. Ada banyak cara untuk meretas bersama solusi dengan skrip shell seperti jawaban lain tunjukkan, tetapi melakukannya dengan cara itu akan menyebabkan banyak kesengsaraan jika Anda akan menggunakan dan memelihara kode untuk jangka waktu lebih lama daripada hanya proyek membuang satu hari.

Dengan asumsi Anda berada di kotak Linux maka kemungkinan besar Anda telah menginstal Python secara default yang mencakup pustaka sqlite3 pada Python v2.5. Anda dapat memeriksa versi Python Anda dengan:

% python -V
Python 2.7.2+

Saya sarankan menggunakan pustaka sqlite3 karena ini adalah solusi berbasis file sederhana yang ada untuk semua platform (termasuk di dalam browser web Anda!) Dan tidak memerlukan server untuk diinstal. Pada dasarnya nol-konfigurasi dan nol-pemeliharaan.

Di bawah ini adalah skrip python sederhana yang akan mem-parsing format file yang Anda berikan sebagai contoh dan kemudian melakukan kueri "pilih semua" sederhana dan hasilkan semua yang disimpan dalam db.

#!/usr/bin/env python

import sqlite3
import sys

dbname = '/tmp/simple.db'
filename = '/tmp/input.txt'
with sqlite3.connect(dbname) as conn:
    conn.execute('''create table if not exists people (key integer primary key, name text, job text)''')
    with open(filename) as f:
        for key in f:
            key = key.strip()
            name = f.next().strip()
            job = f.next().strip()
            try:
                conn.execute('''insert into people values (?,?,?)''', (key, name, job))
            except sqlite3.IntegrityError:
                sys.stderr.write('record already exists: %s, %s, %s\n' % (key, name, job))
    cur = conn.cursor()

    # get all people
    cur.execute('''select * from people''')
    for row in cur:
        print row

    # get just two specific people
    person_list = [1358726575123, 9973834728345]
    cur.execute('''select * from people where key in (?,?)''', person_list)
    for row in cur:
        print row

    # a more general way to get however many people are in the list
    person_list = [1358726575123, 9973834728345]
    template = ','.join(['?'] * len(person_list))
    cur.execute('''select * from people where key in (%s)''' % (template), person_list)
    for row in cur:
        print row

Ya, ini berarti Anda harus belajar beberapa SQL , tetapi itu akan sangat bermanfaat dalam jangka panjang. Selain itu, alih-alih mem-parsing file log Anda, mungkin Anda bisa menulis data langsung ke database sqlite Anda.

aculich
sumber
Terima kasih untuk skrip python! Saya pikir /usr/bin/sqlite3bekerja dengan cara yang sama untuk skrip shell ( packages.debian.org/squeeze/sqlite3 ), meskipun saya belum pernah menggunakannya.
Teresa e Junior
Ya, Anda dapat menggunakan /usr/bin/sqlite3skrip shell, namun saya sarankan menghindari skrip shell kecuali untuk program membuang sederhana dan alih-alih menggunakan bahasa seperti python yang memiliki penanganan kesalahan yang lebih baik dan lebih mudah untuk mempertahankan dan tumbuh.
aculich