Pertanyaan Kecepatan banyak ekspresi reguler dalam python


Saya menulis program python yang berhubungan dengan sejumlah string / file. Masalah saya adalah bahwa saya akan disajikan dengan teks yang cukup pendek, dan saya akan perlu mencari contoh-contoh dari berbagai kata / frasa yang cukup luas.

Saya pikir saya perlu menyusun ekspresi reguler sebagai cara mencocokkan kata-kata / frasa ini dalam teks. Perhatian saya, bagaimanapun, adalah bahwa ini akan memakan banyak waktu.

Pertanyaan saya adalah seberapa cepat proses berulang kali menyusun ekspresi reguler, dan kemudian mencari melalui kumpulan teks kecil untuk menemukan kecocokan? Apakah saya lebih baik menggunakan beberapa metode string?

Edit: Jadi, saya kira contoh pertanyaan saya adalah: Seberapa mahal untuk mengkompilasi dan mencari dengan satu ekspresi reguler versus mengatakan, mengulang kata 'jika' "dalam string" katakan, 5 kali?


4
2017-11-23 11:32


asal


Jawaban:


Jika kecepatan adalah esensi, Anda lebih baik menjalankan beberapa tes sebelum Anda memutuskan bagaimana kode aplikasi produksi Anda.

Pertama-tama, Anda mengatakan bahwa Anda mencari kata-kata yang menunjukkan bahwa Anda mungkin dapat melakukan ini menggunakan split () untuk memecah string pada spasi. Dan kemudian gunakan perbandingan string sederhana untuk melakukan pencarian Anda.

Pasti melakukan kompilasi ekspresi reguler Anda dan lakukan tes waktu membandingkannya dengan fungsi string biasa. Periksa dokumentasi untuk kelas string untuk daftar lengkap.


5
2017-11-23 11:38



Anda harus mencoba untuk mengkompilasi semua regexps Anda menjadi satu dengan menggunakan | operator. Dengan begitu, mesin regexp akan melakukan sebagian besar pengoptimalan untuk Anda. Gunakan operator pengelompokan () untuk menentukan pencocokan regexp mana.


5
2017-11-23 11:59



Kebutuhan Anda tampaknya mencari teks untuk kemunculan pertama dari salah satu dari kumpulan string. Mungkin Anda kemudian ingin memulai kembali pencarian untuk menemukan kejadian berikutnya, dan seterusnya sampai string yang dicari habis. Hanya perbandingan string lama yang biasa saja yang terlibat.

Algoritme klasik untuk tugas ini adalah Aho-Corasick untuk yang ada Ekstensi Python (ditulis dalam C). Ini harus mengalahkan kaus kaki dari segala alternatif yang menggunakan re modul.


3
2017-11-23 13:01



Jika Anda ingin tahu bagaimana cara cepat selama menyusun pola regex, Anda perlu untuk membandingkannya.

Di sini adalah bagaimana saya melakukannya. Ini mengkompilasi 1 Juta waktu setiap pola.

import time,re

def taken(f):
 def wrap(*arg):
  t1,r,t2=time.time(),f(*arg),time.time()
  print t2-t1,"s taken"
  return r
 return wrap

@taken
def regex_compile_test(x):
 for i in range(1000000):
  re.compile(x)
 print "for",x,

#sample tests
regex_compile_test("a")
regex_compile_test("[a-z]")
regex_compile_test("[A-Z0-9._%+-]+@[A-Z0-9.-]+\.[A-Z]{2,4}")

Butuh waktu sekitar 5 menit untuk setiap pola di komputer saya.

for a 4.88999986649 s taken
for [a-z] 4.70300006866 s taken
for [A-Z0-9._%+-]+@[A-Z0-9.-]+\.[A-Z]{2,4} 4.78200006485 s taken

Bottleneck sebenarnya tidak dalam pola kompilasi, dalam mengekstraksi teks seperti re.findall, mengganti re.sub. Jika Anda menggunakannya terhadap beberapa teks MB, itu cukup lambat.

Jika teks Anda diperbaiki, gunakan str.find normal, lebih cepat daripada regex.

Sebenarnya, jika Anda memberikan contoh teks Anda, dan sampel pola regex Anda, kami dapat memberi Anda ide yang lebih baik, ada banyak regex yang hebat, dan orang-orang python di luar sana.

Harap bantuan ini, maaf jika jawaban saya tidak bisa membantu Anda.


2
2017-11-23 12:16



Ketika Anda mengkompilasi regexp, itu diubah menjadi representasi mesin negara. Asalkan regexp dinyatakan secara efisien, seharusnya tetap sangat cepat untuk dicocokkan. Kompilasi regexp bisa mahal, jadi Anda harus melakukannya di depan, dan sesedikit mungkin. Namun akhirnya, hanya Anda yang bisa menjawab jika cukup cepat untuk kebutuhan Anda.

Ada pendekatan pencarian string lainnya, seperti Algoritma Boyer-Moore. Tapi saya bertaruh kerumitan mencari beberapa string terpisah jauh lebih tinggi daripada regexp yang dapat mematikan setiap karakter berturut-turut.


1
2017-11-23 11:41



Ini adalah pertanyaan yang mudah dijawab dengan hanya mencobanya.

>>> import re
>>> import timeit
>>> find = ['foo', 'bar', 'baz']
>>> pattern = re.compile("|".join(find))
>>> with open('c:\\temp\\words.txt', 'r') as f:
        words = f.readlines()

>>> len(words)
235882
>>> timeit.timeit('r = filter(lambda w: any(s for s in find if w.find(s) >= 0), words)', 'from __main__ import find, words', number=30)
18.404569854548527
>>> timeit.timeit('r = filter(lambda w: any(s for s in find if s in w), words)', 'from __main__ import find, words', number=30)
10.953313759150944
>>> timeit.timeit('r = filter(lambda w: pattern.search(w), words)', 'from __main__ import pattern, words', number=30)
6.8793022576891758

Sepertinya Anda dapat mengharapkan ekspresi reguler lebih cepat daripada menggunakan find atau in. Meskipun jika saya adalah Anda, saya akan mengulangi tes ini dengan kasus yang lebih seperti data Anda yang sebenarnya.


1
2017-11-23 18:23



Jika Anda hanya mencari substring tertentu, gunakan str.find() sebagai gantinya.


0
2017-11-23 11:35