Thao tác chuỗi vs Regexps

Question

Chúng tôi thường được thông báo rằng Regexps chậm và nên tránh bất cứ khi nào có thể.

Tuy nhiên, có tính đến các chi phí làm một số chuỗi thao tác chính mình ( không nói về sai lầm thuật toán - đây là một vấn đề khác nhau), đặc biệt là trong PHP hoặc Perl (có thể Java) các hạn là gì, trong trường hợp nào chúng ta có thể xem xét thao tác chuỗi là một lựa chọn tốt hơn? Regexps nào đặc biệt là CPU tham lam?

Ví dụ, đối với những điều sau đây, trong C++, Java, PHP hoặc Perl, những gì bạn muốn giới thiệu

Các regexps có lẽ sẽ nhanh hơn:

• s/abc/def/g hoặc một giải pháp dựa ... while((i=index("abc",$x)>=0) ...$y .= substr()...?
• s/(\d)+/N/g hay một thuật toán quét

Nhưng những gì về

• một email xác nhận regexp?
• s/((0|\w)+?[xy]*[^xy]){2,7}/u/g

sẽ không phải là một thủ công và thuật toán cụ thể được nhanh hơn (thời gian nữa để viết)?

chỉnh sửa

Mấu chốt của vấn đề là để xác định những loại regexp tốt hơn sẽ được viết lại đặc biệt cho một vấn đề nhất định thông qua thao tác chuỗi?

edit2

Một thực hiện chung là Perl regexp. Ví dụ trong Perl - đòi hỏi phải biết làm thế nào chúng được thực hiện - những gì loại của regexp là để tránh, bởi vì việc thực hiện sẽ làm cho quá trình dài và không hiệu quả? Nó có thể không phải là một regexp phức tạp ...

chỉnh sửa tháng 7 năm 2011 (dựa trên ý kiến)

Tôi không nói rằng tất cả regexps chậm. Một số mẫu regexps cụ thể được biết là chậm, do việc xử lý cụ thể của chúng và do việc thực hiện chúng. Ví dụ:
Trong các triển khai Perl/PHP gần đây, những gì được biết là khá chậm - và nên tránh?
Câu trả lời được mong đợi từ những người đã nghiên cứu riêng của họ (profiler ...) và những người có thể cung cấp một loại hướng dẫn chung về những gì được đề nghị/để tránh.

Answer 1

Một tính năng thú vị của thao tác văn bản với cụm từ thông dụng là các mẫu có mức cao và khai báo. Điều này khiến cho việc triển khai phòng đáng kể cho việc tối ưu hóa như bao thanh toán tiền tố chung dài nhất hoặc sử dụng Boyer-Moore cho các chuỗi tĩnh. Ký hiệu ngắn gọn giúp các chuyên gia đọc nhanh hơn. Tôi hiểu ngay lập tức những gì

if (s/^(.)//) { 
    ... 
} 

đang hoạt động và index($_, 0, 1) = "" có vẻ hơi ồn.

Thay vì giới hạn dưới, việc xem xét quan trọng đối với cụm từ thông dụng là giới hạn trên. Đó là một công cụ mạnh mẽ, vì vậy mọi người tin rằng nó có khả năng trích xuất chính xác mã thông báo từ XML, địa chỉ email hoặc các chương trình C++ và không nhận ra rằng một công cụ mạnh mẽ hơn như trình phân tích cú pháp là cần thiết.

Answer 2

Ai nói regexes chậm? Ít nhất trong Perl họ có xu hướng là phương pháp ưa thích của thao tác dây.

Các quy định không tốt về một số thứ như xác thực email vì chủ đề quá phức tạp, không phải vì chúng chậm. A proper email validation regex dài hơn 6.000 ký tự và thậm chí không xử lý tất cả các trường hợp (trước tiên bạn phải loại bỏ các nhận xét).

Ít nhất trong Perl 5, nếu nó có ngữ pháp, có lẽ không nên phân tích cú pháp bằng một regex.

Bạn cũng nên viết lại regex làm chức năng tùy chỉnh nếu regex đã phát triển đến mức nó không thể duy trì dễ dàng nữa (xem ví dụ xác thực email trước) hoặc hồ sơ cho thấy regex là thành phần chậm của mã .

Bạn dường như quan tâm đến tốc độ của regex so với thuật toán tùy chỉnh, nhưng đó không phải là mối quan tâm hợp lệ cho đến khi bạn chứng minh rằng đó là với một trình lược tả. Viết mã theo cách duy trì nhất. Nếu một regex là rõ ràng, sau đó sử dụng một regex. Nếu thuật toán tùy chỉnh rõ ràng, thì hãy sử dụng thuật toán tùy chỉnh. Nếu bạn thấy rằng hoặc là ăn lên rất nhiều thời gian sau khi profiling mã của bạn, sau đó bắt đầu tìm kiếm lựa chọn thay thế.

Answer 3

Cụm từ thông dụng sẽ không bao giờ nhanh hơn thuật toán được tạo thủ công cho một mục đích rất cụ thể. Tệ hơn nữa, trong PHP chúng phải được biên dịch lần đầu tiên chúng được sử dụng (một bộ nhớ đệm được sử dụng sau đó).

Tuy nhiên, chúng chắc chắn gọn gàng hơn. Hơn nữa, việc viết các thuật toán tùy chỉnh thường chậm hơn regex vì công cụ biểu thức thông thường thường được thực hiện ở một ngôn ngữ cấp thấp hơn, với ít chi phí hơn trong các chức năng gọi, v.v.

Ví dụ, preg_replace('/a/', 'b', $string) gần như chắc chắn sẽ nhanh hơn vòng lặp PHP thông qua chuỗi. Nhưng đây là một hình phạt liên tục trong thời gian thực hiện và đôi khi biểu thức thông thường, do backtracking, có thể có một hành vi tiệm cận tồi tệ hơn nhiều.

Bạn được khuyến khích mạnh mẽ để biết cách biểu thức chính quy được triển khai để bạn có thể biết khi nào bạn đang viết những từ không hiệu quả.

Answer 4

Regex không chậm. Nhưng việc triển khai có thể chậm, chủ yếu là vì nó thường được diễn giải và xây dựng lại mỗi khi chúng được sử dụng. Nhưng thư viện regexp tốt cho phép bạn sử dụng các phiên bản được biên dịch. Chúng khá nhanh.

Answer 5

Một số cụm từ thông dụng cực kỳ nhanh và sự khác biệt giữa regex và giải pháp tùy chỉnh có thể không đáng kể (hoặc không đáng để bận tâm).

Trường hợp biểu thức chính quy chậm, tuy nhiên, là khi excessive backtracking occurs. Các biểu thức chính quy phân tích từ trái sang phải và có khả năng khớp văn bản theo nhiều cách. Vì vậy, nếu chúng đạt đến điểm mà động cơ nhận ra rằng mẫu sẽ không khớp với chuỗi thử nghiệm của bạn, thì nó có thể bắt đầu trên và cố gắng khớp theo cách khác. Điều này lặp đi lặp lại backtracking thêm lên và làm chậm thuật toán.

Thường thì biểu thức chính quy có thể được viết lại để hoạt động tốt hơn. Nhưng cuối cùng trong hoạt động sẽ là viết trình phân tích cú pháp được tối ưu hóa của riêng bạn cho nhiệm vụ cụ thể. Bằng cách viết trình phân tích cú pháp của riêng bạn, bạn có thể ví dụ phân tích cú pháp từ trái sang phải trong khi vẫn duy trì bộ nhớ (hoặc trạng thái). Nếu bạn sử dụng kỹ thuật này trong mã thủ tục, bạn thường có thể đạt được hiệu quả mà bạn đang tìm kiếm trong một lần truyền và không có sự chậm trễ của việc quay ngược lại.

Tôi đã phải đối mặt với quyết định này vào đầu năm nay. Trong thực tế, nhiệm vụ trong tầm tay là trên rìa ngoài của những gì thậm chí có thể với các biểu thức thông thường. Cuối cùng, tôi quyết định viết trình phân tích cú pháp của riêng mình, một công cụ tự động đẩy xuống, điều này cực kỳ hiệu quả cho những gì tôi đang cố gắng làm. Nhiệm vụ, nhân tiện, là xây dựng một cái gì đó có thể phân tích các biểu thức thông thường và cung cấp mã Intellisense giống như gợi ý cho họ.

Đó là một chút mỉa mai rằng tôi không sử dụng biểu thức thông thường để phân tích biểu thức thông thường, nhưng bạn có thể đọc về ý nghĩ đằng sau nó tất cả ở đây ... http://blog.regexhero.net/2010/03/code-hinting-for-regular-expressions.html

Answer 6

loại regexp sẽ tốt hơn được viết lại cụ thể cho một vấn đề cụ thể thông qua thao tác chuỗi?

Dễ dàng.

1. Xác định xem bạn có cần viết lại bất kỳ thứ gì không.
   (câu trả lời tích cực sẽ là khoảng 1 cho mỗi 10.000 tập lệnh, phân tích cú pháp văn bản lớn, tài nguyên quan trọng)
2. Làm hồ sơ giải pháp có thể.
3. Sử dụng một bộ quần áo bạn cho một vấn đề nhất định

Đối với 9999 trường hợp còn lại không lãng phí thời gian của bạn với một vấn đề và sử dụng món đồ lặt vặt như bất cứ điều gì mà bạn thích hơn.

Mỗi khi bạn tự hỏi mình một câu hỏi, sẽ rất hữu ích khi tự nhắc nhở rằng theo mặc định, tất cả mã được tối ưu hóa và siêu nhanh được phân tích bởi char trên mọi yêu cầu của người dùng. Không có regexps não-nứt, không có thao tác chuỗi quanh co, nhưng chỉ cần chọn từng ký tự tốt cũ.