मैं बड़े गणितीय अभिव्यक्तियों (लाखों नोड्स) के अनुरूप अभिव्यक्ति ग्राफ के लिए सामान्य उप-संपीड़न उन्मूलन (सीएसई) को कार्यान्वित करने में देख रहा हूं।सामान्य उप-संपीड़न उन्मूलन को लागू करना
यह करने के लिए कौन से एल्गोरिदम उपयुक्त हैं? मैं एक आसान-कार्यान्वित एल्गोरिदम के लिए इंटरनेट खोज रहा था लेकिन मुझे कुछ भी नहीं मिला। यदि संभव हो तो एल्गोरिदम में पूर्ण अभिव्यक्ति ग्राफ के नोड्स की संख्या में रैखिक जटिलता होनी चाहिए।
ये कोई दुष्प्रभाव नहीं हैं? फिर सबसे आसान बात यह है कि उप-अभिव्यक्ति उन्मूलन के लिए उम्मीदवारों को निर्धारित करने के लिए प्रत्येक सब-अभिव्यक्ति के लिए पेड़ों को बाल्टी में रखें। यह CSE का एक विशेष मामला है जहां सभी अभिव्यक्तियां एक (विशाल) "मूलभूत ब्लॉक" में हैं। (मैं इस विचार का उपयोग duplicate code का पता लगाने के आधार के रूप में करता हूं।)
यदि अभिव्यक्तियों के क्रम और दुष्प्रभाव होते हैं, तो आप Value Numbering पर विचार करना चाहेंगे।
ठीक है, कोई दुष्प्रभाव नहीं हैं। अगर मैं आपके सुझाव को सही ढंग से समझता हूं, तो मुझे अभिव्यक्ति के क्रम में अभिव्यक्ति के नोड्स पर लूप करना चाहिए, और प्रत्येक चरण में जांच करें कि क्या हैश मानचित्र में कोई अभिव्यक्ति पहले से मौजूद है या नहीं। यदि यह मौजूद है, तो इसके बजाय इस सबएक्सप्रेस का उपयोग करें, अगर इसे हैश मैप में नहीं जोड़ना है। क्या यह सही ढंग से समझा जाता है? – Joel
हां। "निर्भरताओं के क्रम में" का मतलब है प्रत्येक पेड़ के लिए नीचे। –
मैं वास्तव में इस रणनीति के बारे में सोच रहा था। आप किस तरह का हैशिंग का उपयोग करेंगे? – Joel
यह प्रतिनिधित्व सहायता कर सकता है: http://www.masonchang.com/blog/2010/8/9/sea-of-nodes-compilation-approach.html –