Vấn đề hiệu suất biểu thức chính quy Java

Question

Tôi đang cố gắng tạo một chương trình vẽ đồ thị hàm trong Java và nó liên quan đến việc nhập dữ liệu của người dùng cho hàm sẽ được vẽ đồ thị, phân tích cú pháp và vẽ đồ thị. Ví dụ: người dùng có thể nhập vào x^2 - y^2, cos (x + y), nhật ký (x) - sqrt (y), v.v. Chương trình sử dụng cả hai thao tác nhị phân (+, -, v.v. .) và các hoạt động đơn nhất (cos, sqrt, v.v.).

Tóm lại, để đánh giá các hoạt động đơn nhất, tôi phải đảm bảo rằng biểu thức đã cho tuân theo định dạng của một phép toán đơn nhất. Ví dụ, cos (x), sqrt (x + y) và log (exp (y) - x) tất cả đều phù hợp với định dạng này, vì chúng là các phép toán đơn nhất với một số biểu thức như toán hạng của chúng; tuy nhiên, các chuỗi như sin (x) * cos (y) và 1 + log (x) không theo định dạng này. Để kiểm tra, tôi đã thực hiện một biểu thức chính quy cho định dạng này:

String unaryName = "((productlog)|(zeta)|(log)|(sqrt)|(cos)|(sin)|(tan)|(sec)|(csc)|(csc)|(abs)|(arccos)|(arcsin)|(arctan)|(arcsec)|(arccsc)|(arccot)|(gamma)|(exp))"; 

(đây chỉ là một regex để kiểm tra xem một chuỗi cho trước là một tên cho một hoạt động unary được xác định trước)

String unaryOperation = unaryName + "\\(([^\\(\\)]*(\\(.*\\))*[^\\(\\)]*)+\\)" 

tôi sẽ đưa ra một lời giải thích. Regex này đang tìm kiếm tên của một trong những hoạt động đơn nhất. Sau đó, nó sẽ tìm dấu ngoặc đơn bên trái. Sau đó, nó tìm kiếm một số chuỗi ký tự không phải là dấu ngoặc đơn, và sau đó một số chuỗi bắt đầu bằng dấu ngoặc đơn trái và kết thúc bằng dấu ngoặc đơn phải. Sau này ngăn chặn một chuỗi như "sin (x) + cos (y)" từ khớp.

Cụm từ thông dụng này luôn mang lại kết quả mong muốn, theo như tôi có thể biết. Tuy nhiên, trong việc sử dụng nó, một vấn đề nảy sinh. Hãy xem xét tình huống này:

String s = "cos(3) + sin(4)"; 
System.out.println(s.matches(unaryOperation)); 

Rõ ràng, nếu regex hoạt động, điều này sẽ trả về false. Điều này cũng đúng với ví dụ này:

String s = "cos(3.000) + sin(4)"; 
System.out.println(s.matches(unaryOperation)); 

Không có gì thực sự thay đổi, kiểu mẫu. Tuy nhiên, liên tục thêm số không vào 3, trận đấu có vẻ mất nhiều thời gian hơn để đánh giá. Đối với tôi, 12 zeroes mất khoảng 13 giây. Vì chương trình của tôi sẽ vẽ nhiều điểm trên một đồ thị, nó sẽ phải tính toán hàng ngàn biểu thức mỗi khi nó vẽ đồ thị, vì vậy đây là một lỗ hổng nghiêm trọng.

Tôi đã tìm cách sử dụng biểu thức chính quy này và chương trình của tôi hoạt động khá độc đáo, nhưng tôi vẫn muốn biết: tại sao cụm từ thông dụng này mất quá nhiều thời gian để làm việc cho các đầu vào lớn và bất kỳ cách nào để thay đổi regex để khắc phục vấn đề này?

Answer 1

Bạn có thể sử dụng regex này

unaryName+"\\([^)]*(\\([^()]*\\))?[^(]*\\)" 
        ------------ 
         |->starting from center. 

Ở đây tôi đang kiểm tra liệu các dấu ngoặc tròn là đúng cân bằng ..That nên giải quyết vấn đề của bạn!

Answer 2

Tôi nghi ngờ vấn đề là biểu thức của bạn đang thực hiện lô của việc quay lại vì .* ở giữa mẫu. Hãy thử thay thế nó bằng một định lượng miễn cưỡng: .*? hoặc, tốt hơn (nếu tôi hiểu logic), với [^\\)]*.

Trên thực tế, điều này sẽ không làm các trick:

String unaryOperation = unaryName + "\\([^\\)]*\\)"; 

này sẽ cho một cái tên, một ngoặc trái, bất kỳ số lượng các ký tự không phải ngoặc, và sau đó một ngoặc đúng. Điều này giả định rằng bạn không muốn đối sánh với những thứ như

"cos(3 * (4 + x))" 

(mẫu của bạn cũng sẽ không khớp).