Python, cách nhanh nhất để lặp lại các cụm từ thông dụng nhưng dừng trên kết quả đầu tiên

Question

Tôi có hàm trả về Đúng nếu chuỗi khớp với ít nhất một biểu thức chính quy trong một danh sách và Sai khác. Chức năng này được gọi là thường đủ để hiệu suất là một vấn đề.

Khi chạy thông qua cProfile, hàm này chi tiêu khoảng 65% số thời gian thực hiện các kết quả phù hợp và 35% thời gian của nó lặp lại trong danh sách.

Tôi nghĩ sẽ có cách để sử dụng map() hoặc một cái gì đó nhưng tôi không thể nghĩ cách để nó dừng lặp lại sau khi tìm thấy kết quả phù hợp.

Có cách nào để thực hiện chức năng nhanh hơn trong khi vẫn trả lại hàm khi tìm thấy kết quả khớp đầu tiên không?

def matches_pattern(str, patterns): 
    for pattern in patterns: 
     if pattern.match(str): 
      return True 
    return False 

Answer 1

Việc đầu tiên mà nói đến cái tâm đang đẩy vòng sang phía bên C bằng cách sử dụng một biểu thức máy phát điện:

def matches_pattern(s, patterns): 
    return any(p.match(s) for p in patterns) 

Có lẽ bạn không thậm chí cần một chức năng riêng biệt cho điều đó.

Một điều bạn nên thử là xây dựng một regex phức hợp bằng cách sử dụng toán tử luân phiên | để động cơ có cơ hội tối ưu hóa nó cho bạn. Bạn cũng có thể tạo regex động từ danh sách các mẫu chuỗi, nếu điều này là cần thiết:

def matches_pattern(s, patterns): 
    return re.match('|'.join('(?:%s)' % p for p in patterns), s) 

Tất nhiên bạn cần phải có regex ở dạng chuỗi để hoạt động. Chỉ cần cấu hình cả hai loại này và kiểm tra xem cái nào nhanh hơn :)

Bạn cũng có thể muốn xem một số general tip for debugging regular expressions in Python. Điều này cũng có thể giúp tìm cơ hội để tối ưu hóa.

UPDATE: Tôi đã tò mò và đã viết một chút chuẩn:

import timeit 

setup = """ 
import re 
patterns = [".*abc", "123.*", "ab.*", "foo.*bar", "11010.*", "1[^o]*"]*10 
strings = ["asdabc", "123awd2", "abasdae23", "fooasdabar", "111", "11010100101", "xxxx", "eeeeee", "dddddddddddddd", "ffffff"]*10 
compiled_patterns = list(map(re.compile, patterns)) 

def matches_pattern(str, patterns): 
    for pattern in patterns: 
     if pattern.match(str): 
      return True 
    return False 

def test0(): 
    for s in strings: 
     matches_pattern(s, compiled_patterns) 

def test1(): 
    for s in strings: 
     any(p.match(s) for p in compiled_patterns) 

def test2(): 
    for s in strings: 
     re.match('|'.join('(?:%s)' % p for p in patterns), s) 

def test3(): 
    r = re.compile('|'.join('(?:%s)' % p for p in patterns)) 
    for s in strings: 
     r.match(s) 
""" 

import sys 
print(timeit.timeit("test0()", setup=setup, number=1000)) 
print(timeit.timeit("test1()", setup=setup, number=1000)) 
print(timeit.timeit("test2()", setup=setup, number=1000)) 
print(timeit.timeit("test3()", setup=setup, number=1000)) 

Sản lượng trên máy tính của tôi:

1.4120500087738037 
1.662621021270752 
4.729579925537109 
0.1489570140838623 

Vì vậy any dường như không thể nhanh hơn so với cách tiếp cận ban đầu của bạn . Xây dựng một regex động cũng không thực sự nhanh. Nhưng nếu bạn có thể quản lý để xây dựng một regex trả trước và sử dụng nó nhiều lần, điều này có thể dẫn đến hiệu suất tốt hơn. Bạn cũng có thể điều chỉnh điểm chuẩn này để kiểm tra một số tùy chọn khác :)

Answer 2

Cách để làm điều này nhanh nhất là kết hợp tất cả các regexes thành một với "|" giữa chúng, sau đó đưa ra một cuộc gọi trận đấu regex. Ngoài ra, bạn sẽ muốn biên dịch nó một lần để chắc chắn rằng bạn đang tránh lặp lại biên dịch regex.

Ví dụ:

def matches_pattern(s, pats): 
    pat = "|".join("(%s)" % p for p in pats) 
    return bool(re.match(pat, s)) 

này là dành cho pats như dây đàn, không được biên dịch mẫu. Nếu bạn thực sự chỉ có regexes biên soạn, sau đó:

def matches_pattern(s, pats): 
    pat = "|".join("(%s)" % p.pattern for p in pats) 
    return bool(re.match(pat, s)) 

Answer 3

Thêm vào các câu trả lời tuyệt vời ở trên, đảm bảo bạn so sánh đầu ra của lại.phù hợp với Không:

>>> timeit('None is None') 
0.03676295280456543 
>>> timeit('bool(None)') 
0.1125330924987793 
>>> timeit('re.match("a","abc") is None', 'import re') 
1.0200879573822021 
>>> timeit('bool(re.match("a","abc"))', 'import re') 
1.134294033050537