लुकअप टेबल: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| (9 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
{{Short description|Array that replaces runtime computation with a simpler array indexing operation}} | {{Short description|Array that replaces runtime computation with a simpler array indexing operation}} | ||
[[कंप्यूटर विज्ञान]] में, एक लुकअप टेबल (एलयूटी) एक [[सरणी डेटा संरचना|सरणी]] है जो रनटाइम (प्रोग्राम जीवनचक्र चरण) संगणना को एक सरल सरणी इंडेक्सिंग ऑपरेशन से बदल देती है। प्रक्रिया को डायरेक्ट एड्रेसिंग कहा जाता है और एलयूटी [[हैश टेबल]] से इस तरह से भिन्न होते हैं कि, एक मान प्राप्त करने के लिए <math>v</math> कुंजी के साथ <math>k</math>, एक हैश | [[कंप्यूटर विज्ञान]] में, एक लुकअप टेबल (एलयूटी) एक [[सरणी डेटा संरचना|सरणी]] है जो रनटाइम (प्रोग्राम जीवनचक्र चरण) संगणना को एक सरल सरणी इंडेक्सिंग ऑपरेशन से बदल देती है। प्रक्रिया को डायरेक्ट एड्रेसिंग कहा जाता है और एलयूटी [[हैश टेबल]] से इस तरह से भिन्न होते हैं कि, एक मान प्राप्त करने के लिए <math>v</math> कुंजी के साथ <math>k</math>, एक हैश टेबल <math>v</math> स्लॉट में <math>h(k)</math> मान संग्रहीत करेगी जहाँ <math>h</math> एक [[हैश फंकशन]] है अर्थात् <math>k</math> का उपयोग स्लॉट की गणना करने के लिए किया जाता है, जबकि LUT की स्थिति में, मान <math>v</math> को स्लॉट <math>k</math> में संग्रहीत किया जाता है, इस प्रकार सीधे पता लगाया जा सकता है।<ref name="Kwok95">{{cite journal|journal=Communications in Numerical Methods in Engineering|volume=11|issue=5|first1=W.|last1=Kwok|first2=K.|last2=Haghighi|first3=E.|last3=Kang|year=1995|doi=10.1002/cnm.1640110511|title=अग्रिम-सामने त्रिकोणीय जाल पीढ़ी तकनीक के लिए एक कुशल डेटा संरचना|pages=465–473|url=https://onlinelibrary.wiley.com/doi/10.1002/cnm.1640110511|publisher=Wiley & Sons}}</ref>{{rp|p=466}} प्रसंस्करण समय में बचत महत्वपूर्ण हो सकती है, क्योंकि मेमोरी से मान प्राप्त करना अधिकांश महंगी गणना या इनपुट/आउटपुट ऑपरेशन करने से तेज़ होता है।<ref>{{cite web |url=http://pmcnamee.net/c++-memoization.html |title=सी ++ में स्वचालित ज्ञापन|first=Paul |last=McNamee |date=21 August 1998 |url-status=unfit |archive-url=https://web.archive.org/web/20190416012134/http://pmcnamee.net/c++-memoization.html |archive-date=2019-04-16}}</ref> टेबलओं को [[पूर्वगणना]] किया जा सकता है और स्थिर मेमोरी आवंटन प्रोग्राम स्टोरेज में संग्रहीत किया जा सकता है, प्रोग्राम के प्रारंभिक चरण ([[memoization|मेमोइज़ेशन]]), के भाग के रूप में परिकलित (या "पूर्व-प्राप्त"), या एप्लिकेशन-विशिष्ट प्लेटफ़ॉर्म में हार्डवेयर में संग्रहीत भी किया जा सकता है। किसी सरणी में मान्य (या अमान्य) आइटमों की सूची के विरुद्ध मिलान करके इनपुट मानों को मान्य करने के लिए लुकअप टेबलओं का व्यापक रूप से उपयोग किया जाता है, और कुछ प्रोग्रामिंग भाषाओं में, मिलान इनपुट को संसाधित करने के लिए पॉइंटर फ़ंक्शन (या लेबल के लिए ऑफ़सेट) सम्मिलित हो सकते हैं। प्रोग्राम योग्य हार्डवेयर कार्यात्मकता प्रदान करने के लिए [[क्षेत्र में प्रोग्राम की जा सकने वाली द्वार श्रंखला]] पुन: विन्यास योग्य, हार्डवेयर-कार्यान्वित, लुकअप टेबलओं का व्यापक उपयोग करता है। | ||
== इतिहास == | == इतिहास == | ||
[[File:Abramowitz&Stegun.page97.agr.jpg|thumb|संदर्भ पुस्तक [[अब्रामोवित्ज़ और स्टेगुन]] में [[सामान्य लघुगणक]] की 20वीं सदी की | [[File:Abramowitz&Stegun.page97.agr.jpg|thumb|संदर्भ पुस्तक [[अब्रामोवित्ज़ और स्टेगुन]] में [[सामान्य लघुगणक]] की 20वीं सदी की टेबल का एक भाग।]]कंप्यूटर के आगमन से पहले, मानों की लुकअप टेबल का उपयोग जटिल कार्यों की हाथ की गणना में तेजी लाने के लिए किया जाता था, जैसे कि [[त्रिकोणमिति]], सामान्य लघुगणक और सांख्यिकीय घनत्व कार्यों में।<ref>{{cite book | ||
|editor1-last= Campbell-Kelly | |editor1-last= Campbell-Kelly | ||
|editor1-first= Martin | |editor1-first= Martin | ||
| Line 15: | Line 15: | ||
}} | }} | ||
</ref> | </ref> | ||
प्राचीन (499 ईस्वी) भारत में, [[आर्यभट|आर्यभट्ट]] ने पहली ज्या | प्राचीन (499 ईस्वी) भारत में, [[आर्यभट|आर्यभट्ट]] ने पहली ज्या टेबलओं में से एक का निर्माण किया, जिसे उन्होंने संस्कृत-अक्षर-आधारित संख्या प्रणाली में एन्कोड किया। 493 ईस्वी में, एक्विटाइन के विक्टोरियस ने एक 98-स्तंभ गुणन टेबल लिखी, जिसने ([[रोमन अंक|रोमन अंकों]] में) 2 से 50 बार प्रत्येक संख्या का उत्पाद दिया और पंक्तियाँ एक हज़ार से प्रारंभ होने वाली संख्याओं की एक सूची थीं, जो सैकड़ों से एक सौ तक उतरती थीं। फिर दसियों से दस तक, फिर एक से एक तक, और फिर भिन्नों को 1/144 तक घटाते हुए<ref>Maher, David. W. J. and John F. Makowski. "[https://ecommons.luc.edu/cgi/viewcontent.cgi?article=1024&context=classicalstudies_facpubs Literary Evidence for Roman Arithmetic With Fractions]", 'Classical Philology' (2001) Vol. 96 No. 4 (2001) pp. 376–399. (See page p.383.)</ref> आधुनिक स्कूली बच्चों को अधिकांश सबसे अधिक उपयोग की जाने वाली संख्याओं (9 x 9 या 12 x 12 तक) की गणना से बचने के लिए गुणा टेबल को याद करना सिखाया जाता है। | ||
कंप्यूटर के इतिहास के आरंभ में, इनपुट/आउटपुट संचालन विशेष रूप से धीमे थे - यहां तक कि उस समय के प्रोसेसर की गति की तुलना में भी। यह या तो स्टैटिक लुकअप टेबल (प्रोग्राम में एम्बेडेड) या डायनेमिक प्रीफेच्ड एरेज़ बनाकर केवल सबसे सामान्य रूप से होने वाले डेटा आइटम को सम्मिलित करके महंगे रीड ऑपरेशंस को मैन्युअल [[कैश (कंप्यूटिंग)|कैशिंग (कंप्यूटिंग)]] के रूप में कम करने के लिए समझ में आता है। सिस्टमवाइड कैशिंग की प्रारंभ के बावजूद जो अब इस प्रक्रिया को स्वचालित करता है, एप्लिकेशन स्तर लुकअप | कंप्यूटर के इतिहास के आरंभ में, इनपुट/आउटपुट संचालन विशेष रूप से धीमे थे - यहां तक कि उस समय के प्रोसेसर की गति की तुलना में भी। यह या तो स्टैटिक लुकअप टेबल (प्रोग्राम में एम्बेडेड) या डायनेमिक प्रीफेच्ड एरेज़ बनाकर केवल सबसे सामान्य रूप से होने वाले डेटा आइटम को सम्मिलित करके महंगे रीड ऑपरेशंस को मैन्युअल [[कैश (कंप्यूटिंग)|कैशिंग (कंप्यूटिंग)]] के रूप में कम करने के लिए समझ में आता है। सिस्टमवाइड कैशिंग की प्रारंभ के बावजूद जो अब इस प्रक्रिया को स्वचालित करता है, एप्लिकेशन स्तर लुकअप टेबलएं अभी भी डेटा आइटम्स के प्रदर्शन में सुधार कर सकती हैं जो संभवतः ही कभी बदलती हैं। | ||
लुकअप | लुकअप टेबलएँ कंप्यूटर [[स्प्रेडशीट|स्प्रेडशीटस]] में कार्यान्वित प्रारंभिक कार्यात्मकताओं में से एक थीं, जिसमें [[VisiCalc]] (1979) का प्रारंभिक संस्करण के साथ इसके मूल 20 कार्यों में एक <code>LOOKUP</code> फ़ंक्शन भी सम्मिलित था।<ref>[https://vlookupweek.wordpress.com/2012/03/31/bill-jelen-from-1979-visicalc-and-lookup/ Bill Jelen: "From 1979 – VisiCalc and LOOKUP"!], by MrExcel East, 31 March 2012</ref> इसके बाद बाद की स्प्रेडशीटस, जैसे कि [[माइक्रोसॉफ्ट एक्सेल]], और विशिष्ट <code>VLOOKUP</code> तथा <code>HLOOKUP</code> फ़ंक्शंस द्वारा अनुलंबित या क्षैतिज टेबल में लुकअप को सरल बनाने के लिए किया गया है। माइक्रोसॉफ्ट एक्सेल में <code>XLOOKUP</code> फ़ंक्शन 28 अगस्त 2019 से प्रारंभ किया गया है। | ||
== सीमाएं == | == सीमाएं == | ||
| Line 28: | Line 28: | ||
=== [[तुच्छ हैश समारोह|तुच्छ हैश फ़ंक्शन]] === | === [[तुच्छ हैश समारोह|तुच्छ हैश फ़ंक्शन]] === | ||
एक तुच्छ हैश फ़ंक्शन लुकअप के लिए, परिणाम निकालने के लिए अहस्ताक्षरित कच्चे डेटा मान को सीधे एक-आयामी | एक तुच्छ हैश फ़ंक्शन लुकअप के लिए, परिणाम निकालने के लिए अहस्ताक्षरित कच्चे डेटा मान को सीधे एक-आयामी टेबल के सूचकांक के रूप में उपयोग किया जाता है। छोटी रेंज के लिए, यह सबसे तेज़ लुकअप में से एक हो सकता है, यहां तक कि शून्य शाखाओं के साथ द्विआधारी खोज गति से अधिक और [[निरंतर समय]] में निष्पादित हो सकता है।<ref>{{cite book|last1=Cormen|first1=Thomas H.|title=एल्गोरिदम का परिचय|date=2009|publisher=MIT Press|location=Cambridge, Mass.|isbn=9780262033848|pages=253–255|edition=3rd|url=https://mitpress.mit.edu/books/introduction-algorithms|accessdate=26 November 2015}}</ref> | ||
| Line 48: | Line 48: | ||
उपरोक्त कार्यान्वयन के लिए 32-बिट मान के मूल्यांकन के लिए 32 संचालन की आवश्यकता होती है, जो संभावित रूप से शाखाओं में बंटने के कारण कई घड़ी चक्र ले सकता है। इसे एक लुकअप टेबल में [[लूप अनोलिंग]] किया जा सकता है जो बदले में बेहतर प्रदर्शन के लिए तुच्छ हैश फ़ंक्शन का उपयोग करता है।{{r|apress11|p=282-283}} | उपरोक्त कार्यान्वयन के लिए 32-बिट मान के मूल्यांकन के लिए 32 संचालन की आवश्यकता होती है, जो संभावित रूप से शाखाओं में बंटने के कारण कई घड़ी चक्र ले सकता है। इसे एक लुकअप टेबल में [[लूप अनोलिंग]] किया जा सकता है जो बदले में बेहतर प्रदर्शन के लिए तुच्छ हैश फ़ंक्शन का उपयोग करता है।{{r|apress11|p=282-283}} | ||
बिट्स सरणी, 256 प्रविष्टियों के साथ बिट्स_सेट का निर्माण प्रत्येक संभावित बाइट मान में एक बिट सेट की संख्या देकर किया जाता है (उदाहरण के लिए 0x00 = 0, 0x01 = 1, 0x02 = 1, और इसी तरह)। चूंकि एक रनटाइम एल्गोरिदम का उपयोग बिट्स_सेट सरणी उत्पन्न करने के लिए किया जा सकता है, जब आकार को ध्यान में रखा जाता है तो यह घड़ी चक्रों का एक अक्षम उपयोग होता है, इसलिए एक पूर्व-गणना | बिट्स सरणी, 256 प्रविष्टियों के साथ बिट्स_सेट का निर्माण प्रत्येक संभावित बाइट मान में एक बिट सेट की संख्या देकर किया जाता है (उदाहरण के लिए 0x00 = 0, 0x01 = 1, 0x02 = 1, और इसी तरह)। चूंकि एक रनटाइम एल्गोरिदम का उपयोग बिट्स_सेट सरणी उत्पन्न करने के लिए किया जा सकता है, जब आकार को ध्यान में रखा जाता है तो यह घड़ी चक्रों का एक अक्षम उपयोग होता है, इसलिए एक पूर्व-गणना टेबल का उपयोग किया जाता है - चूंकि एक [[संकलन समय]] स्क्रिप्ट का उपयोग गतिशील रूप से उत्पन्न किया जा सकता है टेबल को स्रोत फ़ाइल में उत्पन्न और संलग्न करें। [[पूर्णांक (कंप्यूटर विज्ञान)]] के प्रत्येक बाइट में योग की गणना प्रत्येक बाइट पर तुच्छ हैश फ़ंक्शन लुकअप के माध्यम से की जा सकती है; इस प्रकार, प्रभावी रूप से शाखाओं से बचने के परिणामस्वरूप प्रदर्शन में काफी सुधार हुआ।{{r|apress11|p=284}} | ||
int count_ones(int input_value) { | int count_ones(int input_value) { | ||
| Line 74: | Line 74: | ||
=== इमेज प्रोसेसिंग में लुकअप टेबल === | === इमेज प्रोसेसिंग में लुकअप टेबल === | ||
{{original research section|date=October 2021}} | {{original research section|date=October 2021}} | ||
[[File:Red Green Blue 16 bit Look up Table Sample.svg|thumb|right|लाल (ए), हरा (बी), नीला (सी) 16-बिट लुकअप | [[File:Red Green Blue 16 bit Look up Table Sample.svg|thumb|right|लाल (ए), हरा (बी), नीला (सी) 16-बिट लुकअप टेबल फ़ाइल मानक। (पंक्तियां 14 से 65524 नहीं दिखाई गई हैं)]] | ||
{{quote|"लुकअप टेबल (LUTs) उन कार्यों के मूल्यांकन को अनुकूलित करने के लिए एक उत्कृष्ट तकनीक है जो गणना करने के लिए महंगे हैं और कैश करने के लिए सस्ती हैं। ... टेबल के नमूने के बीच आने वाले डेटा अनुरोधों के लिए, एक इंटरपोलेशन एल्गोरिदम पास के नमूने औसत से उचित अनुमान उत्पन्न कर सकता | |||
<nowiki>{{quote|"लुकअप टेबल (LUTs) उन कार्यों के मूल्यांकन को अनुकूलित करने के लिए एक उत्कृष्ट तकनीक है जो गणना करने के लिए महंगे हैं और कैश करने के लिए सस्ती हैं। ... टेबल के नमूने के बीच आने वाले डेटा अनुरोधों के लिए, एक इंटरपोलेशन एल्गोरिदम पास के नमूने औसत से उचित अनुमान उत्पन्न कर सकता है"।</nowiki><ref>[https://developer.nvidia.com/gpugems/gpugems2/part-iii-high-quality-rendering/chapter-24-using-lookup-tables-accelerate-color nvidia gpu Gems2 : उपयोग-लुकअप -टेबल्स-त्वरण-रंग]</रेफरी>}} | |||
डेटा विश्लेषण अनुप्रयोगों में, जैसे [[मूर्ति प्रोद्योगिकी]], एक लुकअप टेबल (LUT) का उपयोग इनपुट डेटा को अधिक वांछनीय आउटपुट स्वरूप में बदलने के लिए किया जाता है। उदाहरण के लिए, शनि ग्रह की एक ग्रेस्केल तस्वीर को उसके छल्लों में अंतर पर जोर देने के लिए एक रंगीन छवि में बदल दिया जाएगा। | डेटा विश्लेषण अनुप्रयोगों में, जैसे [[मूर्ति प्रोद्योगिकी]], एक लुकअप टेबल (LUT) का उपयोग इनपुट डेटा को अधिक वांछनीय आउटपुट स्वरूप में बदलने के लिए किया जाता है। उदाहरण के लिए, शनि ग्रह की एक ग्रेस्केल तस्वीर को उसके छल्लों में अंतर पर जोर देने के लिए एक रंगीन छवि में बदल दिया जाएगा। | ||
| Line 95: | Line 96: | ||
=== संगणन ज्या === | === संगणन ज्या === | ||
अधिकांश कंप्यूटर केवल बुनियादी अंकगणितीय संचालन करते हैं और सीधे किसी दिए गए मान की ज्या की गणना नहीं कर सकते हैं। इसके बजाय, वे [[कॉरडिक]] एल्गोरिथम या एक जटिल सूत्र का उपयोग करते हैं जैसे निम्न [[टेलर श्रृंखला]] साइन के मान की गणना करने के लिए उच्च स्तर की सटीकता के लिए:<ref name="sharif14">{{cite journal|journal= Journal of Circuits, Systems and Computers|volume=23|number=4|year=2014|first=Haidar|last=Sharif|doi=10.1142/S0218126614500510|url=https://www.worldscientific.com/doi/abs/10.1142/S0218126614500510|title=सिंगल-कोर आर्किटेक्चर के लिए उच्च-प्रदर्शन गणितीय कार्य|publisher=World Scientific}}</ref>{{rp|p=5}} | अधिकांश कंप्यूटर केवल बुनियादी अंकगणितीय संचालन करते हैं और सीधे किसी दिए गए मान की ज्या की गणना नहीं कर सकते हैं। इसके बजाय, वे [[कॉरडिक]] एल्गोरिथम या एक जटिल सूत्र का उपयोग करते हैं जैसे निम्न [[टेलर श्रृंखला]] साइन के मान की गणना करने के लिए उच्च स्तर की सटीकता के लिए:<ref name="sharif14">{{cite journal|journal= Journal of Circuits, Systems and Computers|volume=23|number=4|year=2014|first=Haidar|last=Sharif|doi=10.1142/S0218126614500510|url=https://www.worldscientific.com/doi/abs/10.1142/S0218126614500510|title=सिंगल-कोर आर्किटेक्चर के लिए उच्च-प्रदर्शन गणितीय कार्य|publisher=World Scientific}}</ref>{{rp|p=5}} | ||
चूंकि, यह गणना करने के लिए महंगा हो सकता है, विशेष रूप से धीमे प्रोसेसर पर, और कई अनुप्रयोग हैं, विशेष रूप से पारंपरिक [[कंप्यूटर ग्राफिक्स]] में, जिन्हें प्रति सेकंड हजारों साइन मानों की गणना करने की आवश्यकता होती है। एक सामान्य समाधान | डेटा विश्लेषण अनुप्रयोगों में, जैसे इमेज प्रोसेसिंग, एक लुकअप टेबल (LUT) का उपयोग इनपुट डेटा को अधिक वांछनीय आउटपुट स्वरूप में बदलने के लिए किया जाता है। उदाहरण के लिए, शनि ग्रह की एक ग्रेस्केल तस्वीर को उसके छल्लों में अंतर पर जोर देने के लिए एक रंगीन छवि में बदल दिया जाएगा। | ||
लुकअप टेबलओं का उपयोग करके रन-टाइम संगणनाओं को कम करने का एक उत्कृष्ट उदाहरण एक त्रिकोणमिति गणना का परिणाम प्राप्त करना है, जैसे मान की साइन। त्रिकोणमितीय कार्यों की गणना एक कंप्यूटिंग अनुप्रयोग को काफी धीमा कर सकती है। एक ही एप्लिकेशन बहुत जल्द समाप्त हो सकता है जब यह पहली बार कई मानों की साइन का पूर्व-गणना करता है, उदाहरण के लिए प्रत्येक पूर्ण संख्या में डिग्री के लिए (टेबल को संकलन समय पर स्थिर चर के रूप में परिभाषित किया जा सकता है, बार-बार रन टाइम लागत को कम करता है)। जब प्रोग्राम को मान की ज्या की आवश्यकता होती है, तो यह मेमोरी एड्रेस से निकटतम ज्या मान को पुनः प्राप्त करने के लिए लुकअप टेबल का उपयोग कर सकता है, और गणितीय सूत्र द्वारा गणना करने के अतिरिक्त वांछित मान की ज्या में प्रक्षेपित भी कर सकता है। इस प्रकार कंप्यूटर सिस्टम में गणित सहसंसाधकों द्वारा लुकअप टेबलओं का उपयोग किया जाता है। लुकअप टेबल में एक त्रुटि इंटेल के कुख्यात फ्लोटिंग-पॉइंट डिवाइड बग के लिए जिम्मेदार थी। | |||
एकल चर के कार्य (जैसे साइन और कोसाइन) एक साधारण सरणी द्वारा कार्यान्वित किए जा सकते हैं। दो या दो से अधिक चर वाले कार्यों के लिए बहुआयामी सरणी अनुक्रमण तकनीकों की आवश्यकता होती है। बाद वाला स्थिति इस प्रकार x और y मानों की सीमित सीमा के लिए '''x<sup>y</sup>''' की गणना करने के लिए फ़ंक्शन को प्रतिस्थापित करने के लिए [x] [y] की दो-आयामी सरणी को नियोजित कर सकता है। जिन कार्यों के एक से अधिक परिणाम हैं, उन्हें लुकअप टेबलओं के साथ कार्यान्वित किया जा सकता है जो संरचनाओं की सरणियाँ हैं। | |||
जैसा कि उल्लेख किया गया है, ऐसे मध्यवर्ती समाधान हैं जो कम मात्रा में गणना के साथ संयोजन में टेबलओं का उपयोग करते हैं, अधिकांश इंटरपोलेशन का उपयोग करते हुए। प्रक्षेप के साथ संयुक्त पूर्व-गणना उन मानों के लिए उच्च यथार्ता उत्पन्न कर सकती है जो दो पूर्व-गणना किए गए मानों के बीच आते हैं। इस तकनीक को निष्पादित करने के लिए थोड़ा अधिक समय की आवश्यकता होती है, लेकिन उच्च यथार्ता की आवश्यकता वाले अनुप्रयोगों में यथार्ता को बहुत बढ़ा सकता है। पूर्व-गणना किए जा रहे मानों के आधार पर, प्रक्षेप के साथ पूर्व-गणना का उपयोग यथार्ता बनाए रखते हुए लुकअप टेबल के आकार को छोटा करने के लिए भी किया जा सकता है। | |||
इमेज प्रोसेसिंग में, लुकअप टेबल को अधिकांश LUTs (या 3DLUT) कहा जाता है, और इंडेक्स वैल्यू की प्रत्येक श्रेणी के लिए आउटपुट वैल्यू देता है। एक सामान्य LUT, जिसे कलरमैप या पैलेट कहा जाता है, का उपयोग रंग और तीव्रता मान निर्धारित करने के लिए किया जाता है जिसके साथ एक विशेष छवि प्रदर्शित की जाएगी। संगणित टोमोग्राफी में, "विंडोिंग" मापा विकिरण की तीव्रता को प्रदर्शित करने के तरीके को निर्धारित करने के लिए संबंधित अवधारणा को संदर्भित करता है। | |||
अधिकांश प्रभावी होने के बावजूद, लुकअप टेबल को नियोजित करने के परिणामस्वरूप एक गंभीर जुर्माना हो सकता है यदि LUT की जगह की जाने वाली गणना अपेक्षाकृत सरल हो। मेमोरी पुनर्प्राप्ति समय और मेमोरी आवश्यकताओं की जटिलता अनुप्रयोग संचालन समय और सिस्टम जटिलता को सीधे सूत्र गणना द्वारा आवश्यक होने के सापेक्ष बढ़ा सकती है। कैश को प्रदूषित करने की संभावना भी एक समस्या बन सकती है। बड़ी टेबल के लिए टेबल एक्सेस लगभग निश्चित रूप से कैश मिस का कारण बनता है। यह घटना तेजी से एक मुद्दा बनती जा रही है क्योंकि प्रोसेसर आउटस्पेस मेमोरी। रीमटेरियलाइज़ेशन, एक कंपाइलर ऑप्टिमाइज़ेशन में एक समान समस्या दिखाई देती है। कुछ परिवेशों में, जैसे कि जावा प्रोग्रामिंग लैंग्वेज, प्रत्येक लुकअप के लिए एक अतिरिक्त तुलना और शाखा से जुड़ी अनिवार्य सीमा-जांच के कारण टेबल लुकअप और भी महंगा हो सकता है। | |||
एक आवश्यक ऑपरेशन के लिए लुकअप टेबल का निर्माण कब संभव है, इस पर दो मूलभूत सीमाएँ हैं। एक उपलब्ध मेमोरी की मात्रा है: टेबल के लिए उपलब्ध स्थान से बड़ी लुकअप टेबल का निर्माण नहीं किया जा सकता है, चूँकि लुकअप समय की कीमत पर डिस्क-आधारित लुकअप टेबल बनाना संभव है। दूसरा वह समय है जो पहली बार टेबल मानों की गणना करने के लिए आवश्यक है; चूँकि इसे सामान्यतः केवल एक बार करने की आवश्यकता होती है, यदि इसमें निषेधात्मक रूप से लंबा समय लगता है, तो यह लुकअप टेबल के उपयोग को एक अनुपयुक्त समाधान बना सकता है। जैसा कि पहले बताया गया है, टेबल को कई स्थितियों में स्थिर रूप से परिभाषित किया जा सकता है। | |||
=== संगणक ज्या === | |||
अधिकांश कंप्यूटर केवल बुनियादी अंकगणितीय संचालन करते हैं और सीधे किसी दिए गए मान की ज्या की गणना नहीं कर सकते हैं। इसके अतिरिक्त, वे कॉर्डिक एल्गोरिथम या एक जटिल सूत्र का उपयोग करते हैं जैसे कि निम्न टेलर श्रृंखला साइन के मूल्य की उच्च स्तर की यथार्ता की गणना करने के लिए<<ref name="sharif14">{{cite journal|journal= Journal of Circuits, Systems and Computers|volume=23|number=4|year=2014|first=Haidar|last=Sharif|doi=10.1142/S0218126614500510|url=https://www.worldscientific.com/doi/abs/10.1142/S0218126614500510|title=High-performance mathematical functions for single-core architectures|publisher=World Scientific}}</ref>{{rp|p=5}} | |||
:<math>\operatorname{sin}(x) \approx x - \frac{x^3}{6} + \frac{x^5}{120} - \frac{x^7}{5040}</math> (for ''x'' close to 0) | |||
चूंकि, यह गणना करने के लिए महंगा हो सकता है, विशेष रूप से धीमे प्रोसेसर पर, और कई अनुप्रयोग हैं, विशेष रूप से पारंपरिक [[कंप्यूटर ग्राफिक्स]] में, जिन्हें प्रति सेकंड हजारों साइन मानों की गणना करने की आवश्यकता होती है। एक सामान्य समाधान प्रारंभ में कई समान रूप से वितरित मानों की ज्या की गणना करना है, और फिर x की ज्या खोजने के लिए हम सरणी इंडेक्सिंग ऑपरेशन के माध्यम से x के निकटतम मान की ज्या चुनते हैं। यह सही मान के करीब होगा क्योंकि ज्या परिवर्तन की परिबद्ध दर के साथ एक सतत फलन है।{{r|sharif14|p=6}} उदाहरण के लिए:<ref>{{cite book|title= असेंबली लैंग्वेज की कला, दूसरा संस्करण|author=Randall Hyde|date=1 March 2010|publisher=No Starch Press|isbn=978-1593272074|url=https://www.ic.unicamp.br/~pannain/mc404/aulas/pdfs/Art%20Of%20Intel%20x86%20Assembly.pdf|via=University of Campinas Institute of Computing}}</ref>{{rp|p=545-548}} | |||
real array sine_table[-1000..1000] | |||
for x from -1000 to 1000 | |||
sine_table[x] = sine(pi * x / 1000) | |||
function lookup_sine(x) | |||
return sine_table[round(1000 * x / pi)] | |||
[[File:Interpolation example linear.svg|thumb|साइन फलन के एक हिस्से पर रेखीय प्रक्षेप|दाहिना]]दुर्भाग्य से, टेबल के लिए काफी जगह की आवश्यकता होती है: यदि IEEE डबल-परिशुद्धता फ़्लोटिंग-पॉइंट नंबरों का उपयोग किया जाता है, तो 16,000 से अधिक बाइट्स की आवश्यकता होगी। हम कम मानक का उपयोग कर सकते हैं, लेकिन तब हमारी यथार्ता काफी खराब हो जाएगी। एक अच्छा समाधान रैखिक इंटरपोलेशन है, जो मान के दोनों ओर टेबल में दो बिंदुओं के बीच एक रेखा खींचता है और उस रेखा पर उत्तर का पता लगाता है। यह अभी भी गणना करने में तेज है, और साइन फ़ंक्शन जैसे सुचारू कार्यों के लिए अधिक यथार्त है। यहाँ रैखिक प्रक्षेप का उपयोग करते हुए एक उदाहरण दिया गया है: | |||
function lookup_sine(x) | |||
x1 = floor(x*1000/pi) | |||
y1 = sine_table[x1] | |||
y2 = sine_table[x1+1] | |||
return y1 + (y2-y1)*(x*1000/pi-x1) | |||
रैखिक इंटरपोलेशन एक इंटरपोलेटेड फ़ंक्शन प्रदान करता है जो निरंतर है, लेकिन सामान्य रूप से निरंतर [[यौगिक]] नहीं होगा। टेबल लुकअप के सहज अंतर्वेशन के लिए जो निरंतर है और निरंतर पहला व्युत्पन्न है, किसी को क्यूबिक हर्मिट स्पलाइन का उपयोग करना चाहिए। | |||
एक अन्य समाधान जो अंतरिक्ष के एक चौथाई का उपयोग करता है लेकिन गणना करने में थोड़ा अधिक समय लेता है, साइन और कोसाइन के बीच संबंधों को उनके समरूपता नियमों के साथ ध्यान में रखना होगा। इस स्थिति में, पहले चतुर्थांश (अर्थात sin(0..pi/2)) के लिए साइन फ़ंक्शन का उपयोग करके लुकअप टेबल की गणना की जाती है। जब हमें एक मान की आवश्यकता होती है, तो हम एक चर को पहले चतुर्थांश में रखे कोण के रूप में निर्दिष्ट करते हैं। फिर हम कोण को चार चतुर्थांशों में रखते हैं (आवश्यक नहीं है यदि मान हमेशा 0 और 2 * पीआई के बीच होते हैं) और सही मान लौटाते हैं (अर्थात् पहला चतुर्थांश एक सीधा रिटर्न है, दूसरा चतुर्थांश पीआई / 2-एक्स से पढ़ा जाता है, तीसरा और चौथे क्रमशः पहले और दूसरे के नकारात्मक हैं)। कोसाइन के लिए, हमें केवल पीआई/2 (अर्थात् एक्स + पीआई/2) द्वारा स्थानांतरित कोण वापस करना होगा। स्पर्शरेखा के लिए, हम साइन को कोसाइन से विभाजित करते हैं (कार्यान्वयन के आधार पर विभाजित-दर-शून्य हैंडलिंग की आवश्यकता हो सकती है): | |||
function init_sine() for x from 0 to (360/4)+1 | |||
sine_table[x] = sin(2*pi * x / 360) | |||
function lookup_sine(x) | |||
x = wrap x from 0 to 360 | |||
y = mod (x, 90) | |||
if (x < 90) return sine_table[ y] | |||
if (x < 180) return sine_table[90-y] | |||
if (x < 270) return -sine_table[ y] | |||
return -sine_table[90-y] | |||
function lookup_cosine(x) | |||
return lookup_sine(x + 90) | |||
function lookup_tan(x) | |||
return lookup_sine(x) / lookup_cosine(x) | |||
इंटरपोलेशन का उपयोग करते समय, लुकअप टेबल के आकार को गैर-समान मानककरण का उपयोग करके कम किया जा सकता है, जिसका अर्थ है कि जहां फ़ंक्शन सीधे के करीब है, हम कुछ मानक बिंदुओं का उपयोग करते हैं, जबकि जहां यह तेजी से मूल्य बदलता है, हम सन्निकटन रखने के लिए अधिक मानक बिंदुओं का उपयोग करते हैं। वास्तविक वक्र के करीब। अधिक जानकारी के लिए इंटरपोलेशन देखें | |||
प्रक्षेप का उपयोग करते समय, लुकअप टेबल के आकार को '[[गैर-समान नमूनाकरण|गैर-समान मानककरण]]'' का उपयोग करके कम किया जा सकता है, जिसका अर्थ है कि जहां फ़ंक्शन सीधे के करीब है, हम कुछ मानक बिंदुओं का उपयोग करते हैं, जबकि जहां यह तेजी से मान बदलता है हम सन्निकटन रखने के लिए अधिक वास्तविक वक्र के करीब मानक बिंदुओं का उपयोग करते हैं । अधिक जानकारी के [[रेखिक आंतरिक]] देखें।'' | |||