पूर्वगणना
एल्गोरिदम में, प्रीकंप्यूटेशन एक लुकअप टेबल उत्पन्न करने के लिए रन टाइम से पहले प्रारंभिक गणना करने का कार्य है जिसे एल्गोरिदम द्वारा हर बार निष्पादित होने पर बार-बार गणना से बचने के लिए उपयोग किया जा सकता है। प्रीकंप्यूटेशन (पूर्वगणना) प्रायः एल्गोरिदम में प्रयोग किया जाता है जो महंगी गणनाओं के परिणामों पर निर्भर करता है जो एल्गोरिदम के इनपुट पर निर्भर नहीं होते हैं। पूर्वगणना का एक तुच्छ उदाहरण हार्डकोडेड गणितीय स्थिरांक का उपयोग है, प्रीकंप्यूटेशन का एक सरल उदाहरण जैसे कि π और e, रन टाइम पर आवश्यक सटीकता के लिए उनके अनुमानों की गणना करने के बजाय हार्डकोडेड गणितीय स्थिरांक का उपयोग है।
डेटाबेस में, भौतिककरण शब्द का उपयोग पूर्व-गणना के परिणामों को संग्रहीत करने के लिए किया जाता है,[1][2] जैसा कि भौतिक दृश्य में होता है।[3][4]
अवलोकन
एल्गोरिथम के निष्पादन की प्रारम्भ में मध्यवर्ती परिणामों के एक सेट की प्रीकंप्यूटिंग प्रायः एल्गोरिथम दक्षता में काफी वृद्धि कर सकती है। यह तब लाभप्रद होता है जब एक या अधिक इनपुट एक छोटी पर्याप्त सीमा तक सीमित होते हैं, जिससे परिणाम स्मृति के उचित आकार के ब्लॉक में संग्रहीत किए जा सकते हैं। क्योंकि समय की जटिलता (सीपीयू कैश देरी को छोड़कर) में मेमोरी एक्सेस अनिवार्य रूप से स्थिर है, एक घटक के साथ किसी भी एल्गोरिदम जो कि एक छोटे से इनपुट रेंज पर निरंतर दक्षता से भी अत्यधिक कम है, को प्रीकंप्यूटिंग मूल्यों से सुधार किया जा सकता है। कुछ मामलों में कुशल सन्निकटन एल्गोरिदम मूल्यों के असतत सबसेट की गणना करके और मध्यवर्ती इनपुट मूल्यों के लिए प्रक्षेपित करके प्राप्त किया जा सकता है, क्योंकि इंटरपोलेशन भी एक रैखिक ऑपरेशन है।
इतिहास
कंप्यूटर के आगमन से पहले, लोगों द्वारा त्रिकोणमितीय तालिकाओं, लघुगणक तालिकाओं और सांख्यिकीय घनत्व कार्यों की तालिकाओं जैसे जटिल कार्यों की हाथ की गणना को गति देने के लिए मूल्यों की मुद्रित लुक-अप तालिकाओं का उपयोग किया जाता था।[5] तालिका" को याद रखना सिखाया जाता है। सबसे अधिक उपयोग की जाने वाली संख्याओं (9 x 9 या 12 x 12 तक) की गणना करने से बचें। यहां तक कि 493 ईस्वी पूर्व में, एक्विटेन के विक्टोरियस ने एक 98-स्तंभ गुणन तालिका लिखी थी, जो (रोमन अंकों में) 2 से 50 गुना तक प्रत्येक संख्या का गुणनफल देती थी और पंक्तियाँ एक हजार से प्रारंभ होने वाली संख्याओं की एक सूची थी, जो सैकड़ों से नीचे उतरती थी। एक सौ से, फिर दसियों से दस तक, फिर एक से एक तक, और फिर 1/144 तक भिन्न है। [6]
उदाहरण
यहां तक कि डिजिटल त्रिकोणमितीय कार्यों के आधुनिक कंप्यूटर कार्यान्वयन भी प्रायः प्रक्षेप एल्गोरिदम के लिए गुणांक प्रदान करने के लिए, या क्रमिक सन्निकटन एल्गोरिदम आरंभ करने के लिए पूर्व-गणना लुकअप तालिकाओं का उपयोग करते हैं।
क्रिप्टोसिस्टम पर कई आक्रमण में पूर्व-गणना सम्मिलित है।
आधुनिक कुशल एल्गोरिदम के हिस्से के रूप में बड़े पैमाने पर प्रीकंप्यूटेशन के उदाहरणों में सम्मिलित हैं:
- इंद्रधनुष टेबल
- परफेक्ट हैश
- क्यूब अटैक
- 3डी ग्राफिक्स में दृश्यता गणना के लिए पूर्व-परिकलित बीएसपी पेड़
- रेडियोसिटी (3डी कंप्यूटर ग्राफिक्स) 3डी ग्राफिक्स में रोशनी के लिए प्रीकंप्यूटेशन
परिणामी कोड के रन-टाइम की गति को बढ़ाने के साधन के रूप में संकलक बड़े पैमाने पर पूर्व-गणना का उपयोग करते हैं: इस पूर्व-गणना को प्रभावी रूप से प्रोग्राम कोड के आंशिक मूल्यांकन के रूप में माना जा सकता है। इस प्रकार के पूर्वगणना के उदाहरणों में डेटा प्रवाह विश्लेषण और शक्ति में कमी के चरण सम्मिलितहैं।
यह भी देखें
- गणितीय तालिका
- एल्गोरिथम दक्षता
- आंशिक मूल्यांकन
- संस्मरण
संदर्भ
- ↑ Jiawei Han; Micheline Kamber (9 June 2011). Data Mining: Concepts and Techniques: Concepts and Techniques. Elsevier. p. 159. ISBN 978-0-12-381480-7.
- ↑ Sven Groppe (29 April 2011). सिमेंटिक वेब डेटाबेस में डेटा प्रबंधन और क्वेरी प्रोसेसिंग. Springer Science & Business Media. p. 178. ISBN 978-3-642-19357-6.
- ↑ Karen Morton; Kerry Osborne; Robyn Sands; Riyaj Shamsudeen; Jared Still (28 October 2013). प्रो ओरेकल एसक्यूएल. Apress. p. 48. ISBN 978-1-4302-6220-6.
- ↑ Marie-Aude Aufaure; Esteban Zimányi (16 January 2012). बिजनेस इंटेलिजेंस: फर्स्ट यूरोपियन समर स्कूल, EBISS 2011, पेरिस, फ्रांस, 3-8 जुलाई, 2011, ट्यूटोरियल लेक्चर. Springer Science & Business Media. p. 43. ISBN 978-3-642-27357-5.
- ↑ Campbell-Kelly, Martin; Croarken, Mary; Flood, Raymond; et al., eds. (2003). The History of Mathematical Tables From Sumer to Spreadsheets. Oxford University Press. ISBN 978-0-19-850841-0.
- ↑ Maher, David. W. J. and John F. Makowski. "Literary Evidence for Roman Arithmetic With Fractions", 'Classical Philology' (2001) Vol. 96 No. 4 (2001) pp. 376–399. (See page p. 383.)
