regex '|' toán tử vs chạy riêng biệt cho mỗi biểu thức con

Question

Tôi có một chuỗi khá lớn (~ 700k) mà tôi cần chạy 10 regex và đếm tất cả các kết quả phù hợp của bất kỳ regex nào. Impl của tôi nhanh chóng và bẩn thỉu là để làm một cái gì đó như re.search ('(expr1) | (expr2) | ...'), nhưng tôi đã tự hỏi nếu chúng ta sẽ thấy bất kỳ lợi ích hiệu suất bằng cách kết hợp trong một vòng thay thế:

Nói cách khác, tôi muốn so sánh hiệu suất của:

def CountMatchesInBigstring(bigstring, my_regexes): 
    """Counts how many of the expressions in my_regexes match bigstring.""" 
    count = 0 
    combined_expr = '|'.join(['(%s)' % r for r in my_regexes]) 
    matches = re.search(combined_expr, bigstring) 
    if matches: 
    count += NumMatches(matches) 
    return count 

vs

def CountMatchesInBigstring(bigstring, my_regexes): 
    """Counts how many of the expressions in my_regexes match bigstring.""" 
    count = 0 
    for reg in my_regexes: 
    matches = re.search(reg, bigstring) 
    if matches: 
     count += NumMatches(matches) 
    return count 

tôi sẽ dừng lại lười biếng và chạy một số xét nghiệm vào ngày mai (và gửi kết quả), nhưng tôi tự hỏi cho dù câu trả lời sẽ nhảy ra cho một người thực sự hiểu làm thế nào regexes làm việc :)

Answer 1

Tôi nghi ngờ rằng regex cũng sẽ làm những gì bạn đang cố gắng làm ... chỉ tốt hơn nhiều :)

do đó, "|" sẽ giành chiến thắng

Answer 2

Hai điều sẽ cho kết quả hơi khác một chút, trừ khi nó được đảm bảo rằng một trận đấu sẽ khớp với một và chỉ một regex. Nếu không, nếu một cái gì đó phù hợp với 2 nó sẽ được tính hai lần. Về lý thuyết, giải pháp của bạn phải nhanh hơn (nếu biểu thức loại trừ lẫn nhau) vì trình biên dịch regex phải có khả năng tạo ra một máy tìm kiếm trạng thái hiệu quả hơn, vì vậy chỉ cần một pass. Tôi mong đợi sự khác biệt là nhỏ, mặc dù, trừ khi các biểu thức rất giống nhau.

Ngoài ra, nếu nó là một chuỗi lớn (lớn hơn 700k) có thể có được lợi ích từ việc thực hiện một lần, và do đó, một yếu tố của n ít trao đổi bộ nhớ sẽ là cần thiết (để đĩa hoặc bộ nhớ cache CPU).

Đặt cược của tôi là trong các thử nghiệm của bạn, điều này thực sự không đáng chú ý. Tôi quan tâm đến kết quả thực tế - vui lòng đăng kết quả.

Answer 3

Tôi đồng ý với amartynov nhưng tôi muốn thêm rằng bạn cũng có thể cân nhắc việc biên dịch regex trước (re.compile()), đặc biệt. trong phiên bản thứ hai, bạn có thể tiết kiệm thời gian thiết lập trong vòng lặp. Có lẽ bạn có thể đo lường điều này là tốt trong khi bạn đang ở trên đó.

Lý do tôi nghĩ rằng ảnh chụp hoạt động tốt hơn là tôi giả định rằng nó được thực hiện đầy đủ trong không gian C và không quá nhiều mã python cần phải được diễn giải.

Nhưng mong đợi các con số.

Answer 4

Một biên dịch đơn và tìm kiếm sẽ mang lại kết quả nhanh hơn, trên thang điểm biểu thức thấp hơn, độ lợi có thể không đáng kể nhưng bạn càng chạy qua mức tăng lớn hơn. Hãy suy nghĩ về nó như là biên dịch một lần và phù hợp vs biên dịch 10 lần và phù hợp.

Answer 5

tôi tin rằng thực hiện đầu tiên bạn sẽ nhanh hơn:

• Một trong những nguyên tắc quan trọng để thực hiện Python là "di chuyển logic để mức độ C" - có nghĩa là chức năng built-in (viết bằng C) được nhanh hơn hơn là triển khai thực hiện Python thuần túy. Vì vậy, khi vòng lặp được thực hiện bởi mô-đun Regex tích hợp, cần nhanh hơn
• Một regex có thể tìm kiếm nhiều pattens trong một lần, nghĩa là nó chỉ chạy qua nội dung tệp của bạn một lần, trong khi nhiều regex sẽ có để đọc toàn bộ tập tin nhiều lần.

Answer 6

Để hiểu cách mô-đun hoạt động - biên dịch _sre.c trong chế độ gỡ lỗi (đặt # define VERBOSE tại 103 dòng trong _sre.c và biên dịch lại python). Sau này bạn bị bệnh thấy một cái gì đó như thế này:

 

>>> import re 
>>> p = re.compile('(a)|(b)|(c)') 
>>> p.search('a'); print '\n\n'; p.search('b') 
|0xb7f9ab10|(nil)|SEARCH 
prefix = (nil) 0 0 
charset = (nil) 
|0xb7f9ab1a|0xb7fb75f4|SEARCH 
|0xb7f9ab1a|0xb7fb75f4|ENTER 
allocating sre_match_context in 0 (32) 
allocate/grow stack 1064 
|0xb7f9ab1c|0xb7fb75f4|BRANCH 
allocating sre_match_context in 32 (32) 
|0xb7f9ab20|0xb7fb75f4|MARK 0 
|0xb7f9ab24|0xb7fb75f4|LITERAL 97 
|0xb7f9ab28|0xb7fb75f5|MARK 1 
|0xb7f9ab2c|0xb7fb75f5|JUMP 20 
|0xb7f9ab56|0xb7fb75f5|SUCCESS 
discard data from 32 (32) 
looking up sre_match_context at 0 
|0xb7f9ab1c|0xb7fb75f4|JUMP_BRANCH 
discard data from 0 (32) 
|0xb7f9ab10|0xb7fb75f5|END 




|0xb7f9ab10|(nil)|SEARCH 
prefix = (nil) 0 0 
charset = (nil) 
|0xb7f9ab1a|0xb7fb7614|SEARCH 
|0xb7f9ab1a|0xb7fb7614|ENTER 
allocating sre_match_context in 0 (32) 
allocate/grow stack 1064 
|0xb7f9ab1c|0xb7fb7614|BRANCH 
allocating sre_match_context in 32 (32) 
|0xb7f9ab20|0xb7fb7614|MARK 0 
|0xb7f9ab24|0xb7fb7614|LITERAL 97 
discard data from 32 (32) 
looking up sre_match_context at 0 
|0xb7f9ab1c|0xb7fb7614|JUMP_BRANCH 
allocating sre_match_context in 32 (32) 
|0xb7f9ab32|0xb7fb7614|MARK 2 
|0xb7f9ab36|0xb7fb7614|LITERAL 98 
|0xb7f9ab3a|0xb7fb7615|MARK 3 
|0xb7f9ab3e|0xb7fb7615|JUMP 11 
|0xb7f9ab56|0xb7fb7615|SUCCESS 
discard data from 32 (32) 
looking up sre_match_context at 0 
|0xb7f9ab2e|0xb7fb7614|JUMP_BRANCH 
discard data from 0 (32) 
|0xb7f9ab10|0xb7fb7615|END 

>>>          
 

Answer 7

Càng ít càng tốt: Nó sẽ chỉ sử dụng nhiều bộ nhớ hơn, thường không phải là vấn đề.

Nếu bất cứ điều gì có thể được để thông dịch viên xử lý, nó sẽ luôn tìm ra giải pháp nhanh hơn (cả về thời gian thực hiện và thời gian thực hiện) so với đối tác điển hình của con người.