गणितीय अभिव्यक्ति का मूल्यांकन करने के लिए सर्वश्रेष्ठ एल्गोरिदम?

Question

गणितीय अभिव्यक्ति का मूल्यांकन करने के लिए सबसे अच्छा एल्गोरिदम क्या है? मैं इस अर्थ में थोड़ा सा अनुकूलित करने में सक्षम होना चाहता हूं कि मेरे पास विभिन्न चर के साथ एक सूत्र हो सकता है, जिसे मुझे विभिन्न चर का उपयोग करके सैकड़ों बार मूल्यांकन करने की आवश्यकता हो सकती है। तो मूल रूप से यदि मैं प्रारंभ में फॉर्मूला को पार्स कर सकता हूं ताकि इसे किसी भी तरीके से अनुकूलित किया जा सके, और फिर मैं इस अनुकूलित संस्करण में जितनी बार चाहूं वैरिएबल में पास कर सकता हूं, हर बार जब यह मेरे लिए परिणाम उत्पन्न करता है।

मैं इसे डेल्फी या सी # में लिखूंगा। मैंने पहले से ही शंटिंग यार्ड एल्गोरिदम का उपयोग करके कुछ लिखा है, लेकिन हर बार मुझे उसी सूत्र की गणना करने की आवश्यकता होती है, मुझे पार्सिंग चरण से गुज़रना पड़ता है। ऐसा करने का एक बेहतर तरीका होना चाहिए।

Answer 1

आप डेल्फी के साथ क्या करना चाहते हैं, तो आप कैसे JclExprEval इकाई काम करता है, JEDI Code Library का हिस्सा इस पर गौर कर सकता है। मैंने इसे कई साल पहले लिखा था (यह थोड़ा अधिक इंजीनियर है); यह कार्यों और चरों को पार करता है और आपको एक विधि सूचक वापस भेज सकता है जो अभिव्यक्ति का त्वरित मूल्यांकन करता है। संदर्भ द्वारा चर को पास करें, और आप उन्हें सीधे बदल सकते हैं और फिर से मूल्यांकन की गई अभिव्यक्ति के अनुसार गणना की जाएगी।

किसी भी मामले में, यह कैसे काम करता है इसकी मूल बातें आपके लिए उपयोगी हो सकती हैं। अभिव्यक्तियों का पुनरावर्ती-मूल पार्सिंग आसान है, और एक पेड़ का निर्माण करके आप फिर से पार्सिंग के बिना कई बार मूल्यांकन कर सकते हैं। JclExprEval वास्तव में एक साधारण स्टैक मशीन के लिए कोड उत्पन्न करता है, ताकि यह पेड़ की व्याख्या से थोड़ा तेज़ काम कर सके; स्टैक मशीनें बड़े पैमाने पर अपने मेमोरी ऑपरेशंस को सरणी में प्रतिबंधित करती हैं और ऑपोड के लिए स्विचेस का उपयोग करती हैं, जबकि पेड़ की व्याख्या पूरे ढेर में लिंक का पालन करती है और अक्सर ऑपकोड के लिए आभासी प्रेषण (या डबल-डिस्पैच) का उपयोग करती है, इसलिए वे आमतौर पर धीमे हो जाते हैं।

पार्सिंग में JclExprEval के समान दृष्टिकोण लेना, लेकिन सी # में लिखा गया है, और Expression का निर्माण करना, जैसे मार्क सुझाव देता है, एक और पूरी तरह से मान्य दृष्टिकोण है। जेआईटी-संकलित अभिव्यक्ति को एक व्याख्याित अभिव्यक्ति कार्यक्रम या पेड़ की तुलना में काफी तेज़ होना चाहिए, जो स्वयं पार्सिंग से बहुत तेज़ हैं।

Answer 2

सी # में .NET 3.5 के साथ, आप इसके लिए Expression का उपयोग कर सकते हैं; आप एक पैरामीटरयुक्त अभिव्यक्ति बना सकते हैं और उसके बाद इसे एक प्रतिनिधि को संकलित कर सकते हैं। यह वही है जो मैंने Finguistics के गणित पहलू के लिए किया था। मेरे पास अभी भी पार्सिंग कोड है जिसका उपयोग मैंने किया था ...

मैं जिस मुख्य चाल का उपयोग करता था वह था कि प्रतिनिधि प्रकार को ज्ञात रखने के लिए, मैंने इनपुट प्रकार के रूप में एक सरणी का उपयोग किया - विभिन्न तर्कों को एआर [0] , एआर 1, एआर [2] इत्यादि। इसका मतलब है कि मैं संकलित कर सकता हूं (उदाहरण के लिए) Func<decimal[], decimal> (decimal एस की एक सरणी लेता है, decimal देता है)।

एक बार जब आप Compile() कहलाते हैं, तो यह बहुत अधिक है कि आपके पास सीधे ऐसा करने के लिए कोड था।

(संपादित करें)

इस तरह से Expression का उपयोग करने (हार्ड-कोडेड समारोह के साथ) का एक संक्षिप्त उदाहरण के रूप में, नीचे देखें। पार्सर मैंने पहले से ही लिखा है चेकर के रूप में काम करता है - यानी यह जांचने के लिए "? + (2 *? -?) = 22 +?" - लेकिन परिणाम को वापस करने के लिए इसे बदलना मुश्किल नहीं होगा (और sin/pow/आदि जैसे अधिक संचालन शुरू करें - संभावित रूप से उन्हें एक सहायक ऑब्जेक्ट पर सार्वजनिक तरीकों से मैप करके (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); 
    } 
}