2009-02-21 41 views
13

Thuật toán tốt nhất để đánh giá biểu thức toán học là gì? Tôi muốn có thể tối ưu hóa điều này một chút theo ý nghĩa rằng tôi có thể có một công thức với các biến khác nhau, mà tôi có thể cần phải đánh giá hàng trăm lần bằng cách sử dụng các biến khác nhau. Về cơ bản, nếu ban đầu tôi có thể phân tích cú pháp công thức sao cho nó được tối ưu hóa theo một cách nào đó và sau đó tôi có thể chuyển các biến đến phiên bản được tối ưu hóa này nhiều lần tùy theo nhu cầu của tôi, mỗi khi nó tạo ra kết quả cho tôi.Thuật toán tốt nhất để đánh giá biểu thức toán học?

Tôi sẽ viết thư này bằng Delphi hoặc C#. Tôi đã viết một cái gì đó tương tự bằng cách sử dụng thuật toán sân shunting, nhưng mỗi lần tôi cần phải tính toán cùng một công thức, tôi phải trải qua giai đoạn phân tích cú pháp. Phải có cách tốt hơn để làm điều này.

+0

Biểu thức phức tạp như thế nào? Giới hạn trong bốn hàm số học, hoặc rất chung chung? – Richard

+0

Có thể khá phức tạp, bao gồm các hàm có nhiều tham số. – Steve

Trả lời

15

Nếu bạn muốn làm điều đó với Delphi, bạn có thể nhìn vào cách các đơn vị JclExprEval hoạt động, một phần của JEDI Code Library. Tôi đã viết nó vài năm trước đây (đó là một chút được thiết kế quá mức); nó phân tích các hàm và các biến và có thể đưa bạn trở lại một con trỏ phương thức đánh giá biểu thức một cách nhanh chóng. Chuyển các biến theo tham chiếu và bạn có thể thay đổi chúng trực tiếp và biểu thức đánh giá lại sẽ được tính toán tương ứng.

Trong mọi trường hợp, các khái niệm cơ bản về cách hoạt động có thể hữu ích cho bạn. Phân tích cú pháp đệ quy của biểu thức dễ dàng, và bằng cách xây dựng một cây bạn có thể đánh giá nhiều lần mà không cần phân tích cú pháp lại. JclExprEval thực sự tạo ra mã cho một máy xếp chồng đơn giản, để nó có thể làm việc nhanh hơn một chút so với giải thích cây; các máy chủ ngăn chặn phần lớn các hoạt động bộ nhớ của chúng thành mảng và sử dụng các switch cho opcodes, trong khi việc giải thích cây theo các liên kết trong toàn bộ heap và thường sử dụng công văn ảo (hoặc double-dispatch) cho opcodes, vì vậy chúng thường kết thúc chậm hơn.

Cách tiếp cận tương tự như JclExprEval khi phân tích cú pháp nhưng được viết bằng C# và xây dựng một Expression, như Marc gợi ý, là một cách tiếp cận hoàn toàn hợp lệ khác. Biểu thức được biên dịch JIT phải nhanh hơn một chút so với một chương trình biểu thức giải nghĩa hoặc cây, bản thân chúng nhanh hơn rất nhiều so với phân tích cú pháp.

+0

Điều đó có vẻ giống như những gì tôi cần. thks. Tôi thích 'quá thiết kế'! – Steve

8

Trong C# với .NET 3.5, bạn có thể sử dụng Expression cho việc này; bạn có thể xây dựng một biểu thức được tham số hóa và sau đó biên dịch nó thành một đại biểu. Đây chính xác là những gì tôi đã làm cho khía cạnh toán học của Finguistics. Tôi vẫn có mã phân tích mà tôi đã sử dụng nếu bạn muốn ...

Bí quyết chính mà tôi đã sử dụng là giữ cho loại đại biểu được biết, tôi đã sử dụng mảng làm loại đầu vào - xử lý các arg khác nhau như arr [0] , arr 1, arr [2] v.v. Điều này có nghĩa là tôi có thể biên dịch thành (ví dụ) Func<decimal[], decimal> (mất một mảng là decimal s, trả lại một decimal).

Khi bạn đã gọi số Compile(), điều này rất nguy hiểm như thể bạn đã có mã để thực hiện trực tiếp.

(chỉnh sửa)

Là một ví dụ ngắn gọn của việc sử dụng Expression theo cách này (với một chức năng mã hóa cứng), xem dưới đây. Trình phân tích cú pháp tôi đã viết hiện tại là hoạt động như một biến vị ngữ - tức là để kiểm tra xem "? + (2 *? -?) = 22 +?" - nhưng sẽ không khó thay đổi nó để trả về kết quả thay thế (và giới thiệu nhiều hoạt động hơn, như sin/pow/etc - có lẽ bằng cách ánh xạ chúng trực tiếp tới các phương thức công khai trên đối tượng trợ giúp (qua Expression.Call)).

using System; 
using System.Linq.Expressions; 
static class Program 
{ 
    static void Main() 
    { 
     var args = Expression.Parameter(typeof(float[]), "args"); 
     var x = Expression.ArrayIndex(args, Expression.Constant(0)); 
     var y = Expression.ArrayIndex(args, Expression.Constant(1)); 
     var add = Expression.Add(x, y); 
     var lambda = Expression.Lambda<Func<float[], float>>(add, args); 

     Func<float[], float> func = lambda.Compile(); 
     Console.WriteLine(func.Call(1, 2)); 
     Console.WriteLine(func.Call(3, 4)); 
     Console.WriteLine(func.Call(5, 6)); 
    } 

    static T Call<T>(this Func<T[], T> func, params T[] args) 
    { // just allows "params" usage... 
     return func(args); 
    } 
} 
+0

Tôi đang tự hỏi liệu có nên làm một công việc "đúng" của mã phân tích cú pháp như một dự án thú cưng ... nó sẽ không có nhiều thay đổi đối với mã hiện có. –

+0

Làm tốt lắm! Khung được triển khai như thế nào? – boj

+0

@boj - tốt, đó là hơn một năm trước đây ;-p Trình phân tích cú pháp khá chuẩn, IIRC –

Các vấn đề liên quan