Có ai biết nếu Python (bất kỳ phiên bản nào) đã sử dụng NFA (Tự động xác định hữu hạn) để đánh giá các biểu thức thông thường hoặc sử dụng một số cơ chế khác không? Vui lòng cung cấp liên kết/tham chiếu nếu có.Python có sử dụng NFA để đánh giá biểu thức chính quy trong mô-đun không?
này nên mất ít hơn một ms trên DFA:
$ time python3 -c 'import re; re.match("a?"*25+"a"*25, "a"*25)'
real 0m7.273s
đổi 25 với 100 và nó sẽ không chấm dứt cho một đời.
Sau đây là cách nó trông giống trên DFA (grep):
$ time echo "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" |grep "a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
real 0m0.063s
Có một cuộc thảo luận vĩ đại của chủ đề này tại http://swtch.com/~rsc/regexp/regexp1.html
Vì hầu hết động cơ RE hiện nay cho phép ngôn ngữ không phải thường xuyên để được xuất hiện Tôi nghi ngờ bất kỳ động cơ RE hiện đại nào thực sự vẫn sử dụng NFA hoặc DFA nữa. – Joey
Vâng, vì một công cụ RE có thể xác định một tập hợp con của RE là thường xuyên, và chúng được sử dụng phổ biến, nó có ý nghĩa để tối ưu hóa cho những tình huống đó. Vì vậy, hoàn toàn có thể là họ _sometimes_ sử dụng NFA hoặc DFA. – MSalters