लुकअप टेबल: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(14 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>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|मेमोइज़ेशन]]), के भाग के रूप में परिकलित (या "पूर्व-प्राप्त"), या एप्लिकेशन-विशिष्ट प्लेटफ़ॉर्म में हार्डवेयर में संग्रहीत भी किया जा सकता है। किसी सरणी में मान्य (या अमान्य) आइटमों की सूची के विरुद्ध मिलान करके इनपुट मानों को मान्य करने के लिए लुकअप तालिकाओं का व्यापक रूप से उपयोग किया जाता है, और कुछ प्रोग्रामिंग भाषाओं में, मिलान इनपुट को संसाधित करने के लिए पॉइंटर फ़ंक्शन (या लेबल के लिए ऑफ़सेट) सम्मिलित हो सकते हैं। प्रोग्राम योग्य हार्डवेयर कार्यात्मकता प्रदान करने के लिए [[क्षेत्र में प्रोग्राम की जा सकने वाली द्वार श्रंखला]] पुन: विन्यास योग्य, हार्डवेयर-कार्यान्वित, लुकअप तालिकाओं का व्यापक उपयोग करता है।
[[कंप्यूटर विज्ञान]] में, एक लुकअप टेबल (एलयूटी) एक [[सरणी डेटा संरचना|सरणी]]  है जो रनटाइम (प्रोग्राम जीवनचक्र चरण) संगणना को एक सरल सरणी इंडेक्सिंग ऑपरेशन से बदल देती है। प्रक्रिया को डायरेक्ट एड्रेसिंग कहा जाता है और एलयूटी [[हैश टेबल]] से इस तरह से भिन्न होते हैं कि, एक मान प्राप्त करने के लिए <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वीं सदी की तालिका का एक भाग।]]कंप्यूटर के आगमन से पहले, मानों की लुकअप टेबल का उपयोग जटिल कार्यों की हाथ की गणना में तेजी लाने के लिए किया जाता था, जैसे कि [[त्रिकोणमिति]], सामान्य लघुगणक और सांख्यिकीय घनत्व कार्यों में।<ref>{{cite book
[[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 ईस्वी) भारत में, [[आर्यभट]]्ट ने पहली आर्यभट्ट की ज्या तालिका बनाई, जिसे उन्होंने संस्कृत-अक्षर-आधारित संख्या प्रणाली में एन्कोड किया। 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 तक) की गणना से बचने के लिए गुणा तालिका को याद करना सिखाया जाता है।
प्राचीन (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) का प्रारंभिक संस्करण सम्मिलित था। <code>LOOKUP</code> अपने मूल 20 कार्यों में कार्य करता है।<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 से शुरू किया गया है।
लुकअप टेबलएँ कंप्यूटर [[स्प्रेडशीट|स्प्रेडशीटस]] में कार्यान्वित प्रारंभिक कार्यात्मकताओं में से एक थीं, जिसमें [[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 से प्रारंभ किया गया है।


== सीमाएं ==
== सीमाएं ==
हालांकि LUT के प्रदर्शन की गारंटी है <math>O(1)</math> लुकअप ऑपरेशन के लिए, किन्हीं भी दो संस्थाओं या मानों में एक ही कुंजी नहीं हो सकती है <math>k</math>. जब ब्रह्मांड का आकार (गणित) <math>\cup</math>—जहाँ कुंजियाँ खींची जाती हैं—बड़ी होती है, यह अव्यावहारिक हो सकता है या [[स्मृति]] में संग्रहीत करना असंभव हो सकता है। इसलिए, इस मामले में, [[हैश टेबल]] एक बेहतर विकल्प होगा।{{r|Kwok95|p=468}}
चूंकि LUT का प्रदर्शन लुकअप ऑपरेशन के लिए <math>O(1)</math> की गारंटी है, कोई भी दो निकाय या मानों में एक ही कुंजी <math>k</math> नहीं हो सकती है. जब ब्रह्मांड का आकार (गणित) <math>\cup</math>—जहाँ कुंजियाँ खींची जाती हैं—बड़ी होती है, तो [[स्मृति]] में संग्रहीत करना अव्यावहारिक या असंभव हो सकता है। इसलिए, इस स्थिति में, [[हैश टेबल]] एक बेहतर विकल्प होगा।{{r|Kwok95|p=468}}




== उदाहरण ==
== उदाहरण ==


=== [[तुच्छ हैश समारोह]] ===
=== [[तुच्छ हैश समारोह|तुच्छ हैश फ़ंक्शन]] ===
एक तुच्छ हैश फ़ंक्शन लुकअप के लिए, परिणाम निकालने के लिए अहस्ताक्षरित कच्चे डेटा मान को सीधे एक-आयामी तालिका के सूचकांक के रूप में उपयोग किया जाता है। छोटी रेंज के लिए, यह सबसे तेज़ लुकअप में से एक हो सकता है, यहां तक ​​कि शून्य शाखाओं के साथ द्विआधारी खोज गति से अधिक और [[निरंतर समय]] में निष्पादित हो सकता है।<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>
एक तुच्छ हैश फ़ंक्शन लुकअप के लिए, परिणाम निकालने के लिए अहस्ताक्षरित कच्चे डेटा मान को सीधे एक-आयामी टेबल के सूचकांक के रूप में उपयोग किया जाता है। छोटी रेंज के लिए, यह सबसे तेज़ लुकअप में से एक हो सकता है, यहां तक ​​कि शून्य शाखाओं के साथ द्विआधारी खोज गति से अधिक और [[निरंतर समय]] में निष्पादित हो सकता है।<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>




==== बाइट्स की एक श्रृंखला में बिट्स की गिनती ====
==== बाइट्स की एक श्रृंखला में बिट्स की गिनती ====
एक असतत समस्या जो कई कंप्यूटरों पर हल करने के लिए महंगी है, वह बिट्स की संख्या की गणना करना है जो एक (बाइनरी) संख्या में 1 पर सेट होती है, जिसे कभी-कभी [[हैमिंग वजन]] कहा जाता है। उदाहरण के लिए, बाइनरी में दशमलव संख्या 37 00100101 है, इसलिए इसमें तीन बिट हैं जो बाइनरी 1 पर सेट हैं।<ref name="apress11">{{cite book|doi=10.1007/978-1-4302-4159-1_26|publisher=Apress|url=https://link.springer.com/chapter/10.1007/978-1-4302-4159-1_26|title= प्रदर्शन के लिए विकास। में: पैकेटसी प्रोग्रामिंग|author1=Jungck P.|author2=Dencan R.|author3=Mulcahy D.|year=2011|isbn=978-1-4302-4159-1}}</ref>{{rp|p=282}}
<nowiki>:</nowiki>एक असतत समस्या जो कई कंप्यूटरों पर हल करने के लिए महंगी है, वह बिट्स की संख्या की गणना करना है जो एक (बाइनरी) संख्या में 1 पर सेट होती है, जिसे कभी-कभी [[हैमिंग वजन]] कहा जाता है। उदाहरण के लिए, बाइनरी में दशमलव संख्या "37" बाइनरी में "00100101" है, इसलिए इसमें तीन बिट्स हैं जो बाइनरी 1 पर सेट हैं।<ref name="apress11">{{cite book|doi=10.1007/978-1-4302-4159-1_26|publisher=Apress|url=https://link.springer.com/chapter/10.1007/978-1-4302-4159-1_26|title= प्रदर्शन के लिए विकास। में: पैकेटसी प्रोग्रामिंग|author1=Jungck P.|author2=Dencan R.|author3=Mulcahy D.|year=2011|isbn=978-1-4302-4159-1}}</ref>{{rp|p=282}}
 
C (प्रोग्रामिंग लैंग्वेज) कोड का एक सरल उदाहरण, जिसे एक इंट में 1 बिट गिनने के लिए डिज़ाइन किया गया है, ऐसा दिखाई दे सकता है:{{r|apress11|p=283}}
C (प्रोग्रामिंग लैंग्वेज) कोड का एक सरल उदाहरण, जिसे एक इंट में 1 बिट गिनने के लिए डिज़ाइन किया गया है, ऐसा दिखाई दे सकता है:{{r|apress11|p=283}}
<वाक्यविन्यास प्रकाश लैंग = सी>
int count_ones (अहस्ताक्षरित int x) {
  इंट परिणाम = 0;
  जबकि (एक्स! = 0) {
    एक्स = एक्स और (एक्स - 1);
    परिणाम ++;
  }
  वापसी परिणाम;
}</syntaxhighlight>


उपरोक्त कार्यान्वयन के लिए 32-बिट मान के मूल्यांकन के लिए 32 संचालन की आवश्यकता होती है, जो नियंत्रण प्रवाह के कारण संभावित रूप से प्रति निर्देश कई चक्र ले सकता है। यह लुकअप टेबल में [[लूप अनोलिंग]] हो सकता है जो बदले में बेहतर प्रदर्शन के लिए तुच्छ हैश फ़ंक्शन का उपयोग करता है।{{r|apress11|p=282-283}}
 
बिट्स सरणी, 256 प्रविष्टियों के साथ बिट्स_सेट का निर्माण प्रत्येक संभावित बाइट मान में एक बिट सेट की संख्या देकर किया जाता है (उदाहरण के लिए 0x00 = 0, 0x01 = 1, 0x02 = 1, और इसी तरह)। हालांकि एक रनटाइम (प्रोग्राम जीवनचक्र चरण) एल्गोरिदम का उपयोग बिट्स_सेट सरणी उत्पन्न करने के लिए किया जा सकता है, जब आकार को ध्यान में रखा जाता है तो यह घड़ी चक्रों का एक अक्षम उपयोग होता है, इसलिए एक प्रीकंप्यूटेड तालिका का उपयोग किया जाता है - हालांकि एक [[संकलन समय]] स्क्रिप्ट को गतिशील रूप से उपयोग किया जा सकता है तालिका को स्रोत फ़ाइल में उत्पन्न और संलग्न करें। [[पूर्णांक (कंप्यूटर विज्ञान)]] के प्रत्येक बाइट में योग की गणना प्रत्येक बाइट पर तुच्छ हैश फ़ंक्शन लुकअप के माध्यम से की जा सकती है; इस प्रकार, प्रभावी रूप से शाखाओं से बचने के परिणामस्वरूप प्रदर्शन में काफी सुधार हुआ।{{r|apress11|p=284}}
  int count_ones(unsigned int x) {
<वाक्यविन्यास प्रकाश लैंग = सी>
 
इंट काउंट_ओन्स (इंट इनपुट_वैल्यू) {
  int result = 0;
  यूनियन फोर_बाइट्स {
  while (x!= 0) {
    int big_int;
    x = x & (x - 1);
    चार प्रत्येक_बाइट [4];
    result++;
  } ऑपरेंड = इनपुट_वैल्यू;
  }
  कॉन्स्ट इंट बिट्स_सेट [256] = {
  return result;
      0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4,
}
      2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
उपरोक्त कार्यान्वयन के लिए 32-बिट मान के मूल्यांकन के लिए 32 संचालन की आवश्यकता होती है, जो संभावित रूप से शाखाओं में बंटने के कारण कई घड़ी चक्र ले सकता है। इसे एक लुकअप टेबल में [[लूप अनोलिंग]] किया जा सकता है जो बदले में बेहतर प्रदर्शन के लिए तुच्छ हैश फ़ंक्शन का उपयोग करता है।{{r|apress11|p=282-283}}
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4,
 
      2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
बिट्स सरणी, 256 प्रविष्टियों के साथ बिट्स_सेट का निर्माण प्रत्येक संभावित बाइट मान में एक बिट सेट की संख्या देकर किया जाता है (उदाहरण के लिए 0x00 = 0, 0x01 = 1, 0x02 = 1, और इसी तरह)। चूंकि एक रनटाइम एल्गोरिदम का उपयोग बिट्स_सेट सरणी उत्पन्न करने के लिए किया जा सकता है, जब आकार को ध्यान में रखा जाता है तो यह घड़ी चक्रों का एक अक्षम उपयोग होता है, इसलिए एक पूर्व-गणना टेबल का उपयोग किया जाता है - चूंकि एक [[संकलन समय]] स्क्रिप्ट का उपयोग गतिशील रूप से उत्पन्न किया जा सकता है टेबल को स्रोत फ़ाइल में उत्पन्न और संलग्न करें। [[पूर्णांक (कंप्यूटर विज्ञान)]] के प्रत्येक बाइट में योग की गणना प्रत्येक बाइट पर तुच्छ हैश फ़ंक्शन लुकअप के माध्यम से की जा सकती है; इस प्रकार, प्रभावी रूप से शाखाओं से बचने के परिणामस्वरूप प्रदर्शन में काफी सुधार हुआ।{{r|apress11|p=284}}
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6,
 
      4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  int count_ones(int input_value) {
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5,
 
      3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  union four_bytes {
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6,
<nowiki> </nowiki>  int big_int;
      4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
<nowiki> </nowiki>  char each_byte[4];
      4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};
<nowiki> </nowiki> } operand = input_value;
  वापसी (बिट्स_सेट [ऑपरेंड.च_बाइट [0 + बिट्स_सेट [ऑपरेंड.च_बाइट [1 +]
<nowiki> </nowiki> const int bits_set[256] = {
          बिट्स_सेट [ऑपरेंड.च_बाइट [2 + बिट्स_सेट [ऑपरेंड.च_बाइट [3]);
<nowiki> </nowiki>    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4,
}}
<nowiki> </nowiki>    2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
</वाक्यविन्यास हाइलाइट>
<nowiki> </nowiki>    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4,
<nowiki> </nowiki>    2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
<nowiki> </nowiki>    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6,
<nowiki> </nowiki>    4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
<nowiki> </nowiki>    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5,
<nowiki> </nowiki>    3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
<nowiki> </nowiki>    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6,
<nowiki> </nowiki>    4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
<nowiki> </nowiki>    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};
<nowiki> </nowiki> return (bits_set[operand.each_byte[0]] + bits_set[operand.each_byte[1]] +
<nowiki> </nowiki>        bits_set[operand.each_byte[2]] + bits_set[operand.each_byte[3]]);
}}


=== इमेज प्रोसेसिंग में लुकअप टेबल ===
=== इमेज प्रोसेसिंग में लुकअप टेबल ===
{{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-बिट लुकअप तालिका फ़ाइल नमूना। (पंक्तियां 14 से 65524 नहीं दिखाई गई हैं)]]
[[File:Red Green Blue 16 bit Look up Table Sample.svg|thumb|right|लाल (ए), हरा (बी), नीला (सी) 16-बिट लुकअप टेबल फ़ाइल मानक। (पंक्तियां 14 से 65524 नहीं दिखाई गई हैं)]]




{{quote|"Lookup tables (LUTs) are an excellent technique for optimizing the evaluation of functions that are expensive to compute and inexpensive to cache. ... For data requests that fall between the table's samples, an interpolation algorithm can generate reasonable approximations by averaging nearby samples."<ref>[https://developer.nvidia.com/gpugems/gpugems2/part-iii-high-quality-rendering/chapter-24-using-lookup-tables-accelerate-color nvidia gpu gems2 : using-lookup-tables-accelerate-color]</ref>}}
 
<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 88: Line 92:
अधिकांश प्रभावी होने के बावजूद, लुकअप टेबल को नियोजित करने के परिणामस्वरूप एक गंभीर जुर्माना हो सकता है यदि 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=सिंगल-कोर आर्किटेक्चर के लिए उच्च-प्रदर्शन गणितीय कार्य|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}}
:<math>\operatorname{sin}(x) \approx x - \frac{x^3}{6} + \frac{x^5}{120} - \frac{x^7}{5040}</math> (एक्स के करीब 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}}
डेटा विश्लेषण अनुप्रयोगों में, जैसे इमेज प्रोसेसिंग, एक लुकअप टेबल (LUT) का उपयोग इनपुट डेटा को अधिक वांछनीय आउटपुट स्वरूप में बदलने के लिए किया जाता है। उदाहरण के लिए, शनि ग्रह की एक ग्रेस्केल तस्वीर को उसके छल्लों में अंतर पर जोर देने के लिए एक रंगीन छवि में बदल दिया जाएगा।
<वाक्यविन्यास लैंग = abap>
 
वास्तविक सरणी साइन_टेबल [-1000..1000]
लुकअप टेबलओं का उपयोग करके रन-टाइम संगणनाओं को कम करने का एक उत्कृष्ट उदाहरण एक त्रिकोणमिति गणना का परिणाम प्राप्त करना है, जैसे मान की साइन। त्रिकोणमितीय कार्यों की गणना एक कंप्यूटिंग अनुप्रयोग को काफी धीमा कर सकती है। एक ही एप्लिकेशन बहुत जल्द समाप्त हो सकता है जब यह पहली बार कई मानों की साइन का पूर्व-गणना करता है, उदाहरण के लिए प्रत्येक पूर्ण संख्या में डिग्री के लिए (टेबल को संकलन समय पर स्थिर चर के रूप में परिभाषित किया जा सकता है, बार-बार रन टाइम लागत को कम करता है)। जब प्रोग्राम को मान की ज्या की आवश्यकता होती है, तो यह मेमोरी एड्रेस से निकटतम ज्या मान को पुनः प्राप्त करने के लिए लुकअप टेबल का उपयोग कर सकता है, और गणितीय सूत्र द्वारा गणना करने के अतिरिक्त वांछित मान की ज्या में प्रक्षेपित भी कर सकता है। इस प्रकार कंप्यूटर सिस्टम में गणित सहसंसाधकों द्वारा लुकअप टेबलओं का उपयोग किया जाता है। लुकअप टेबल में एक त्रुटि इंटेल के कुख्यात फ्लोटिंग-पॉइंट डिवाइड बग के लिए जिम्मेदार थी।
एक्स के लिए -1000 से 1000 तक
 
    साइन_टेबल [एक्स] = साइन (पीआई * एक्स / 1000)
एकल चर के कार्य (जैसे साइन और कोसाइन) एक साधारण सरणी द्वारा कार्यान्वित किए जा सकते हैं। दो या दो से अधिक चर वाले कार्यों के लिए बहुआयामी सरणी अनुक्रमण तकनीकों की आवश्यकता होती है। बाद वाला स्थिति इस प्रकार x और y मानों की सीमित सीमा के लिए '''x<sup>y</sup>''' की गणना करने के लिए फ़ंक्शन को प्रतिस्थापित करने के लिए [x] [y] की दो-आयामी सरणी को नियोजित कर सकता है। जिन कार्यों के एक से अधिक परिणाम हैं, उन्हें लुकअप टेबलओं के साथ कार्यान्वित किया जा सकता है जो संरचनाओं की सरणियाँ हैं।
 
जैसा कि उल्लेख किया गया है, ऐसे मध्यवर्ती समाधान हैं जो कम मात्रा में गणना के साथ संयोजन में टेबलओं का उपयोग करते हैं, अधिकांश इंटरपोलेशन का उपयोग करते हुए। प्रक्षेप के साथ संयुक्त पूर्व-गणना उन मानों के लिए उच्च यथार्ता उत्पन्न कर सकती है जो दो पूर्व-गणना किए गए मानों के बीच आते हैं। इस तकनीक को निष्पादित करने के लिए थोड़ा अधिक समय की आवश्यकता होती है, लेकिन उच्च यथार्ता की आवश्यकता वाले अनुप्रयोगों में यथार्ता को बहुत बढ़ा सकता है। पूर्व-गणना किए जा रहे मानों के आधार पर, प्रक्षेप के साथ पूर्व-गणना का उपयोग यथार्ता बनाए रखते हुए लुकअप टेबल के आकार को छोटा करने के लिए भी किया जा सकता है।
 
इमेज प्रोसेसिंग में, लुकअप टेबल को अधिकांश LUTs (या 3DLUT) कहा जाता है, और इंडेक्स वैल्यू की प्रत्येक श्रेणी के लिए आउटपुट वैल्यू देता है। एक सामान्य LUT, जिसे कलरमैप या पैलेट कहा जाता है, का उपयोग रंग और तीव्रता मान निर्धारित करने के लिए किया जाता है जिसके साथ एक विशेष छवि प्रदर्शित की जाएगी। संगणित टोमोग्राफी में, "विंडोिंग" मापा विकिरण की तीव्रता को प्रदर्शित करने के तरीके को निर्धारित करने के लिए संबंधित अवधारणा को संदर्भित करता है।
 
अधिकांश प्रभावी होने के बावजूद, लुकअप टेबल को नियोजित करने के परिणामस्वरूप एक गंभीर जुर्माना हो सकता है यदि LUT की जगह की जाने वाली गणना अपेक्षाकृत सरल हो। मेमोरी पुनर्प्राप्ति समय और मेमोरी आवश्यकताओं की जटिलता अनुप्रयोग संचालन समय और सिस्टम जटिलता को सीधे सूत्र गणना द्वारा आवश्यक होने के सापेक्ष बढ़ा सकती है। कैश को प्रदूषित करने की संभावना भी एक समस्या बन सकती है। बड़ी टेबल के लिए टेबल एक्सेस लगभग निश्चित रूप से कैश मिस का कारण बनता है। यह घटना तेजी से एक मुद्दा बनती जा रही है क्योंकि प्रोसेसर आउटस्पेस मेमोरी। रीमटेरियलाइज़ेशन, एक कंपाइलर ऑप्टिमाइज़ेशन में एक समान समस्या दिखाई देती है। कुछ परिवेशों में, जैसे कि जावा प्रोग्रामिंग लैंग्वेज, प्रत्येक लुकअप के लिए एक अतिरिक्त तुलना और शाखा से जुड़ी अनिवार्य सीमा-जांच के कारण टेबल लुकअप और भी महंगा हो सकता है।
 
एक आवश्यक ऑपरेशन के लिए लुकअप टेबल का निर्माण कब संभव है, इस पर दो मूलभूत सीमाएँ हैं। एक उपलब्ध मेमोरी की मात्रा है: टेबल के लिए उपलब्ध स्थान से बड़ी लुकअप टेबल का निर्माण नहीं किया जा सकता है, चूँकि लुकअप समय की कीमत पर डिस्क-आधारित लुकअप टेबल बनाना संभव है। दूसरा वह समय है जो पहली बार टेबल मानों की गणना करने के लिए आवश्यक है; चूँकि इसे सामान्यतः केवल एक बार करने की आवश्यकता होती है, यदि इसमें निषेधात्मक रूप से लंबा समय लगता है, तो यह लुकअप टेबल के उपयोग को एक अनुपयुक्त समाधान बना सकता है। जैसा कि पहले बताया गया है, टेबल को कई स्थितियों में स्थ