लुकअप टेबल

कंप्यूटर विज्ञान में, एक लुकअप टेबल (एलयूटी) एक सरणी है जो रनटाइम (प्रोग्राम जीवनचक्र चरण) संगणना को एक सरल सरणी इंडेक्सिंग ऑपरेशन से बदल देती है। प्रक्रिया को डायरेक्ट एड्रेसिंग कहा जाता है और एलयूटी हैश टेबल से इस तरह से भिन्न होते हैं कि, एक मान प्राप्त करने के लिए $v$ कुंजी के साथ $k$ , एक हैश तालिका $v$ स्लॉट में $h(k)$ मान संग्रहीत करेगी जहाँ $h$ एक हैश फंकशन है अर्थात् $k$ का उपयोग स्लॉट की गणना करने के लिए किया जाता है, जबकि LUT की स्थिति में, मान $v$ को स्लॉट $k$ में संग्रहीत किया जाता है, इस प्रकार सीधे पता लगाया जा सकता है।^[1]^: 466 प्रसंस्करण समय में बचत महत्वपूर्ण हो सकती है, क्योंकि मेमोरी से मान प्राप्त करना अधिकांश महंगी गणना या इनपुट/आउटपुट ऑपरेशन करने से तेज़ होता है।^[2] तालिकाओं को पूर्वगणना किया जा सकता है और स्थिर मेमोरी आवंटन प्रोग्राम स्टोरेज में संग्रहीत किया जा सकता है, प्रोग्राम के प्रारंभिक चरण (मेमोइज़ेशन), के भाग के रूप में परिकलित (या "पूर्व-प्राप्त"), या एप्लिकेशन-विशिष्ट प्लेटफ़ॉर्म में हार्डवेयर में संग्रहीत भी किया जा सकता है। किसी सरणी में मान्य (या अमान्य) आइटमों की सूची के विरुद्ध मिलान करके इनपुट मानों को मान्य करने के लिए लुकअप तालिकाओं का व्यापक रूप से उपयोग किया जाता है, और कुछ प्रोग्रामिंग भाषाओं में, मिलान इनपुट को संसाधित करने के लिए पॉइंटर फ़ंक्शन (या लेबल के लिए ऑफ़सेट) सम्मिलित हो सकते हैं। प्रोग्राम योग्य हार्डवेयर कार्यात्मकता प्रदान करने के लिए क्षेत्र में प्रोग्राम की जा सकने वाली द्वार श्रंखला पुन: विन्यास योग्य, हार्डवेयर-कार्यान्वित, लुकअप तालिकाओं का व्यापक उपयोग करता है।

इतिहास

संदर्भ पुस्तक अब्रामोवित्ज़ और स्टेगुन में सामान्य लघुगणक की 20वीं सदी की तालिका का एक भाग।

कंप्यूटर के आगमन से पहले, मानों की लुकअप टेबल का उपयोग जटिल कार्यों की हाथ की गणना में तेजी लाने के लिए किया जाता था, जैसे कि त्रिकोणमिति, सामान्य लघुगणक और सांख्यिकीय घनत्व कार्यों में।^[3]

प्राचीन (499 ईस्वी) भारत में, आर्यभट्ट ने पहली ज्या तालिकाओं में से एक का निर्माण किया, जिसे उन्होंने संस्कृत-अक्षर-आधारित संख्या प्रणाली में एन्कोड किया। 493 ईस्वी में, एक्विटाइन के विक्टोरियस ने एक 98-स्तंभ गुणन तालिका लिखी, जिसने (रोमन अंकों में) 2 से 50 बार प्रत्येक संख्या का उत्पाद दिया और पंक्तियाँ एक हज़ार से शुरू होने वाली संख्याओं की एक सूची थीं, जो सैकड़ों से एक सौ तक उतरती थीं। फिर दसियों से दस तक, फिर एक से एक तक, और फिर भिन्नों को 1/144 तक घटाते हुए^[4] आधुनिक स्कूली बच्चों को अधिकांश सबसे अधिक उपयोग की जाने वाली संख्याओं (9 x 9 या 12 x 12 तक) की गणना से बचने के लिए गुणा तालिका को याद करना सिखाया जाता है।

कंप्यूटर के इतिहास के आरंभ में, इनपुट/आउटपुट संचालन विशेष रूप से धीमे थे - यहां तक कि उस समय के प्रोसेसर की गति की तुलना में भी। यह या तो स्टैटिक लुकअप टेबल (प्रोग्राम में एम्बेडेड) या डायनेमिक प्रीफेच्ड एरेज़ बनाकर केवल सबसे सामान्य रूप से होने वाले डेटा आइटम को सम्मिलित करके महंगे रीड ऑपरेशंस को मैन्युअल कैशिंग (कंप्यूटिंग) के रूप में कम करने के लिए समझ में आता है। सिस्टमवाइड कैशिंग की प्रारंभ के बावजूद जो अब इस प्रक्रिया को स्वचालित करता है, एप्लिकेशन स्तर लुकअप तालिकाएं अभी भी डेटा आइटम्स के प्रदर्शन में सुधार कर सकती हैं जो संभवतः ही कभी बदलती हैं।

लुकअप तालिकाएँ कंप्यूटर स्प्रेडशीटस में कार्यान्वित प्रारंभिक कार्यात्मकताओं में से एक थीं, जिसमें VisiCalc (1979) का प्रारंभिक संस्करण के साथ इसके मूल 20 कार्यों में एक LOOKUP फ़ंक्शन भी सम्मिलित था।^[5] इसके बाद बाद की स्प्रेडशीटस, जैसे कि माइक्रोसॉफ्ट एक्सेल, और विशिष्ट VLOOKUP तथा HLOOKUP फ़ंक्शंस द्वारा अनुलंबित या क्षैतिज तालिका में लुकअप को सरल बनाने के लिए किया गया है। माइक्रोसॉफ्ट एक्सेल में XLOOKUP फ़ंक्शन 28 अगस्त 2019 से प्रारंभ किया गया है।

सीमाएं

चूंकि LUT का प्रदर्शन लुकअप ऑपरेशन के लिए $O(1)$ की गारंटी है, कोई भी दो निकाय या मानों में एक ही कुंजी $k$ नहीं हो सकती है. जब ब्रह्मांड का आकार (गणित) $\cup$ —जहाँ कुंजियाँ खींची जाती हैं—बड़ी होती है, तो स्मृति में संग्रहीत करना अव्यावहारिक या असंभव हो सकता है। इसलिए, इस स्थिति में, हैश टेबल एक बेहतर विकल्प होगा।^[1]^: 468

उदाहरण

तुच्छ हैश फ़ंक्शन

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

बाइट्स की एक श्रृंखला में बिट्स की गिनती

:एक असतत समस्या जो कई कंप्यूटरों पर हल करने के लिए महंगी है, वह बिट्स की संख्या की गणना करना है जो एक (बाइनरी) संख्या में 1 पर सेट होती है, जिसे कभी-कभी हैमिंग वजन कहा जाता है। उदाहरण के लिए, बाइनरी में दशमलव संख्या "37" बाइनरी में "00100101" है, इसलिए इसमें तीन बिट्स हैं जो बाइनरी 1 पर सेट हैं।^[7]^: 282

C (प्रोग्रामिंग लैंग्वेज) कोड का एक सरल उदाहरण, जिसे एक इंट में 1 बिट गिनने के लिए डिज़ाइन किया गया है, ऐसा दिखाई दे सकता है:^[7]^: 283

 int count_ones(unsigned int x) {

  int result = 0;
  while (x!= 0) {
    x = x & (x - 1);
    result++;
  }
  return result;
}

उपरोक्त कार्यान्वयन के लिए 32-बिट मान के मूल्यांकन के लिए 32 संचालन की आवश्यकता होती है, जो संभावित रूप से शाखाओं में बंटने के कारण कई घड़ी चक्र ले सकता है। इसे एक लुकअप टेबल में लूप अनोलिंग किया जा सकता है जो बदले में बेहतर प्रदर्शन के लिए तुच्छ हैश फ़ंक्शन का उपयोग करता है।^[7]^: 282-283

बिट्स सरणी, 256 प्रविष्टियों के साथ बिट्स_सेट का निर्माण प्रत्येक संभावित बाइट मान में एक बिट सेट की संख्या देकर किया जाता है (उदाहरण के लिए 0x00 = 0, 0x01 = 1, 0x02 = 1, और इसी तरह)। चूंकि एक रनटाइम एल्गोरिदम का उपयोग बिट्स_सेट सरणी उत्पन्न करने के लिए किया जा सकता है, जब आकार को ध्यान में रखा जाता है तो यह घड़ी चक्रों का एक अक्षम उपयोग होता है, इसलिए एक पूर्व-गणना तालिका का उपयोग किया जाता है - चूंकि एक संकलन समय स्क्रिप्ट का उपयोग गतिशील रूप से उत्पन्न किया जा सकता है तालिका को स्रोत फ़ाइल में उत्पन्न और संलग्न करें। पूर्णांक (कंप्यूटर विज्ञान) के प्रत्येक बाइट में योग की गणना प्रत्येक बाइट पर तुच्छ हैश फ़ंक्शन लुकअप के माध्यम से की जा सकती है; इस प्रकार, प्रभावी रूप से शाखाओं से बचने के परिणामस्वरूप प्रदर्शन में काफी सुधार हुआ।^[7]^: 284

 int count_ones(int input_value) {

  union four_bytes {
    int big_int;
    char each_byte[4];
  } operand = input_value;
  const int bits_set[256] = {
      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,
      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,
      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,
      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,
      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, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
      4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};
  return (bits_set[operand.each_byte[0]] + bits_set[operand.each_byte[1]] +
          bits_set[operand.each_byte[2]] + bits_set[operand.each_byte[3]]);
}}

इमेज प्रोसेसिंग में लुकअप टेबल

लाल (ए), हरा (बी), नीला (सी) 16-बिट लुकअप तालिका फ़ाइल मानक। (पंक्तियां 14 से 65524 नहीं दिखाई गई हैं)

{{quote|"लुकअप टेबल (LUTs) उन कार्यों के मूल्यांकन को अनुकूलित करने के लिए एक उत्कृष्ट तकनीक है जो गणना करने के लिए महंगे हैं और कैश करने के लिए सस्ती हैं। ... टेबल के नमूने के बीच आने वाले डेटा अनुरोधों के लिए, एक इंटरपोलेशन एल्गोरिदम पास के नमूने औसत से उचित अनुमान उत्पन्न कर सकता है। ."Cite error: Closing </ref> missing for <ref> tag^: 5

डेटा विश्लेषण अनुप्रयोगों में, जैसे इमेज प्रोसेसिंग, एक लुकअप टेबल (LUT) का उपयोग इनपुट डेटा को अधिक वांछनीय आउटपुट स्वरूप में बदलने के लिए किया जाता है। उदाहरण के लिए, शनि ग्रह की एक ग्रेस्केल तस्वीर को उसके छल्लों में अंतर पर जोर देने के लिए एक रंगीन छवि में बदल दिया जाएगा।

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

एकल चर के कार्य (जैसे साइन और कोसाइन) एक साधारण सरणी द्वारा कार्यान्वित किए जा सकते हैं। दो या दो से अधिक चर वाले कार्यों के लिए बहुआयामी सरणी अनुक्रमण तकनीकों की आवश्यकता होती है। बाद वाला मामला इस प्रकार x और y मानों की सीमित सीमा के लिए xy की गणना करने के लिए फ़ंक्शन को प्रतिस्थापित करने के लिए [x] [y] की दो-आयामी सरणी को नियोजित कर सकता है। जिन कार्यों के एक से अधिक परिणाम हैं, उन्हें लुकअप तालिकाओं के साथ कार्यान्वित किया जा सकता है जो संरचनाओं की सरणियाँ हैं।

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

इमेज प्रोसेसिंग में, लुकअप टेबल को अक्सर LUTs (या 3DLUT) कहा जाता है, और इंडेक्स वैल्यू की प्रत्येक श्रेणी के लिए आउटपुट वैल्यू देता है। एक सामान्य LUT, जिसे कलरमैप या पैलेट कहा जाता है, का उपयोग रंग और तीव्रता मान निर्धारित करने के लिए किया जाता है जिसके साथ एक विशेष छवि प्रदर्शित की जाएगी। संगणित टोमोग्राफी में, "विंडोिंग" मापा विकिरण की तीव्रता को प्रदर्शित करने के तरीके को निर्धारित करने के लिए संबंधित अवधारणा को संदर्भित करता है।

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

एक आवश्यक ऑपरेशन के लिए लुकअप टेबल का निर्माण कब संभव है, इस पर दो मूलभूत सीमाएँ हैं। एक उपलब्ध मेमोरी की मात्रा है: तालिका के लिए उपलब्ध स्थान से बड़ी लुकअप टेबल का निर्माण नहीं किया जा सकता है, हालांकि लुकअप समय की कीमत पर डिस्क-आधारित लुकअप टेबल बनाना संभव है। दूसरा वह समय है जो पहली बार तालिका मानों की गणना करने के लिए आवश्यक है; हालाँकि इसे आमतौर पर केवल एक बार करने की आवश्यकता होती है, यदि इसमें निषेधात्मक रूप से लंबा समय लगता है, तो यह लुकअप तालिका के उपयोग को एक अनुपयुक्त समाधान बना सकता है। जैसा कि पहले बताया गया है, टेबल को कई मामलों में स्थिर रूप से परिभाषित किया जा सकता है।

संगणक ज्या

अधिकांश कंप्यूटर केवल बुनियादी अंकगणितीय संचालन करते हैं और सीधे किसी दिए गए मान की ज्या की गणना नहीं कर सकते हैं। इसके बजाय, वे कॉर्डिक एल्गोरिथम या एक जटिल सूत्र का उपयोग करते हैं जैसे कि निम्न टेलर श्रृंखला साइन के मूल्य की उच्च स्तर की यथार्ता की गणना करने के लिए

\operatorname {sin} (x)\approx x-{\frac {x^{3}}{6}}+{\frac {x^{5}}{120}}-{\frac {x^{7}}{5040}}

(एक्स के करीब 0 के लिए)

चूंकि, यह गणना करने के लिए महंगा हो सकता है, विशेष रूप से धीमे प्रोसेसर पर, और कई अनुप्रयोग हैं, विशेष रूप से पारंपरिक कंप्यूटर ग्राफिक्स में, जिन्हें प्रति सेकंड हजारों साइन मानों की गणना करने की आवश्यकता होती है। एक सामान्य समाधान शुरू में कई समान रूप से वितरित मानों की ज्या की गणना करना है, और फिर x की ज्या खोजने के लिए हम सरणी इंडेक्सिंग ऑपरेशन के माध्यम से x के निकटतम मान की ज्या चुनते हैं। यह सही मान के करीब होगा क्योंकि ज्या परिवर्तन की परिबद्ध दर के साथ एक सतत फलन है।^[8]^: 6 उदाहरण के लिए:^[9]^: 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)]

दाहिना

दुर्भाग्य से, तालिका के लिए काफी जगह की आवश्यकता होती है: यदि 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)

इंटरपोलेशन का उपयोग करते समय, लुकअप टेबल के आकार को गैर-समान मानककरण का उपयोग करके कम किया जा सकता है, जिसका अर्थ है कि जहां फ़ंक्शन सीधे के करीब है, हम कुछ मानक बिंदुओं का उपयोग करते हैं, जबकि जहां यह तेजी से मूल्य बदलता है, हम सन्निकटन रखने के लिए अधिक मानक बिंदुओं का उपयोग करते हैं। वास्तविक वक्र के करीब। अधिक जानकारी के लिए इंटरपोलेशन देखें

प्रक्षेप का उपयोग करते समय, लुकअप तालिका के आकार को 'गैर-समान मानककरण का उपयोग करके कम किया जा सकता है, जिसका अर्थ है कि जहां फ़ंक्शन सीधे के करीब है, हम कुछ मानक बिंदुओं का उपयोग करते हैं, जबकि जहां यह तेजी से मान बदलता है हम सन्निकटन रखने के लिए अधिक वास्तविक वक्र के करीब मानक बिंदुओं का उपयोग करते हैं । अधिक जानकारी के रेखिक आंतरिक देखें।

लुकअप टेबल के अन्य उपयोग

कैश

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

एक टुकड़ा (टैग) में पते के शेष बिट्स का मान होता है; यदि ये बिट स्मृति पते से पढ़ने या लिखने के लिए मेल खाते हैं, तो दूसरे टुकड़े में इस पते के लिए कैश्ड मान होता है।
दूसरा टुकड़ा उस पते से जुड़े डेटा को बनाए रखता है।

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

हार्डवेयर LUTs

डिजिटल तर्क में, एक लुकअप टेबल को एक बहुसंकेतक के साथ लागू किया जा सकता है, जिसकी चुनिंदा लाइनें एड्रेस सिग्नल द्वारा संचालित होती हैं और जिनके इनपुट ऐरे में निहित तत्वों के मान होते हैं। ये मान या तो हार्ड-वायर्ड हो सकते हैं, जैसा कि ASIC में होता है जिसका उद्देश्य किसी फ़ंक्शन के लिए विशिष्ट होता है, या D लैचेस द्वारा प्रदान किया जाता है जो विन्यास योग्य मानों की अनुमति देता है। (ROM, EPROM, EEPROM, या यादृच्छिक अभिगम स्मृति।)

एक n-बिट LUT किसी भी n-इनपुट बूलियन फ़ंक्शन को LUT में फ़ंक्शन की सत्य तालिका संग्रहीत करके एनकोड कर सकता है। यह बूलियन तर्क फ़ंक्शंस को एन्कोडिंग करने का एक कुशल विधि है, और 4-6 बिट्स इनपुट के साथ LUTs वास्तव में आधुनिक फील्ड-प्रोग्रामेबल गेट एरेज़ (FPGAs) के प्रमुख घटक हैं जो पुन: कॉन्फ़िगर करने योग्य हार्डवेयर लॉजिक क्षमताएं प्रदान करते हैं।

डेटा अधिग्रहण और नियंत्रण प्रणाली

डेटा अधिग्रहण और नियंत्रण प्रणाली में, लुकअप टेबल का उपयोग सामान्यतः निम्नलिखित कार्यों को करने के लिए किया जाता है:

अंशांकन डेटा का अनुप्रयोग, ताकि अनलिब्रेटेड माप या सेटपॉइंट (नियंत्रण प्रणाली) मानों में सुधार लागू किया जा सके; तथा
उपक्रम माप इकाई रूपांतरण; तथा
सामान्य उपयोगकर्ता-परिभाषित संगणना करना।

कुछ प्रणालियों में, इन गणनाओं के लिए बहुपदों को लुकअप तालिकाओं के स्थान पर भी परिभाषित किया जा सकता है।

यह भी देखें

सहयोगी सरणी
शाखा तालिका
लड़की की यथार्त तालिकाएँ
संस्मरण
मेमोरी-बाउंड फ़ंक्शन
शिफ्ट रजिस्टर लुकअप टेबल
पैलेट (कंप्यूटिंग), a.k.a. कलर लुकअप टेबल या CLUT - कंप्यूटर ग्राफिक्स में उपयोग के लिए
3डी लुकअप टेबल - फिल्म उद्योग में उपयोग

संदर्भ

↑ ^1.0 ^1.1 Kwok, W.; Haghighi, K.; Kang, E. (1995). "अग्रिम-सामने त्रिकोणीय जाल पीढ़ी तकनीक के लिए एक कुशल डेटा संरचना". Communications in Numerical Methods in Engineering. Wiley & Sons. 11 (5): 465–473. doi:10.1002/cnm.1640110511.
↑ McNamee, Paul (21 August 1998). "सी ++ में स्वचालित ज्ञापन". Archived from the original on 2019-04-16.{{cite web}}: CS1 maint: unfit URL (link)
↑ Campbell-Kelly, Martin; Croarken, Mary; Robson, Eleanor, eds. (2003). गणितीय तालिकाओं का इतिहास: सुमेर से स्प्रेडशीट तक. Oxford University Press.
↑ 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.)
↑ Bill Jelen: "From 1979 – VisiCalc and LOOKUP"!, by MrExcel East, 31 March 2012
↑ Cormen, Thomas H. (2009). एल्गोरिदम का परिचय (3rd ed.). Cambridge, Mass.: MIT Press. pp. 253–255. ISBN 9780262033848. Retrieved 26 November 2015.
↑ ^7.0 ^7.1 ^7.2 ^7.3 Jungck P.; Dencan R.; Mulcahy D. (2011). प्रदर्शन के लिए विकास। में: पैकेटसी प्रोग्रामिंग. Apress. doi:10.1007/978-1-4302-4159-1_26. ISBN 978-1-4302-4159-1.
↑ Cite error: Invalid <ref> tag; no text was provided for refs named sharif14
↑ Randall Hyde (1 March 2010). असेंबली लैंग्वेज की कला, दूसरा संस्करण (PDF). No Starch Press. ISBN 978-1593272074 – via University of Campinas Institute of Computing.

बाहरी संबंध

Fast table lookup using input character as index for branch table
Art of Assembly: Calculation via Table Lookups
"Bit Twiddling Hacks" (includes lookup tables) By Sean Eron Anderson of Stanford University
Memoization in C++ by Paul McNamee, Johns Hopkins University showing savings
"The Quest for an Accelerated Population Count" by Henry S. Warren, Jr.

[Kwok95-1] 1.0 ^1.1 Kwok, W.; Haghighi, K.; Kang, E. (1995). "अग्रिम-सामने त्रिकोणीय जाल पीढ़ी तकनीक के लिए एक कुशल डेटा संरचना". Communications in Numerical Methods in Engineering. Wiley & Sons. 11 (5): 465–473. doi:10.1002/cnm.1640110511.

[2] McNamee, Paul (21 August 1998). "सी ++ में स्वचालित ज्ञापन". Archived from the original on 2019-04-16.{{cite web}}: CS1 maint: unfit URL (link)

[3] Campbell-Kelly, Martin; Croarken, Mary; Robson, Eleanor, eds. (2003). गणितीय तालिकाओं का इतिहास: सुमेर से स्प्रेडशीट तक. Oxford University Press.

[4] 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.)

[5] Bill Jelen: "From 1979 – VisiCalc and LOOKUP"!, by MrExcel East, 31 March 2012

[6] Cormen, Thomas H. (2009). एल्गोरिदम का परिचय (3rd ed.). Cambridge, Mass.: MIT Press. pp. 253–255. ISBN 9780262033848. Retrieved 26 November 2015.

[apress11-7] 7.0 ^7.1 ^7.2 ^7.3 Jungck P.; Dencan R.; Mulcahy D. (2011). प्रदर्शन के लिए विकास। में: पैकेटसी प्रोग्रामिंग. Apress. doi:10.1007/978-1-4302-4159-1_26. ISBN 978-1-4302-4159-1.

[sharif14-8] Cite error: Invalid <ref> tag; no text was provided for refs named sharif14

[9] Randall Hyde (1 March 2010). असेंबली लैंग्वेज की कला, दूसरा संस्करण (PDF). No Starch Press. ISBN 978-1593272074 – via University of Campinas Institute of Computing.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Anonymous

Search

लुकअप टेबल

Namespaces

More

Page actions

Contents

इतिहास

सीमाएं

उदाहरण

तुच्छ हैश फ़ंक्शन

बाइट्स की एक श्रृंखला में बिट्स की गिनती

इमेज प्रोसेसिंग में लुकअप टेबल

संगणक ज्या

लुकअप टेबल के अन्य उपयोग

कैश

हार्डवेयर LUTs

डेटा अधिग्रहण और नियंत्रण प्रणाली

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

लुकअप टेबल

इतिहास

सीमाएं

उदाहरण

तुच्छ हैश फ़ंक्शन

बाइट्स की एक श्रृंखला में बिट्स की गिनती

इमेज प्रोसेसिंग में लुकअप टेबल

संगणक ज्या

लुकअप टेबल के अन्य उपयोग

कैश

हार्डवेयर LUTs

डेटा अधिग्रहण और नियंत्रण प्रणाली

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories