수식을 평가하는 데 가장 적합한 알고리즘입니까?

Question

수식을 평가하는 데 가장 좋은 알고리즘은 무엇입니까? 나는 다른 변수를 사용하여 수백 번 평가할 필요가있는 다양한 변수가있는 수식을 가질 수 있다는 점에서이를 조금만 최적화 할 수 있기를 바랍니다. 기본적으로 수식을 분석하여 어떤 식 으로든 최적화 할 수 있다면 필요한만큼 여러 번이 최적화 된 버전으로 변수를 전달할 수 있습니다. 결과는 매번 생성됩니다.

이 글은 Delphi 또는 C#으로 작성합니다. 내가 shunting 야드 알고리즘을 사용하여 비슷한 것을 이미 작성했지만 동일한 수식을 계산할 때마다 구문 분석 단계를 거쳐야합니다. 이것을하기위한 더 좋은 방법이 있어야합니다.

Answer 1

델파이을 함께하고 싶어, 당신은 JclExprEval 장치가 JEDI Code Library의 일부가 작동하는 방법으로 볼 수 있었다. 나는 그것을 몇 년 전에 쓴 적이있다. 함수와 변수를 파싱하고 표현식을 빠르게 평가하는 메소드 포인터를 돌려 줄 수 있습니다. 변수를 참조로 전달하면 변수를 직접 변경할 수 있으므로 다시 계산 된식이 그에 따라 계산됩니다.

어쨌든 어떻게 작동하는지에 대한 기본 사항은 도움이 될 수 있습니다. 재귀 - 내려 구문의 구문 분석은 쉽고 트리를 작성하여 다시 파싱하지 않고 여러 번 평가할 수 있습니다. JclExprEval은 실제로 간단한 스택 머신에 대한 코드를 생성하므로 트리 해석보다 조금 더 빠르게 작업 할 수 있습니다. 스택 머신은 주로 메모리 연산을 배열로 제한하고 opcode를 위해 스위치를 사용하지만, 트리 해석은 힙 전체의 링크를 따라오고 종종 opcode에 가상 디스패치 (또는 이중 디스패치)를 사용하므로 일반적으로 느리게 끝납니다.

구문 분석시에도 JclExprEval과 동일한 접근 방식을 취하고 있지만 C#으로 작성하고 Expression을 작성하는 것은 Marc에서 제안한 것처럼 다른 방법으로는 매우 유용합니다. JIT로 컴파일 된 표현식은 인터프리터 표현식 프로그램이나 트리보다 훨씬 빠르며, 파싱보다는 훨씬 빠릅니다.

Answer 2

.NET 3.5의 C#에서는 Expression을 사용할 수 있습니다. 매개 변수화 된 표현식을 작성한 다음 위임자에게 컴파일 할 수 있습니다. 이것은 정확히 Finguistics의 수학적 측면에서 내가 한 것입니다. 나는 여전히 당신이 원한다면 내가 사용한 구문 분석 코드를 가지고있다 ...

내가 사용한 주된 트릭은 델리게이트 형식을 알려주기 위해서 입력 유형으로 배열을 사용했다. arr [0] , arr 1, arr [2] 등입니다. 이는 Func<decimal[], decimal> (예 : decimal의 배열을 취하고 decimal을 반환)으로 컴파일 할 수 있음을 의미합니다.

Compile()을 일단 호출하면 직접 코드를 작성한 것처럼 보입니다.

(하드 코딩 기능)이 방법을 사용 Expression의 간단한 예로서

(편집)

아래 참조. 이미 작성한 파서는 입니다. 현재은 술어 검사기로 작동합니다. 즉 "? + (2 *? -?) = 22 +?" - 대신 결과를 반환하기 위해 변경하는 것은 어렵지 않을 것입니다 (예 : sin/pow/etc - 아마도 도우미 객체의 public 메소드에 직접 매핑하여 (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); 
    } 
}