सेंटीनल वैल्यू: Difference between revisions

From Vigyanwiki
No edit summary
 
(One intermediate revision by the same user not shown)
Line 15: Line 15:
  }}</ref> [[कलन विधि]] के संदर्भ में विशेष [[मूल्य (कंप्यूटर विज्ञान)]] है जो समाप्ति की स्थिति के रूप में सामान्यतः नियंत्रण प्रवाह या पुनरावर्ती एल्गोरिदम में अपनी उपस्थिति का उपयोग करता है।
  }}</ref> [[कलन विधि]] के संदर्भ में विशेष [[मूल्य (कंप्यूटर विज्ञान)]] है जो समाप्ति की स्थिति के रूप में सामान्यतः नियंत्रण प्रवाह या पुनरावर्ती एल्गोरिदम में अपनी उपस्थिति का उपयोग करता है।


प्रहरी मान [[इन-बैंड]] डेटा का रूप है जो डेटा के अंत का पता लगाना संभव बनाता है जब कोई [[आउट-ऑफ-बैंड डेटा]] (जैसे स्पष्ट आकार संकेत) प्रदान नहीं किया जाता है। मूल्य को इस तरह से चुना जाना चाहिए कि यह सभी नियमबद्ध डेटा मूल्यों से अलग होने की गारंटी है अन्यथा, ऐसे मूल्यों की उपस्थिति समय से पहले डेटा के अंत(सेमीप्रिडिकेट समस्या) का संकेत देगी। प्रहरी मान को कभी-कभी "काहिरा में हाथी" के रूप में जाना जाता है, मजाक के कारण जहां इसका उपयोग भौतिक प्रहरी के रूप में किया जाता है। सुरक्षित भाषाओं में, अधिकांश प्रहरी मूल्यों को [[विकल्प प्रकार|विकल्प प्रकारों]] से बदला जा सकता है, जो असाधारण स्थितियों की स्पष्ट हैंडलिंग को प्रयुक्त करते हैं।
सेंटीनल वैल्यू [[इन-बैंड]] डेटा का रूप है जो डेटा के अंत का पता लगाना संभव बनाता है जब कोई [[आउट-ऑफ-बैंड डेटा]] (जैसे स्पष्ट आकार संकेत) प्रदान नहीं किया जाता है। मूल्य को इस तरह से चुना जाना चाहिए कि यह सभी नियमबद्ध डेटा मूल्यों से अलग होने की गारंटी है अन्यथा, ऐसे मूल्यों की उपस्थिति समय से पहले डेटा के अंत(सेमीप्रिडिकेट समस्या) का संकेत देगी। सेंटीनल मान (वैल्यू) को कभी-कभी "काहिरा में हाथी" के रूप में जाना जाता है, मजाक के कारण जहां इसका उपयोग भौतिक सेंटीनल के रूप में किया जाता है। सुरक्षित भाषाओं में, अधिकांश सेंटीनल वैल्यू को [[विकल्प प्रकार|विकल्प प्रकारों]] से बदला जा सकता है, जो असाधारण स्थितियों की स्पष्ट हैंडलिंग को प्रयुक्त करते हैं।


== उदाहरण ==
== उदाहरण ==
सामान्य प्रहरी मूल्यों और उनके उपयोगों के कुछ उदाहरण:
सामान्य सेंटीनल वैल्यू और उनके उपयोगों के कुछ उदाहरण:
* [[अशक्त-समाप्त स्ट्रिंग]] के अंत को इंगित करने के लिए अशक्त वर्ण।
* [[अशक्त-समाप्त स्ट्रिंग]] के अंत को इंगित करने के लिए अशक्त वर्ण।
* लिंक की गई सूची या ट्री (डेटा संरचना) के अंत का संकेत देने के लिए अशक्त सूचक(नल पॉइंटर)।
* लिंक की गई सूची या ट्री (डेटा संरचना) के अंत का संकेत देने के लिए अशक्त सूचक(नल पॉइंटर)।
Line 27: Line 27:
थोड़ी अलग परिस्थितियों में उपयोग की जाने वाली संबंधित प्रथा, कुछ प्रोसेसिंग लूप में समाप्ति के लिए तथा स्पष्ट परीक्षण की आवश्यकता से बचने के लिए, डेटा के अंत में कुछ विशिष्ट मूल्य रखना है, क्योंकि मान पहले से ही अन्य कारणों से उपस्थित होंकर परीक्षणों द्वारा समाप्ति को ट्रिगर करेगा। उपरोक्त उपयोगों के विपरीत, यह नहीं है कि डेटा को स्वाभाविक रूप से कैसे संग्रहीत या संसाधित किया जाता है, किंतु इसके अतिरिक्त अनुकूलन है, जो सीधे एल्गोरिथम की तुलना में समाप्ति की जांच करता है। यह सामान्यतः खोज में प्रयोग किया जाता है।<ref>{{cite book |last1=Mehlhorn |first1=Kurt |author1-link=Kurt Mehlhorn |last2=Sanders |first2=Peter |author2-link=Peter Sanders (computer scientist) |year=2008 |title=Algorithms and Data Structures: The Basic Toolbox 3 Representing Sequences by Arrays and Linked Lists |publisher=Springer |page=63 |url=http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/SortedSequences.pdf |isbn=978-3-540-77977-3}}</ref><ref>{{cite book |last=McConnell |first=Steve |year=2004 |title=Code Complete |edition=2nd |location=Redmond |publisher=Microsoft Press |isbn=0-7356-1967-0 |page=621 |url=https://archive.org/details/codecomplete0000mcco/page/621 |url-access=registration}}</ref>
थोड़ी अलग परिस्थितियों में उपयोग की जाने वाली संबंधित प्रथा, कुछ प्रोसेसिंग लूप में समाप्ति के लिए तथा स्पष्ट परीक्षण की आवश्यकता से बचने के लिए, डेटा के अंत में कुछ विशिष्ट मूल्य रखना है, क्योंकि मान पहले से ही अन्य कारणों से उपस्थित होंकर परीक्षणों द्वारा समाप्ति को ट्रिगर करेगा। उपरोक्त उपयोगों के विपरीत, यह नहीं है कि डेटा को स्वाभाविक रूप से कैसे संग्रहीत या संसाधित किया जाता है, किंतु इसके अतिरिक्त अनुकूलन है, जो सीधे एल्गोरिथम की तुलना में समाप्ति की जांच करता है। यह सामान्यतः खोज में प्रयोग किया जाता है।<ref>{{cite book |last1=Mehlhorn |first1=Kurt |author1-link=Kurt Mehlhorn |last2=Sanders |first2=Peter |author2-link=Peter Sanders (computer scientist) |year=2008 |title=Algorithms and Data Structures: The Basic Toolbox 3 Representing Sequences by Arrays and Linked Lists |publisher=Springer |page=63 |url=http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/SortedSequences.pdf |isbn=978-3-540-77977-3}}</ref><ref>{{cite book |last=McConnell |first=Steve |year=2004 |title=Code Complete |edition=2nd |location=Redmond |publisher=Microsoft Press |isbn=0-7356-1967-0 |page=621 |url=https://archive.org/details/codecomplete0000mcco/page/621 |url-access=registration}}</ref>


उदाहरण के लिए, जब किसी अवर्गीकृत सूची (अमूर्त डेटा प्रकार) में किसी विशेष मान की खोज करते समय, प्रत्येक तत्व की तुलना इस मान से की जाएगी, तथा समानता पाए जाने [[आंतरिक फंदे]] समाप्त हो जायेंगे ; चूँकि, इस स्थिति से निपटने के लिए कि मूल्य अनुपस्थित होना चाहिए, अतः प्रत्येक चरण के बाद खोज को असफल रूप से पूरा करने के लिए भी परीक्षण करना चाहिए। सूची के अंत में खोजे गए मान को जोड़कर असफल खोज अब संभव नहीं है, और आंतरिक लूप में किसी स्पष्ट समाप्ति परीक्षण की आवश्यकता नहीं है; बाद में, किसी को अभी भी यह तय करना होगा कि क्या सही मैच पाया गया था, किंतु इस परीक्षण को प्रत्येक पुनरावृत्ति के अतिरिक्त केवल एक बार करने की आवश्यकता है।<ref>{{cite book |last=Knuth |first=Donald |authorlink=Donald Knuth |year=1973 |title=The Art of Computer Programming, Volume 3: Sorting and searching |publisher=[[Addison-Wesley]] |isbn=0-201-03803-X |page=395}}</ref> नुथ डेटा के अंत में रखे गए मान को प्रहरी के अतिरिक्त डमी मान कहता है।
उदाहरण के लिए, जब किसी अवर्गीकृत सूची (अमूर्त डेटा प्रकार) में किसी विशेष मान की खोज करते समय, प्रत्येक तत्व की तुलना इस मान से की जाएगी, तथा समानता पाए जाने [[आंतरिक फंदे]] समाप्त हो जायेंगे ; चूँकि, इस स्थिति से निपटने के लिए कि मूल्य अनुपस्थित होना चाहिए, अतः प्रत्येक चरण के बाद खोज को असफल रूप से पूरा करने के लिए भी परीक्षण करना चाहिए। सूची के अंत में खोजे गए मान को जोड़कर असफल खोज अब संभव नहीं है, और आंतरिक लूप में किसी स्पष्ट समाप्ति परीक्षण की आवश्यकता नहीं है; बाद में, किसी को अभी भी यह तय करना होगा कि क्या सही मैच पाया गया था, किंतु इस परीक्षण को प्रत्येक पुनरावृत्ति के अतिरिक्त केवल एक बार करने की आवश्यकता है।<ref>{{cite book |last=Knuth |first=Donald |authorlink=Donald Knuth |year=1973 |title=The Art of Computer Programming, Volume 3: Sorting and searching |publisher=[[Addison-Wesley]] |isbn=0-201-03803-X |page=395}}</ref> नुथ डेटा के अंत में रखे गए मान को सेंटीनल के अतिरिक्त डमी मान कहता है।


=== उदाहरण ===
=== उदाहरण ===
Line 41: Line 41:
     return -1; // not found
     return -1; // not found
}
}
</syntaxhighlight>चूँकि, यह लूप के प्रत्येक पुनरावृत्ति पर दो परीक्षण करता है:पहला यह कि क्या मान मिल गया है और दूसरा यह कि क्या सरणी का अंत हो गया है। यह बाद वाला परीक्षण है जिसे प्रहरी मान का उपयोग करके टाला जाता है। यह मानते हुए कि सरणी को तत्व द्वारा बढ़ाया जा सकता है (स्मृति आवंटन या सफाई के बिना; यह लिंक की गई सूची के लिए अधिक यथार्थवादी है, जैसा कि नीचे दिया गया है), इसे फिर से लिखा जा सकता है:<syntaxhighlight>
</syntaxhighlight>चूँकि, यह लूप के प्रत्येक पुनरावृत्ति पर दो परीक्षण करता है:पहला यह कि क्या मान मिल गया है और दूसरा यह कि क्या सरणी का अंत हो गया है। यह बाद वाला परीक्षण है जिसे सेंटीनल मान का उपयोग करके टाला जाता है। यह मानते हुए कि सरणी को तत्व द्वारा बढ़ाया जा सकता है (स्मृति आवंटन या सफाई के बिना; यह लिंक की गई सूची के लिए अधिक यथार्थवादी है, जैसा कि नीचे दिया गया है), इसे फिर से लिखा जा सकता है:<syntaxhighlight>
int find(int arr[], size_t len, int val)
int find(int arr[], size_t len, int val)
{
{
Line 55: Line 55:
             return -1; // not found
             return -1; // not found
}
}
</syntaxhighlight><code>i &lt; len</code> के लिए परीक्षण अभी भी उपस्थित है, किंतु इसे लूप के बाहर ले जाया गया है, जिसमें अब केवल परीक्षण (मान के लिए) है, और संतरी(प्रहरी) मूल्य के कारण समाप्त होने की गारंटी है। प्रहरी मान हिट होने पर समाप्ति पर ही जाँच होती है, जो प्रत्येक पुनरावृत्ति के लिए परीक्षण की जगह लेती है।
</syntaxhighlight><code>i &lt; len</code> के लिए परीक्षण अभी भी उपस्थित है, किंतु इसे लूप के बाहर ले जाया गया है, जिसमें अब केवल परीक्षण (मान के लिए) है, और संतरी(सेंटीनल) मूल्य के कारण समाप्त होने की गारंटी है। सेंटीनल मान हिट होने पर समाप्ति पर ही जाँच होती है, जो प्रत्येक पुनरावृत्ति के लिए परीक्षण की जगह लेती है।




Line 82: Line 82:
== यह भी देखें ==
== यह भी देखें ==
* कनारी मूल्य
* कनारी मूल्य
* [[प्रहरी नोड]]
* [[प्रहरी नोड|सेंटीनल नोड]]
* अर्धसूत्रीविभाजन समस्या
* अर्धसूत्रीविभाजन समस्या
* काहिरा में हाथी
* काहिरा में हाथी

Latest revision as of 16:39, 8 September 2023

कंप्यूटर प्रोग्रामिंग में, सेंटीनल वैल्यू (जिसे फ्लैग वैल्यू, ट्रिप वैल्यू, रॉग वैल्यू, सिग्नल वैल्यू या डमी डेटा भी कहा जाता है)[1] कलन विधि के संदर्भ में विशेष मूल्य (कंप्यूटर विज्ञान) है जो समाप्ति की स्थिति के रूप में सामान्यतः नियंत्रण प्रवाह या पुनरावर्ती एल्गोरिदम में अपनी उपस्थिति का उपयोग करता है।

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

उदाहरण

सामान्य सेंटीनल वैल्यू और उनके उपयोगों के कुछ उदाहरण:

  • अशक्त-समाप्त स्ट्रिंग के अंत को इंगित करने के लिए अशक्त वर्ण।
  • लिंक की गई सूची या ट्री (डेटा संरचना) के अंत का संकेत देने के लिए अशक्त सूचक(नल पॉइंटर)।
  • समान अंतराल वाले डेटा मानों की धारा में सबसे महत्वपूर्ण बिट, उदाहरण के लिए, 8-बिट बाइट्स में संग्रहीत 7-बिट एएससीआईआई(ASCII) वर्णों की धारा में एक सेट 8-बिट विशेष संपत्ति(जैसे उलटा वीडियो, बोल्ड अक्षरों या इटैलिक) या धारा का अंत का संकेत देता है।
  • गैर-ऋणात्मक पूर्णांकों के अनुक्रम के अंत को इंगित करने के लिए ऋणात्मक पूर्णांक।

वेरिएंट

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

उदाहरण के लिए, जब किसी अवर्गीकृत सूची (अमूर्त डेटा प्रकार) में किसी विशेष मान की खोज करते समय, प्रत्येक तत्व की तुलना इस मान से की जाएगी, तथा समानता पाए जाने आंतरिक फंदे समाप्त हो जायेंगे ; चूँकि, इस स्थिति से निपटने के लिए कि मूल्य अनुपस्थित होना चाहिए, अतः प्रत्येक चरण के बाद खोज को असफल रूप से पूरा करने के लिए भी परीक्षण करना चाहिए। सूची के अंत में खोजे गए मान को जोड़कर असफल खोज अब संभव नहीं है, और आंतरिक लूप में किसी स्पष्ट समाप्ति परीक्षण की आवश्यकता नहीं है; बाद में, किसी को अभी भी यह तय करना होगा कि क्या सही मैच पाया गया था, किंतु इस परीक्षण को प्रत्येक पुनरावृत्ति के अतिरिक्त केवल एक बार करने की आवश्यकता है।[4] नुथ डेटा के अंत में रखे गए मान को सेंटीनल के अतिरिक्त डमी मान कहता है।

उदाहरण

ऐरे(सरणी)

उदाहरण के लिए, यदि सी में किसी सरणी में मान की खोज की जाती है, तो सीधा कार्यान्वयन इस प्रकार है; कि बिना किसी परिणाम के वापस आने की अर्धविराम समस्या को हल करने के लिए ऋणात्मक संख्या (अमान्य सूचकांक) के उपयोग पर ध्यान दें:

int find(int arr[], size_t len, int val)
{
    for (int i = 0; i < len; i++)
        if (arr[i] == val)
            return i;
    return -1; // not found
}

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

int find(int arr[], size_t len, int val)
{
    int i;

    arr[len] = val; // add sentinel value
    for (i = 0;; i++)
        if (arr[i] == val)
            break;
    if (i < len)
            return i;
    else
            return -1; // not found
}

i < len के लिए परीक्षण अभी भी उपस्थित है, किंतु इसे लूप के बाहर ले जाया गया है, जिसमें अब केवल परीक्षण (मान के लिए) है, और संतरी(सेंटीनल) मूल्य के कारण समाप्त होने की गारंटी है। सेंटीनल मान हिट होने पर समाप्ति पर ही जाँच होती है, जो प्रत्येक पुनरावृत्ति के लिए परीक्षण की जगह लेती है।


सरणी के अंतिम तत्व को सेंटीनेल द्वारा अस्थायी रूप से प्रतिस्थापित करना और इसे संभालना भी संभव है, खासकर यदि यह पहुंच गया हो:

int find(int arr[], size_t len, int val)
{
    int last;

    if (len == 0)
        return -1;
    last = arr[len - 1];
    arr[len - 1] = val; // add sentinel value

    int i;
    for (i = 0;; i++)
        if (arr[i] == val)
            break;
    arr[len - 1] = last;
    if (arr[i] == val)
            return i;
    else
            return -1; // not found
}

यह भी देखें

संदर्भ

  1. Knuth, Donald (1973). The Art of Computer Programming, Volume 1: Fundamental Algorithms (Second ed.). Addison-Wesley. pp. 213–214, 631. ISBN 0-201-03809-9.
  2. Mehlhorn, Kurt; Sanders, Peter (2008). Algorithms and Data Structures: The Basic Toolbox 3 Representing Sequences by Arrays and Linked Lists (PDF). Springer. p. 63. ISBN 978-3-540-77977-3.
  3. McConnell, Steve (2004). Code Complete (2nd ed.). Redmond: Microsoft Press. p. 621. ISBN 0-7356-1967-0.
  4. Knuth, Donald (1973). The Art of Computer Programming, Volume 3: Sorting and searching. Addison-Wesley. p. 395. ISBN 0-201-03803-X.