हम C # में एक “कैलकुलेटर” लिखते हैं। भाग I मूल्य गणना, व्युत्पन्न, सरलीकरण, और अन्य कलहंस

नमस्ते!

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


हम नए साल से शेष कुकीज़ लेते हैं, और चलाई है!

अभिव्यक्ति सभा

एक अभिव्यक्ति क्या है?

बेशक, यह एक पंक्ति नहीं है। यह बहुत स्पष्ट है कि एक गणितीय सूत्र या तो एक पेड़ है या एक स्टैक है, और यहां हम पहले पर रोकते हैं। अर्थात्, प्रत्येक नोड, इस पेड़ का प्रत्येक नोड, किसी प्रकार का संचालन, परिवर्तनशील या स्थिर है।



एक ऑपरेशन या तो एक फ़ंक्शन या एक ऑपरेटर है, सिद्धांत रूप में, लगभग एक ही बात है। उसके बच्चे एक फ़ंक्शन (ऑपरेटर) के तर्क हैं।

अपने कोड में श्रेणी पदानुक्रम

बेशक, कार्यान्वयन किसी भी हो सकता है। हालांकि, विचार यह है कि यदि आपके पेड़ में केवल नोड्स और पत्ते होते हैं, तो वे अलग हैं। इसलिए, मैं इन "चीजों" - संस्थाओं को बुलाता हूं। इसलिए, उच्च वर्ग अमूर्त वर्ग इकाई होगा।


और चार उत्तराधिकारी वर्ग भी होंगे: नंबरइंटीटिटी, वैरिएबल एनीटिटी, ऑपरेटरएटेंटिटी, फंक्शनएंटिटी।

अभिव्यक्ति का निर्माण कैसे करें?

सबसे पहले, हम कोड में एक अभिव्यक्ति का निर्माण करेंगे, अर्थात।

var x = new VariableEntity("x"); var expr = x * x + 3 * x + 12; 

यदि आप एक खाली वर्ग VariableEntity घोषित करते हैं, तो ऐसा कोड आपको एक त्रुटि देगा, वे कहते हैं कि गुणा और योग करना नहीं जानता है।

ओवरराइडिंग ऑपरेटर्स

अधिकांश भाषाओं की एक बहुत ही महत्वपूर्ण और उपयोगी सुविधा, जो आपको अंकगणितीय संचालन के निष्पादन को अनुकूलित करने की अनुमति देती है। यह भाषा के आधार पर अलग-अलग तरीके से वाक्यविन्यास कार्यान्वित किया जाता है। उदाहरण के लिए, C # में एक कार्यान्वयन

 public static YourClass operator +(YourClass a, YourClass b) { return new YourClass(a.ToString() + b.ToString()); } 

C # में ओवरराइडिंग स्टेटमेंट के बारे में अधिक जानें
शलजम यहाँ लागू किया जाता है ।

(गैर) स्पष्ट कास्टिंग

संकलित भाषाओं में जैसे कि C #, इस तरह की चीज आमतौर पर मौजूद होती है और यदि आवश्यक हो तो बिना myvar.ToAnotherType () के कॉल करने पर आपको टाइप करने की अनुमति मिलती है। इसलिए, उदाहरण के लिए, यह लिखना सुविधाजनक होगा

 NumberEntity myvar = 3; 

सामान्य के बजाय

 NumberEntity myvar = new NumberEntity(3); 

C # में टाइप कास्टिंग पर अधिक
इस लाइन पर शलजम लागू किया जाता है।

निलंबन

इकाई वर्ग में एक बच्चे का क्षेत्र है - यह इकाई की एक सूची है, जो इस इकाई के लिए तर्क हैं।


जब हम किसी फ़ंक्शन या ऑपरेटर को कॉल करते हैं, तो हमें एक नई इकाई बनानी चाहिए, और उसमें उन बच्चों को डालना चाहिए जिनसे फ़ंक्शन या ऑपरेटर कहा जाता है। उदाहरण के लिए, सिद्धांत में राशि कुछ इस तरह दिखनी चाहिए:

 public static Entity operator +(Entity a, Entity b){ var res = new OperatorEntity("+"); res.Children.Add(a); res.Children.Add(b); return res; } 

यही है, अब यदि हमारे पास इकाई x और इकाई 3 है, तो x + 3 दो बच्चों के साथ योग ऑपरेटर का सार लौटाएगा: 3 और x। इसलिए, हम अभिव्यक्ति पेड़ बना सकते हैं।

एक फ़ंक्शन कॉल सरल है और ऑपरेटर के साथ उतना सुंदर नहीं है:

 public Entity Sin(Entity a) { var res = new FunctionEntity("sin"); res.Children.Add(a); return res; } 

शलजम में लटकना यहां लागू होता है ।

ठीक है, हमने एक अभिव्यक्ति ट्री बनाया।

चर प्रतिस्थापन

यहां सब कुछ बेहद सरल है। हमारे पास इकाई है - हम जांचते हैं कि क्या यह स्वयं एक चर है, यदि हां, तो हम मूल्य वापस करते हैं, अन्यथा हम बच्चों के माध्यम से चलाते हैं।

यह विशाल 48-लाइन फ़ाइल ऐसे जटिल फ़ंक्शन को लागू करती है।

मान गणना

दरअसल, यह सब किस लिए है। यहाँ हम Entity में किसी प्रकार की विधि को जोड़ने वाले हैं

 public Entity Eval() { if (IsLeaf) { return this; } else return MathFunctions.InvokeEval(Name, Children); } 

पत्ती अपरिवर्तित है, लेकिन बाकी सभी चीजों के लिए हमारे पास एक कस्टम गणना है। फिर से, मैं सिर्फ एक उदाहरण दूंगा:

 public static Entity Eval(List<Entity> args) { MathFunctions.AssertArgs(args.Count, 1); var r = args[0].Eval(); if (r is NumberEntity) return new NumberEntity(Number.Sin((r as NumberEntity).Value)); else return r.Sin(); } 

यदि तर्क एक संख्या है, तो हम एक संख्यात्मक कार्य करेंगे, अन्यथा हम इसे वापस कर देंगे जैसा कि यह था।

संख्या?

यह सबसे सरल इकाई है, संख्या। उस पर अंकगणितीय ऑपरेशन किए जा सकते हैं। डिफ़ॉल्ट रूप से, यह जटिल है। उसके पास पाप, कॉस, और कुछ अन्य परिभाषित जैसे ऑपरेशन भी हैं।

यदि रुचि है, तो संख्या यहाँ वर्णित है ।

यौगिक

कोई भी व्युत्पन्न की गणना संख्यात्मक रूप से कर सकता है, और ऐसा फ़ंक्शन एक पंक्ति में सही मायने में लिखा जाता है:

 public double Derivative(Func<double, double> f, double x) => (f(x + 1.0e-5) - f(x)) * 1.0e+5; 

लेकिन निश्चित रूप से हम एक विश्लेषणात्मक व्युत्पन्न चाहते हैं। चूँकि हमारे पास पहले से ही एक अभिव्यक्ति वृक्ष है, इसलिए हम प्रत्येक नोड को विभेदन नियम के अनुसार बदल सकते हैं। यह कुछ इस तरह काम करना चाहिए:



उदाहरण के लिए, मेरे कोड में राशि कैसे लागू की गई है:

 public static Entity Derive(List<Entity> args, VariableEntity variable) { MathFunctions.AssertArgs(args.Count, 2); var a = args[0]; var b = args[1]; return a.Derive(variable) + b.Derive(variable); } 

लेकिन काम

 public static Entity Derive(List<Entity> args, VariableEntity variable) { MathFunctions.AssertArgs(args.Count, 2); var a = args[0]; var b = args[1]; return a.Derive(variable) * b + b.Derive(variable) * a; } 

और यहाँ अपने आप में एक समाधान है:

 public Entity Derive(VariableEntity x) { if (IsLeaf) { if (this is VariableEntity && this.Name == x.Name) return new NumberEntity(1); else return new NumberEntity(0); } else return MathFunctions.InvokeDerive(Name, Children, x); } 

यह इकाई विधि है। और जैसा कि हम देखते हैं, पत्ती के केवल दो राज्य हैं - या तो यह एक चर है जिसके द्वारा हम अंतर करते हैं, फिर इसका व्युत्पन्न 1 है, या यह एक स्थिर (संख्या या परिवर्तनीय) है, तो इसका व्युत्पन्न 0 है, या एक नोड है, फिर नाम से एक संदर्भ है (InvokeDerive) कार्यों के शब्दकोश को संदर्भित करता है, जहां वांछित एक स्थित है (उदाहरण के लिए, योग या साइन))।

ध्यान दें कि मैं डाई / डीएक्स जैसी किसी चीज़ को यहां नहीं छोड़ता और तुरंत कहता हूं कि जिस वेरिएबल से हम अंतर करते हैं उसका व्युत्पन्न 0. है। लेकिन यहां यह अलग तरह से किया जाता है।

सभी भेदभाव एक फ़ाइल में वर्णित हैं, लेकिन अधिक आवश्यक नहीं है।

अभिव्यक्ति का सरलीकरण। पैटर्न

अभिव्यक्ति का सरलीकरण आमतौर पर सिद्धांत में तुच्छ नहीं है। उदाहरण के लिए, कौन सी अभिव्यक्ति सरल है: $$$x ^ 2 - y ^ 2$या $$$(x - y) (x + y)$? लेकिन हम कुछ विचारों का पालन करते हैं, और उनके आधार पर हम उन नियमों को बनाना चाहते हैं जो अभिव्यक्ति को सटीक रूप से सरल बनाते हैं।

प्रत्येक एवल में यह लिखना संभव है कि अगर हमारे पास योग है, और बच्चे काम कर रहे हैं, तो हम चार विकल्पों को हल करेंगे, और अगर कुछ समान है, तो हम कारक निकाल लेंगे ... लेकिन निश्चित रूप से मैं ऐसा नहीं करना चाहता। इसलिए, आप नियमों और पैटर्न की प्रणाली का अनुमान लगा सकते हैं। तो हम क्या चाहते हैं? कुछ इस वाक्य रचना की तरह:

 { any1 / (any2 / any3) -> any1 * any3 / any2 }, { const1 * var1 + const2 * var1 -> (const1 + const2) * var1 }, { any1 + any1 * any2 -> any1 * (Num(1) + any2) }, 

यहां एक पेड़ का एक उदाहरण है जिसमें एक सबट्री पाया गया था (हरे रंग में परिचालित) जो किसी भी पैटर्न + 1 (const1 * any1 (किसी भी पाया गया नारंगी में परिक्रमा करता है) से मेल खाता है।



जैसा कि आप देख सकते हैं, कभी-कभी हमारे लिए यह महत्वपूर्ण है कि एक ही इकाई को दोहराया जाना चाहिए, उदाहरण के लिए, अभिव्यक्ति x + a * x को छोटा करने के लिए, हमें x को वहां और वहां होने की आवश्यकता है, क्योंकि x + a * y अब कम नहीं है। इसलिए, हमें एक एल्गोरिथ्म बनाने की ज़रूरत है जो न केवल यह जांचती है कि पेड़ पैटर्न से मेल खाता है, बल्कि यह भी

1. सत्यापित करें कि समान एंटिटी पैटर्न समान एंटिटी से मेल खाता है।
2. लिखने के लिए कि क्या से मेल खाती है, फिर स्थानापन्न करने के लिए।

प्रवेश बिंदु कुछ इस तरह दिखता है:

 internal Dictionary<int, Entity> EqFits(Entity tree) { var res = new Dictionary<int, Entity>(); if (!tree.PatternMakeMatch(this, res)) return null; else return res; } 

और पेड़ में। PaternMakeMatch, हम कुंजी और उनके मूल्यों के साथ शब्दकोश को पुनरावृत्ति करते हैं। यहाँ स्वयं प्रतिरूपों की सूची का एक उदाहरण दिया गया है:

 static readonly Pattern any1 = new Pattern(100, PatType.COMMON); static readonly Pattern any2 = new Pattern(101, PatType.COMMON); static readonly Pattern const1 = new Pattern(200, PatType.NUMBER); static readonly Pattern const2 = new Pattern(201, PatType.NUMBER); static readonly Pattern func1 = new Pattern(400, PatType.FUNCTION); 

जब हम any1 * const1 - func1 इत्यादि लिखते हैं, तो प्रत्येक नोड में एक संख्या होगी - यह कुंजी है। दूसरे शब्दों में, शब्दकोश को भरते समय, ये संख्याएं कुंजियों के रूप में दिखाई देंगी: 100, 101, 200, 201, 400 ... और जब एक पेड़ का निर्माण होता है, तो हम कुंजी के अनुरूप मूल्य को देखेंगे और इसे प्रतिस्थापित करेंगे।

यहां लागू किया गया ।

सरल। पेड़ की छँटाई

लेख में जो मैंने पहले ही संबोधित किया है, लेखक ने इसे बस करने का फैसला किया, और पेड़ के हैश द्वारा व्यावहारिक रूप से हल किया। वह 2 बी + सी चालू करने के लिए एक -ए, बी + सी + बी को कम करने में कामयाब रहा। लेकिन हम, निश्चित रूप से, (x + y) + x * y - 3 * x को कम करना चाहते हैं, और सामान्य रूप से अधिक जटिल चीजों में।

पैटर्न काम नहीं कर रहे हैं?

सामान्य तौर पर, हमने पहले क्या किया था, पैटर्न एक राक्षसी रूप से अद्भुत चीज है। यह आपको वर्गों, और साइन और कोसिन के वर्ग के योग और अन्य जटिल चीजों के बीच के अंतर को कम करने की अनुमति देगा। लेकिन प्राथमिक हथेली, ((((((x + 1) + 1) + 1) + 1), यह कम नहीं होगा, क्योंकि यहां मुख्य नियम शर्तों की कम्यूटिटी है। इसलिए, पहला कदम "रैखिक बच्चों" को अलग करना है।

"रैखिक बच्चे"

दरअसल, योग या अंतर के प्रत्येक नोड के लिए (और, वैसे, उत्पाद / विभाजन), हम शर्तों (कारकों) की एक सूची प्राप्त करना चाहते हैं।



यह मूल रूप से सीधा है। LinearChildren (Entity नोड) फ़ंक्शन को एक सूची वापस करने दें, फिर हम नोड में बच्चे को देखते हैं। चिल्ड्रेन: यदि बच्चा एक योग नहीं है, तो result। जोड़ें (बच्चा), अन्यथा परिणाम ।ddRange (LinearCildren (बच्चा))।

यहां लागू सबसे खूबसूरत तरीका नहीं।

बच्चों का समूह बनाना

तो हमारे पास बच्चों की एक सूची है, लेकिन आगे क्या? मान लीजिए कि हमारे पास पाप (x) + x + y + sin (x) + 2 * x है। जाहिर है, हमारे एल्गोरिथ्म को पांच शर्तें प्राप्त होंगी। अगला, हम समानता द्वारा समूह बनाना चाहते हैं, उदाहरण के लिए, x पाप की तुलना में 2 * x अधिक लगता है (x)।

यहाँ एक अच्छा समूहन है:



चूंकि इसमें पैटर्न 2 * x + x से 3 * x के रूपांतरण के साथ आगे का सामना करेंगे।

यही है, हम पहले कुछ हैश द्वारा समूह बनाते हैं, और फिर मल्टीहांग करते हैं - एन-आर्य योग को बाइनरी में परिवर्तित करते हैं।

नोड हैश

एक ओर $$$x$और $$$x + 1$एक समूह में रखा जाना चाहिए। दूसरी ओर, यदि उपलब्ध हो $$$ए * x$के साथ एक समूह में डाल दिया $$$y * (x + 1)$व्यर्थ।


इसलिए, हम बहु-स्तरीय छँटाई को लागू करते हैं। पहले, हम यह दिखावा करते हैं $$$x + 1$- एक ही बात। क्रमबद्ध, शांत हो गया। फिर हम दिखावा करते हैं $$$x + 1$केवल दूसरों के साथ रखा जा सकता है $$$x + 1$। और अब हमारी $$$a * (x + 1)$और $$$y * (x + 1)$अंत में टीम बनाई गई। काफी सरलता से लागू:

 internal string Hash(SortLevel level) { if (this is FunctionEntity) return this.Name + "_" + string.Join("_", from child in Children select child.Hash(level)); else if (this is NumberEntity) return level == SortLevel.HIGH_LEVEL ? "" : this.Name + " "; else if (this is VariableEntity) return "v_" + Name; else return (level == SortLevel.LOW_LEVEL ? this.Name + "_" : "") + string.Join("_", from child in Children where child.Hash(level) != "" select child.Hash(level)); } 

जैसा कि आप देख सकते हैं, फ़ंक्शन किसी भी तरह से छँटाई को प्रभावित करता है (बेशक, क्योंकि $$$च (x)$साथ $$$x$आम तौर पर सामान्य मामले में जुड़ा नहीं)। एक चर की तरह, $$$x$साथ $$$य$खैर, यह मिश्रण करने के लिए काम नहीं करता है। लेकिन स्थिरांक और ऑपरेटरों को सभी स्तरों पर ध्यान नहीं दिया जाता है। इस क्रम में, सरलीकरण प्रक्रिया ही

 public Entity Simplify(int level) { //      :   ,   ,     . . var stage1 = this.InnerSimplify(); Entity res = stage1; for (int i = 0; i < level; i++) { //     .    -  x  x+1 (  ),  -  x-1  x+1 (,   ),  -  x+1  x+1 ( ). switch (i) { case 0: res = res.Sort(SortLevel.HIGH_LEVEL); break; case 2: res = res.Sort(SortLevel.MIDDLE_LEVEL); break; case 4: res = res.Sort(SortLevel.LOW_LEVEL); break; } //    . res = TreeAnalyzer.Replace(Patterns.CommonRules, res).InnerSimplify(); } return res; } 

मैं यहां पेड़ को छांटता हूं।

कार्यों का "संकलन"

उद्धरण चिह्नों में - चूंकि यह केवल IL कोड में नहीं है, बल्कि केवल बहुत तेज़ निर्देशों के सेट में है। लेकिन यह बहुत आसान है।

स्थानापन्न समस्या

एक फ़ंक्शन के मूल्य की गणना करने के लिए, हमें उदाहरण के लिए, केवल चर प्रतिस्थापन और eval को कॉल करना होगा

 var x = MathS.Var("x"); var expr = x * x + 3; var result = expr.Substitute(x, 5).Eval(); 

लेकिन यह धीरे-धीरे काम करता है, प्रति साइन के बारे में 1.5 माइक्रोसेकंड।

अनुदेश

गणना को गति देने के लिए, हम स्टैक पर एक फ़ंक्शन गणना करते हैं, अर्थात्:

1) हम फास्टएक्सप्रेशन क्लास के साथ आते हैं, जिसमें निर्देशों की एक सूची होगी

2) जब संकलित किया जाता है, तो निर्देशों को रिवर्स ऑर्डर में स्टैक किया जाता है, अर्थात, यदि कोई फ़ंक्शन x * x + sin (x) + 3 है, तो निर्देश कुछ इस तरह होंगे:

 PUSHVAR 0 //    0 - x CALL 6 //    6 -  PUSHCONST 3 CALL 0 //    0 -  PUSHVAR 0 PUSHVAR 0 CALL 2 CALL 0 

अगला, जब बुलाया जाता है, तो हम इन निर्देशों को चलाते हैं और संख्या वापस करते हैं।

राशि कथन को निष्पादित करने का एक उदाहरण:

 internal static void Sumf(Stack<Number> stack) { Number n1 = stack.Pop(); Number n2 = stack.Pop(); stack.Push(n1 + n2); } 

साइन कॉल 1500ns से घटाकर 60ns (सिस्टम कॉम्प्लेक्स.इन 30ns के लिए काम करता है) किया गया था।
शलजम यहाँ लागू किया जाता है ।

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

सभी कोड के साथ भंडार के लिए लिंक , साथ ही परीक्षण और नमूने।


आपका ध्यान के लिए धन्यवाद!