Có tốt hơn khi sử dụng trình độ không tham lam hoặc một lookahead?

Question

Tôi có một khối văn bản có thể lớn để tìm kiếm các phiên bản [[...]], trong đó ... có thể là bất kỳ thứ gì, kể cả các dấu ngoặc khác (mặc dù chúng không thể lồng nhau; trường hợp đầu tiên là ]] sau [[ kết thúc trận đấu).

tôi có thể nghĩ đến hai cách để phù hợp với văn bản này:

• Sử dụng khuôn khổ vòng loại không tham lam: /\[\[.+?\]\]/
• Sử dụng một lookahead: /\[\[(?:(?!\]\]).)+\]\]/

là một sự lựa chọn vốn đã tốt hơn so với khác, từ một quan điểm hiệu suất (tôi muốn nói đầu tiên có lẽ là dễ đọc hơn)? Tôi nhớ lại đọc rằng tốt hơn là không sử dụng các vòng loại không tham lam, nhưng tôi không thể tìm thấy nguồn cho điều đó ngay bây giờ.

Answer 1

Tốt hơn nên sử dụng bộ định lượng không tham lam trong trường hợp này.

Hãy chuỗi ví dụ này "[[a]b]]"

không tham lam lượng hóa

 
     \[\[.+?\]\] 
Atom # 1 2 3 4 5 

1. Atom # 1 \[ trận
2. Atom # 2 \[ trận
3. Atom # 3 .+? phù hợp với "a"
4. Atom # 4 \] trận
5. Atom # 5 \] thất bại, trở lại # 3 nhưng giữ vị trí chuỗi
6. Atom # 3 .+? phù hợp với "]"
7. Atom # 4 \] thất bại, trở lại # 3 nhưng giữ vị trí chuỗi
8. Atom # 3 .+? phù hợp với "b"
9. Atom # 4 \] trận
10. Atom # 5 \] trận
11. thành công

Look-ahead:

 
     \[\[(?:(?!\]\]).)+\]\] 
Atom # 1 2 3 4  5 6 7 

1. Atom # 1 \[ trận
2. Atom # 2 \[ trận
3. Atom # 4 (?!\]\]) thành công (ví dụ:không phù hợp) ngay tại "a", đi trên
4. Atom # 5 . phù hợp với "a", lặp lại ở vị trí thứ 3
5. Atom # 4 (?!\]\]) đạt được trận đấu phần tại "]"
6. Atom # 4 (?!\]\]) thành công (tức là không phù hợp) tại "b", đi trên
7. Atom # 5 . phù hợp với "]", lặp lại ở vị trí thứ 3
8. Atom # 4 (?!\]\]) thành công (tức là không phù hợp) ngay tại "b", đi trên
9. Atom # 5 . phù hợp với "b", lặp lại ở vị trí thứ 3
10. Atom # 4 (?!\]\]) đạt được trận đấu phần tại "]"
11. Atom # 4 (?!\]\]) đạt được trận đấu đầy đủ tại "]", ergo: # 4 thất bại, lối ra # 3
12. Atom # 6 \] trận
13. Atom # 7 \] trận
14. thành công

Vì vậy, có vẻ như người định lượng không tham lam có ít việc phải làm hơn.

Tuyên bố từ chối trách nhiệm: Đây là ví dụ nhân tạo và hiệu suất thực tế có thể khác nhau, tùy thuộc vào đầu vào, biểu thức thực tế và triển khai công cụ regex. Tôi chỉ 98% chắc chắn rằng những gì tôi vạch ra ở đây là những gì đang thực sự xảy ra, vì vậy tôi mở cửa để sửa chữa. Ngoài ra, như với tất cả các mẹo hiệu suất, không thực hiện điều này theo giá trị khuôn mặt, thực hiện so sánh điểm chuẩn của riêng bạn nếu bạn muốn biết chắc chắn.

Answer 2

Tôi nghĩ tốt hơn là nên sử dụng vòng loại không tham lam. Bạn có chắc chắn rằng bài viết bạn đã đọc không nói "cẩn thận với tham lam phù hợp không?"

Answer 3

Một biến thể: /\[\[((?:\]?[^]])+)]]/

Nó sử dụng không quantifiers không tham lam cũng không trông-aheads. Nó cho phép một đơn ] trước bất kỳ số nào không ]. Nếu có hai dãy số ], sự lặp lại bên trong sẽ dừng lại và trận đấu sẽ kết thúc.

Mẫu này sẽ là cách tốt nhất để sử dụng với công cụ biên dịch regex của FSA. Trên các công cụ theo dõi ngược lại, nó có thể chậm hơn so với biến thể không tham lam.

Answer 4

Bạn đang sử dụng hương vị regex nào? Nếu đó là một hỗ trợ quantifiers sở hữu, có một sự thay thế tốt hơn nhiều:

\[\[(?:[^\]]++|\](?!\]))*+\]\] 

[^\]]++ gobbles lên bất kỳ nhân vật khác hơn ] và không bận tâm lưu thông tin trạng thái mà có thể làm thụt lùi càng tốt. Nếu nó nhìn thấy một ], nó thực hiện một lookahead để xem nếu có khác. Bao bọc toàn bộ điều trong một định lượng sở hữu khác có nghĩa là nó chỉ thực hiện một tra cứu bất cứ khi nào nó nhìn thấy một ] và nó chỉ phát lại một lần: khi nó tìm thấy kết thúc ]].

Các bộ định lượng sở hữu được hỗ trợ bởi các định dạng Java, JGSoft, PCRE (PHP), Oniguruma (Ruby 1.9) và Perl 5.12.Tất cả những hương vị đó cũng hỗ trợ các nhóm nguyên tử, có thể được sử dụng để đạt được hiệu quả tương tự:

\[\[(?>(?:(?>[^\]]+)|\](?!\]))*)\]\] 

Hương vị .NET hỗ trợ các nhóm nguyên tử nhưng không phải là định lượng sở hữu.