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?
6
A
Trả lời
5
4
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
Các vấn đề liên quan
- 1. Có cách nào để đánh giá số lần biểu thức chính quy Perl đã khớp không?
- 2. Biểu thức chính quy của Python
- 3. Biểu thức chính quy của Python HOẶC
- 4. Biểu thức chính quy của Python không khớp với
- 5. biểu thức chính quy python để chia đoạn văn
- 6. Tại sao Python đánh giá biểu thức này không chính xác?
- 7. JFormattedTextField sử dụng định dạng biểu thức chính quy?
- 8. Biểu thức chính quy JavaScript
- 9. Đánh giá biểu thức có điều kiện
- 10. Đánh giá biểu thức toán
- 11. Python - Đánh giá biểu thức toán học trong chuỗi
- 12. giá trị chiết xuất sử dụng biểu thức chính quy trong mysql
- 13. Python sử dụng kết quả của hàm cho Thay đổi Biểu thức Chính quy
- 14. Làm cách nào để sử dụng biến trong biểu thức chính quy?
- 15. Biểu thức chính quy không tuân thủ
- 16. Cây đánh giá biểu thức trong Haskell
- 17. Làm sạch các biểu thức chính quy của Python
- 18. Biểu thức chính quy của Python với mã số
- 19. Thư viện để kiểm tra xem hai biểu thức chính quy có bằng nhau/đẳng cấu
- 20. Biểu thức chính quy để tìm các không gian
- 21. Nội tuyến để đánh giá biểu thức
- 22. Có sử dụng Biểu thức chính quy nhanh hơn IndexOf không?
- 23. biểu thức chính quy không có ký tự
- 24. Cụm từ thông dụng để tìm biểu thức chính quy?
- 25. Biểu thức chính quy Javascript cho giá trị rgb
- 26. Đánh giá biểu thức C
- 27. Cách phân loại/phân loại chuỗi theo quy tắc biểu thức chính quy trong Python
- 28. Tại sao không có tiêu chuẩn biểu thức chính quy?
- 29. tách một chuỗi có thoát khỏi chuỗi sử dụng biểu thức chính quy trong Java
- 30. Cần biểu thức chính quy để xác nhận tên
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