Tại sao /^(.+)+Q$/.test("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX ") mất quá nhiều thời gian?

Question

Khi tôi chạy

/^(.+)+Q$/.test("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX") 

trong Chrome hoặc IE, phải mất ~ 10 giây để hoàn thành. (Firefox có thể đánh giá nó gần như ngay lập tức.)

Tại sao phải mất quá lâu? (Và tại sao/Firefox có thể làm điều đó nhanh như thế nào?)

(Tất nhiên, tôi không bao giờ chạy regex cụ thể này, nhưng tôi gặp vấn đề tương tự với URL regex tại http://daringfireball.net/2010/07/improved_regex_for_matching_urls và dường như đun sôi xuống này, tức là có một số URL mà sẽ làm cho trình duyệt để khóa lên)

Ví dụ:

var re = /\b((?:https?:\/\/|www\d{0,3}[.]|[a-z0-9.\-]+[.][a-z]{2,4}\/)(?:[^\s()<>]+|\(([^\s()<>]+|(\([^\s()<>]+\)))*\))+(?:\(([^\s()<>]+|(\([^\s()<>]+\)))*\)|[^\s`!()\[\]{};:'".,<>?«»“”‘’]))/i; 
re.test("http://google.com/?q=(AAAAAAAAAAAAAAAAAAAAAAAAAAAAA") 

Answer 1

như đã nêu bởi thg435, có vẻ như thảm khốc back-theo dõi. Có một bài viết tuyệt vời về điều này, Regular Expression Matching Can Be Simple And Fast.

Nó mô tả một phương pháp hiệu quả được gọi là Thompson NFA. Như đã nói, mặc dù, điều này không hỗ trợ tất cả các tính năng của các regex hiện đại. Ví dụ, nó không thể làm backreferences. Tuy nhiên, theo đề nghị trong bài viết:.

"Mặc dù vậy, nó sẽ là hợp lý để sử dụng mô phỏng NFA Thompson cho biểu thức thông thường nhất, và chỉ đưa ra thụt lùi khi nó là cần thiết Một thực hiện đặc biệt thông minh có thể kết hợp hai, chỉ sử dụng để quay ngược lại để thích ứng với các phản hồi ngược. "

Tôi nghi ngờ Firefox có thể thực hiện việc này.