समष्टि-समय का व्यापार: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(11 intermediate revisions by 6 users not shown)
Line 1: Line 1:
"स्थान-समय का व्यापार " या "समय-स्मृति का व्यापार "या" [[कंप्यूटर विज्ञान]] में कलनविधीय स्थान-समय संगति" एक विषय है, जहाँ एक [[ कलन विधि |कलन विधि]] या प्रोग्राम समय को कम करते हुए स्थान के विस्तार के बदले में बढ़े हुए स्थान का उपयोग करता है। यहाँ, स्थान का अर्थ एक दिए गए कार्य को करने में उपयोग होने वाले डेटा संग्रहण (RAM, HDD) [[डायनेमिक रैंडम-एक्सेस मेमोरी]], [[हार्ड डिस्क ड्राइव]],को संकेत करता है, और समय का अर्थ दिए गए कार्य को करने में उपयोग होने वाला समय होता है।
"स्थान-समय का व्यापार या [[कंप्यूटर विज्ञान]] में कलनविधीय स्थान-समय संगति" एक विषय है, जहाँ एक विधिकलन या प्रोग्राम समय को कम करते हुए स्थान के विस्तार के बदले में बढ़े हुए स्थान का उपयोग करता है। यहाँ, स्थान का अर्थ एक दिए गए कार्य को करने में उपयोग होने वाले डेटा संग्रहण (रैम, एचडीडी) [[डायनेमिक रैंडम-एक्सेस मेमोरी]], [[हार्ड डिस्क ड्राइव]],को संकेत करता है, और समय का अर्थ दिए गए कार्य को करने में उपयोग होने वाला समय होता है।


[[ CPU | CPU]]एक दिए गए स्थान-समय के व्यापार  की उपयोगिता पर संबंधित स्थिर और परिवर्तनशील लागतों जैसे [[ CPU |सीपीयू]] की गति, संग्रहण स्थान की लागत का प्रभाव पड़ता है, और इसे घटती लाभ की प्राप्ति का सामर्थ्य होता है
एक दिए गए स्थान-समय के व्यापार  की उपयोगिता पर संबंधित स्थिर और परिवर्तनशील लागतों जैसे [[ CPU |सीपीयू]] की गति, संग्रहण स्थान की लागत का प्रभाव पड़ता है, और इसे घटते लाभ के प्राप्ति का सामर्थ्य होता है


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


1980 में [[मार्टिन हेलमैन]] ने पहली बार [[क्रिप्ट विश्लेषण]] के लिए  समय-स्मृति के व्यापार का उपयोग करने का प्रस्ताव दिया।<ref>{{cite journal | title=एक क्रिप्ट एनालिटिक टाइम-मेमोरी ट्रेडऑफ़| author=Hellman, Martin | journal=IEEE Transactions on Information Theory |date=July 1980 | volume=26 | issue=4 | pages=401–406 | doi=10.1109/tit.1980.1056220| citeseerx=10.1.1.120.2463 }}</ref>
1980 में [[मार्टिन हेलमैन]] ने पहली बार [[क्रिप्ट विश्लेषण]] के लिए  समय-मेमोरी के व्यापार का उपयोग करने का प्रस्ताव दिया। <ref>{{cite journal | title=एक क्रिप्ट एनालिटिक टाइम-मेमोरी ट्रेडऑफ़| author=Hellman, Martin | journal=IEEE Transactions on Information Theory |date=July 1980 | volume=26 | issue=4 | pages=401–406 | doi=10.1109/tit.1980.1056220| citeseerx=10.1.1.120.2463 }}</ref>




== ट्रेडऑफ़ के प्रकार ==
== व्यापार के प्रकार ==


=== [[ तालिका देखो ]] बनाम पुनर्गणना ===
=== लुकअप[[ तालिका देखो | तालिका]] [[फुल टेबल स्कैन|बनाम]] पुनर्गणना ===
एक सामान्य स्थिति एक एल्गोरिथ्म है जिसमें एक लुकअप टेबल शामिल है: एक कार्यान्वयन में संपूर्ण तालिका शामिल हो सकती है, जो कंप्यूटिंग समय को कम करती है, लेकिन आवश्यक मेमोरी की मात्रा को बढ़ाती है, या यह आवश्यकतानुसार तालिका प्रविष्टियों की गणना कर सकती है, कंप्यूटिंग समय में वृद्धि कर सकती है, लेकिन मेमोरी आवश्यकताओं को कम कर सकती है।
एक सामान्य स्थिति एक विधिकलन है, जिसमें एक लुकअप तालिका सम्मिलित है। एक कार्यान्वयन में संपूर्ण तालिका सम्मिलित हो सकती है, जो अभिकलन समय को कम करती है, परंतु आवश्यक मेमोरी की मात्रा को बढ़ाती है, या यह आवश्यकतानुसार तालिका प्रविष्टियों की गणना कर सकती है, जो अभिकलन  समय में वृद्धि कर सकती है, परंतु मेमोरी आवश्यकताओं को कम कर सकती है।  


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


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


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


=== छोटा कोड बनाम [[लूप अनोलिंग]] ===
=== सूक्ष्म कूट बनाम [[लूप अनोलिंग|लूप विस्तारण]] ===
लूप अनोलिंग लागू करते समय उच्च प्रोग्राम गति के लिए बड़े कोड आकार का व्यापार  किया जा सकता है। यह तकनीक लूप के प्रत्येक पुनरावृत्ति के लिए कोड को लंबा बनाती है, लेकिन प्रत्येक पुनरावृत्ति के अंत में लूप की शुरुआत में वापस कूदने के लिए आवश्यक संगणना समय को बचाती है।
[[लूप अनोलिंग|लूप विस्तारण]] लागू करते समय उच्च प्रोग्राम गति के लिए बड़े कूट आकार का व्यापार  किया जा सकता है। यह तकनीक हर लूप के प्रत्येक घुमाव के लिए कोड को लंबा बनाती है, परंतु प्रत्येक घुमाव के अंत में लूप का प्रारंभ वापस जाने के लिए आवश्यक गणना समय की बचत करती है।


== अन्य उदाहरण ==
== अन्य उदाहरण ==
स्पेस-टाइम ट्रेडऑफ़ का उपयोग करने वाले एल्गोरिदम में शामिल हैं:
स्थान-समय व्यापार का उपयोग करने वाले कलन विधियों में सम्मिलित हैं:
* [[असतत लघुगणक]] की गणना के लिए [[बेबी-स्टेप जाइंट-स्टेप]] एल्गोरिद्म
* [[असतत लघुगणक]] की गणना के लिए सूक्ष्म चरण दीर्घ चरण  विधिकलन।
* क्रिप्टोग्राफी में रेनबो टेबल, जहां विरोधी जानवर-बल के हमले के लिए आवश्यक घातीय समय से बेहतर करने की कोशिश कर रहा है। [[क्रिप्टोग्राफ़िक हैश फ़ंक्शन]] के हैश स्थान में रेनबो टेबल आंशिक रूप से पूर्व-गणना किए गए मानों का उपयोग सप्ताहों के बजाय मिनटों में पासवर्ड क्रैक करने के लिए करते हैं। [[इंद्रधनुष तालिका]] के आकार को कम करने से हैश स्थान पर पुनरावृति करने में लगने वाला समय बढ़ जाता है।
* क्रिप्टोग्राफी में रेनबो टेबल, जहां प्रतिद्वंद्वी ब्रूट-फोर्स हमले के लिए लघुत्तम समय से बेहतर परिणाम प्राप्त करने का प्रयास कर रहा हो। रेनबो टेबल क्रिप्टोग्राफिक हैश फलन के हैश स्थान में आंशिक पूर्वगणित मानों का उपयोग करते हैं जिससे पासवर्ड को सप्ताहों केअतिरिक्त कुछ मिनटों में क्रैक किया जा सके। [[इंद्रधनुष तालिका|रेनबो तालिका]] के आकार को कम करने से हैश स्थान पर पुनरावृति करने में लगने वाला समय बढ़ जाता है।
* [[बीच-बीच में हमला]] केवल [[कुंजी (क्रिप्टोग्राफी)]] खोजने के लिए स्पेस-टाइम ट्रेडऑफ़ का उपयोग करता है <math>2^{n+1}</math> एन्क्रिप्शन (और <math>O(2^n)</math> अंतरिक्ष) बनाम अपेक्षित <math>2^{2n}</math> एन्क्रिप्शन (लेकिन केवल <math>O(1)</math> अंतरिक्ष) भोले हमले की।
* मीट-इन-द-मिडल अटैक स्थान-समय व्यापार का उपयोग करता है जिससे केवल संग्रहण की क्षमता के आधार पर क्रिप्टोग्राफिक कुंजी को खोजें। जिससे मात्र <math>2^{n+1}</math> और <math>O(2^n)</math> अंतरिक्ष एन्क्रिप्शन बनाम अपेक्षित <math>2^{2n}</math> एन्क्रिप्शन परंतु <math>O(1)</math> अंतरिक्ष) नाईव अटैक ।
* [[गतिशील प्रोग्रामिंग]], जहाँ अधिक मेमोरी का उपयोग करके किसी समस्या की समय जटिलता को काफी कम किया जा सकता है।
* [[गतिशील प्रोग्रामिंग]], जहाँ अधिक मेमोरी का उपयोग करके किसी समस्या की समय जटिलता को काफी कम किया जा सकता है।


== यह भी देखें ==
== यह भी देखें ==


* {{annotated link|Algorithmic efficiency}}
* एल्गोरिथम दक्षता
* {{annotated link|Blum's speedup theorem}}
* ब्लम का स्पीडअप प्रमेय
* {{annotated link|Computational complexity}}
* अभिकलनात्मक जटिलता
* {{annotated link|Computational resource}}
* कम्प्यूटेशनल संसाधन
* {{annotated link|Savitch's theorem}}
* सैविच की प्रमेय


==संदर्भ==
==संदर्भ==
Line 49: Line 49:
* [http://www.cs.sjsu.edu/faculty/stamp/RUA/TMTO.pdf Once Upon a Time-Memory Tradeoff.]
* [http://www.cs.sjsu.edu/faculty/stamp/RUA/TMTO.pdf Once Upon a Time-Memory Tradeoff.]


{{DEFAULTSORT:Space-time tradeoff}}[[Category: सॉफ्टवेयर अनुकूलन]]
{{DEFAULTSORT:Space-time tradeoff}}


 
[[Category:Created On 11/05/2023|Space-time tradeoff]]
 
[[Category:Machine Translated Page|Space-time tradeoff]]
[[Category: Machine Translated Page]]
[[Category:Pages with script errors|Space-time tradeoff]]
[[Category:Created On 11/05/2023]]
[[Category:Templates Vigyan Ready]]
[[Category:सॉफ्टवेयर अनुकूलन|Space-time tradeoff]]

Latest revision as of 13:15, 3 November 2023

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

एक दिए गए स्थान-समय के व्यापार की उपयोगिता पर संबंधित स्थिर और परिवर्तनशील लागतों जैसे सीपीयू की गति, संग्रहण स्थान की लागत का प्रभाव पड़ता है, और इसे घटते लाभ के प्राप्ति का सामर्थ्य होता है

इतिहास

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

1980 में मार्टिन हेलमैन ने पहली बार क्रिप्ट विश्लेषण के लिए समय-मेमोरी के व्यापार का उपयोग करने का प्रस्ताव दिया। [1]


व्यापार के प्रकार

लुकअप तालिका बनाम पुनर्गणना

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

डाटाबेस सूचकांक बनाम तालिका

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

संपीड़ित बनाम असम्पीडित डेटा

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

पुन: प्रतिपादन बनाम संग्रहीत चित्र

एक सदिश छवि के एसवीजी स्रोत को संग्रहित करना और प्रत्येक बार पृष्ठ का अनुरोध होने पर इसे बिटम छवि के रूप में प्रदर्शित करना समय के साथ स्थान का व्यापार करना होगा। अधिक समय का उपयोग होगा, परंतु कम स्थान की आवश्यकता होगी। अधिक समय का उपयोग, परंतु कम जगह। पृष्ठ में परिवर्तन होने पर छवि को प्रतिपादन करना और प्रतिपादन की गई छवियों को संग्रहित करना समय और स्थान के बदले व्यापार स्थान का उपयोग होगा, परंतु समय का कम उपयोग होगा। इस तकनीक को सामान्य रूप से अभिकलन के रूप में जाना जाता है।

सूक्ष्म कूट बनाम लूप विस्तारण

लूप विस्तारण लागू करते समय उच्च प्रोग्राम गति के लिए बड़े कूट आकार का व्यापार किया जा सकता है। यह तकनीक हर लूप के प्रत्येक घुमाव के लिए कोड को लंबा बनाती है, परंतु प्रत्येक घुमाव के अंत में लूप का प्रारंभ वापस जाने के लिए आवश्यक गणना समय की बचत करती है।

अन्य उदाहरण

स्थान-समय व्यापार का उपयोग करने वाले कलन विधियों में सम्मिलित हैं:

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

यह भी देखें

  • एल्गोरिथम दक्षता
  • ब्लम का स्पीडअप प्रमेय
  • अभिकलनात्मक जटिलता
  • कम्प्यूटेशनल संसाधन
  • सैविच की प्रमेय

संदर्भ

  1. Hellman, Martin (July 1980). "एक क्रिप्ट एनालिटिक टाइम-मेमोरी ट्रेडऑफ़". IEEE Transactions on Information Theory. 26 (4): 401–406. CiteSeerX 10.1.1.120.2463. doi:10.1109/tit.1980.1056220.


बाहरी संबंध