समष्टि-समय का व्यापार: Difference between revisions
No edit summary |
|||
| Line 1: | Line 1: | ||
"स्थान-समय का व्यापार " या "समय- | "स्थान-समय का व्यापार " या "समय-मेमोरी का व्यापार "या" [[कंप्यूटर विज्ञान]] में कलनविधीय स्थान-समय संगति" एक विषय है, जहाँ एक [[ कलन विधि |कलन विधि]] या प्रोग्राम समय को कम करते हुए स्थान के विस्तार के बदले में बढ़े हुए स्थान का उपयोग करता है। यहाँ, स्थान का अर्थ एक दिए गए कार्य को करने में उपयोग होने वाले डेटा संग्रहण (RAM, HDD) [[डायनेमिक रैंडम-एक्सेस मेमोरी]], [[हार्ड डिस्क ड्राइव]],को संकेत करता है, और समय का अर्थ दिए गए कार्य को करने में उपयोग होने वाला समय होता है। | ||
[[ CPU | CPU]]एक दिए गए स्थान-समय के व्यापार की उपयोगिता पर संबंधित स्थिर और परिवर्तनशील लागतों जैसे [[ CPU |सीपीयू]] की गति, संग्रहण स्थान की लागत का प्रभाव पड़ता है, और इसे घटती लाभ की प्राप्ति का सामर्थ्य होता है | [[ CPU | CPU]]एक दिए गए स्थान-समय के व्यापार की उपयोगिता पर संबंधित स्थिर और परिवर्तनशील लागतों जैसे [[ CPU |सीपीयू]] की गति, संग्रहण स्थान की लागत का प्रभाव पड़ता है, और इसे घटती लाभ की प्राप्ति का सामर्थ्य होता है | ||
== इतिहास == | == इतिहास == | ||
पशुओं के व्यवहार के पूर्व चरणों में समय- | पशुओं के व्यवहार के पूर्व चरणों में समय-मेमोरी के व्यापार का जीववैज्ञानिक उपयोग देखा जा सकता है। डीएनए में संग्रहित ज्ञान का उपयोग करना या प्रायोगिकता के प्रतिक्रियाओं को "सहज ज्ञान" के रूप में कोड करके, समय-महत्वपूर्ण परिस्थितियों में गणना की आवश्यकता से बचाया जा सकता है। कंप्यूटरों के संदर्भ में अधिक विशिष्ट रूप से कहें तो, लुकअप तालिकाएं सबसे पहले से ही ऑपरेटिंग सिस्टम के प्रारंभिक संस्करणों से लागू की जाती रही हैं। | ||
1980 में [[मार्टिन हेलमैन]] ने पहली बार [[क्रिप्ट विश्लेषण]] के लिए समय- | 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> | ||
== | == व्यापार के प्रकार == | ||
=== [[ तालिका देखो ]] | === लुकअप[[ तालिका देखो | तालिका]] के विरुद्ध पुनर्गणना === | ||
एक सामान्य स्थिति एक | एक सामान्य स्थिति एक कलन विधि है, जिसमें एक लुकअप तालिका सम्मिलित है। एक कार्यान्वयन में संपूर्ण तालिका सम्मिलित हो सकती है, जो अभिकलन समय को कम करती है, परंतु आवश्यक मेमोरी की मात्रा को बढ़ाती है, या यह आवश्यकतानुसार तालिका प्रविष्टियों की गणना कर सकती है, जो अभिकलन समय में वृद्धि कर सकती है, परंतु मेमोरी आवश्यकताओं को कम कर सकती है। | ||
=== [[डाटाबेस इंडेक्स]] [[फुल टेबल स्कैन]] === | === [[डाटाबेस इंडेक्स]] [[फुल टेबल स्कैन]] === | ||
| Line 18: | Line 18: | ||
===संपीड़ित बनाम असम्पीडित डेटा=== | ===संपीड़ित बनाम असम्पीडित डेटा=== | ||
डेटा संग्रहण की समस्या के लिए स्पेस-टाइम | डेटा संग्रहण की समस्या के लिए स्पेस-टाइम व्यापार लागू किया जा सकता है। यदि डेटा असम्पीडित संग्रहीत किया जाता है, तो यह अधिक स्थान लेता है, परंतु डेटा को संपीड़ित करने की तुलना में एक्सेस में कम समय लगता है (चूंकि डेटा को संपीड़ित करने से इसमें लगने वाले स्थान की मात्रा कम हो जाती है, परंतु डेटा संपीड़न को चलाने में समय लगता है)। समस्या के विशेष उदाहरण के आधार पर, कोई भी तरीका व्यावहारिक है। ऐसे दुर्लभ उदाहरण भी हैं जहां संपीड़ित डेटा के साथ सीधे काम करना संभव है, जैसे संपीड़ित [[बिटमैप इंडेक्स]] के मामले में, जहां संपीड़न के बिना संपीड़न के साथ काम करना तेज़ होता है। | ||
===री-रेंडरिंग बनाम संगृहीत चित्र === | ===री-रेंडरिंग बनाम संगृहीत चित्र === | ||
किसी वेक्टर ग्राफ़िक्स के केवल [[स्केलेबल [[वेक्टर ग्राफिक्स]]]] स्रोत को संग्रहीत करना और हर बार पृष्ठ के लिए अनुरोध किए जाने पर इसे [[बिटमैप]] के रूप में प्रस्तुत करना स्पेस के लिए ट्रेडिंग समय होगा; अधिक समय का उपयोग, | किसी वेक्टर ग्राफ़िक्स के केवल [[स्केलेबल [[वेक्टर ग्राफिक्स]]]] स्रोत को संग्रहीत करना और हर बार पृष्ठ के लिए अनुरोध किए जाने पर इसे [[बिटमैप]] के रूप में प्रस्तुत करना स्पेस के लिए ट्रेडिंग समय होगा; अधिक समय का उपयोग, परंतु कम जगह। जब पृष्ठ बदला जाता है तो छवि को प्रस्तुत करना और प्रदान की गई छवियों को संग्रहीत करना समय के लिए व्यापार स्थान होगा; अधिक जगह का उपयोग, परंतु कम समय। इस तकनीक को आमतौर पर [[कैश (कंप्यूटिंग)|कैश (अभिकलन )]] के रूप में जाना जाता है। | ||
=== छोटा कोड बनाम [[लूप अनोलिंग]] === | === छोटा कोड बनाम [[लूप अनोलिंग]] === | ||
लूप अनोलिंग लागू करते समय उच्च प्रोग्राम गति के लिए बड़े कोड आकार का व्यापार किया जा सकता है। यह तकनीक लूप के प्रत्येक पुनरावृत्ति के लिए कोड को लंबा बनाती है, | लूप अनोलिंग लागू करते समय उच्च प्रोग्राम गति के लिए बड़े कोड आकार का व्यापार किया जा सकता है। यह तकनीक लूप के प्रत्येक पुनरावृत्ति के लिए कोड को लंबा बनाती है, परंतु प्रत्येक पुनरावृत्ति के अंत में लूप की शुरुआत में वापस कूदने के लिए आवश्यक संगणना समय को बचाती है। | ||
== अन्य उदाहरण == | == अन्य उदाहरण == | ||
स्पेस-टाइम | स्पेस-टाइम व्यापार का उपयोग करने वाले एल्गोरिदम में शामिल हैं: | ||
* [[असतत लघुगणक]] की गणना के लिए [[बेबी-स्टेप जाइंट-स्टेप]] एल्गोरिद्म | * [[असतत लघुगणक]] की गणना के लिए [[बेबी-स्टेप जाइंट-स्टेप]] एल्गोरिद्म | ||
* क्रिप्टोग्राफी में रेनबो टेबल, जहां विरोधी जानवर-बल के हमले के लिए आवश्यक घातीय समय से बेहतर करने की कोशिश कर रहा है। [[क्रिप्टोग्राफ़िक हैश फ़ंक्शन]] के हैश स्थान में रेनबो टेबल आंशिक रूप से पूर्व-गणना किए गए मानों का उपयोग सप्ताहों के बजाय मिनटों में पासवर्ड क्रैक करने के लिए करते हैं। [[इंद्रधनुष तालिका]] के आकार को कम करने से हैश स्थान पर पुनरावृति करने में लगने वाला समय बढ़ जाता है। | * क्रिप्टोग्राफी में रेनबो टेबल, जहां विरोधी जानवर-बल के हमले के लिए आवश्यक घातीय समय से बेहतर करने की कोशिश कर रहा है। [[क्रिप्टोग्राफ़िक हैश फ़ंक्शन]] के हैश स्थान में रेनबो टेबल आंशिक रूप से पूर्व-गणना किए गए मानों का उपयोग सप्ताहों के बजाय मिनटों में पासवर्ड क्रैक करने के लिए करते हैं। [[इंद्रधनुष तालिका]] के आकार को कम करने से हैश स्थान पर पुनरावृति करने में लगने वाला समय बढ़ जाता है। | ||
* [[बीच-बीच में हमला]] केवल [[कुंजी (क्रिप्टोग्राफी)]] खोजने के लिए स्पेस-टाइम | * [[बीच-बीच में हमला]] केवल [[कुंजी (क्रिप्टोग्राफी)]] खोजने के लिए स्पेस-टाइम व्यापार का उपयोग करता है <math>2^{n+1}</math> एन्क्रिप्शन (और <math>O(2^n)</math> अंतरिक्ष) बनाम अपेक्षित <math>2^{2n}</math> एन्क्रिप्शन (परंतु केवल <math>O(1)</math> अंतरिक्ष) भोले हमले की। | ||
* [[गतिशील प्रोग्रामिंग]], जहाँ अधिक मेमोरी का उपयोग करके किसी समस्या की समय जटिलता को काफी कम किया जा सकता है। | * [[गतिशील प्रोग्रामिंग]], जहाँ अधिक मेमोरी का उपयोग करके किसी समस्या की समय जटिलता को काफी कम किया जा सकता है। | ||
Revision as of 08:38, 30 May 2023
"स्थान-समय का व्यापार " या "समय-मेमोरी का व्यापार "या" कंप्यूटर विज्ञान में कलनविधीय स्थान-समय संगति" एक विषय है, जहाँ एक कलन विधि या प्रोग्राम समय को कम करते हुए स्थान के विस्तार के बदले में बढ़े हुए स्थान का उपयोग करता है। यहाँ, स्थान का अर्थ एक दिए गए कार्य को करने में उपयोग होने वाले डेटा संग्रहण (RAM, HDD) डायनेमिक रैंडम-एक्सेस मेमोरी, हार्ड डिस्क ड्राइव,को संकेत करता है, और समय का अर्थ दिए गए कार्य को करने में उपयोग होने वाला समय होता है।
CPUएक दिए गए स्थान-समय के व्यापार की उपयोगिता पर संबंधित स्थिर और परिवर्तनशील लागतों जैसे सीपीयू की गति, संग्रहण स्थान की लागत का प्रभाव पड़ता है, और इसे घटती लाभ की प्राप्ति का सामर्थ्य होता है
इतिहास
पशुओं के व्यवहार के पूर्व चरणों में समय-मेमोरी के व्यापार का जीववैज्ञानिक उपयोग देखा जा सकता है। डीएनए में संग्रहित ज्ञान का उपयोग करना या प्रायोगिकता के प्रतिक्रियाओं को "सहज ज्ञान" के रूप में कोड करके, समय-महत्वपूर्ण परिस्थितियों में गणना की आवश्यकता से बचाया जा सकता है। कंप्यूटरों के संदर्भ में अधिक विशिष्ट रूप से कहें तो, लुकअप तालिकाएं सबसे पहले से ही ऑपरेटिंग सिस्टम के प्रारंभिक संस्करणों से लागू की जाती रही हैं।
1980 में मार्टिन हेलमैन ने पहली बार क्रिप्ट विश्लेषण के लिए समय-मेमोरी के व्यापार का उपयोग करने का प्रस्ताव दिया।[1]
व्यापार के प्रकार
लुकअप तालिका के विरुद्ध पुनर्गणना
एक सामान्य स्थिति एक कलन विधि है, जिसमें एक लुकअप तालिका सम्मिलित है। एक कार्यान्वयन में संपूर्ण तालिका सम्मिलित हो सकती है, जो अभिकलन समय को कम करती है, परंतु आवश्यक मेमोरी की मात्रा को बढ़ाती है, या यह आवश्यकतानुसार तालिका प्रविष्टियों की गणना कर सकती है, जो अभिकलन समय में वृद्धि कर सकती है, परंतु मेमोरी आवश्यकताओं को कम कर सकती है।
डाटाबेस इंडेक्स फुल टेबल स्कैन
डाटाबेस मैनेजमेंट सिस्टम डाटाबेस इंडेक्स डेटा स्ट्रक्चर बनाने की क्षमता प्रदान करते हैं। इंडेक्स अतिरिक्त स्थान की कीमत पर लुकअप ऑपरेशंस की गति में सुधार करते हैं। अनुक्रमणिका के बिना, वांछित डेटा का पता लगाने के लिए कभी-कभी समय लेने वाली पूर्ण तालिका स्कैन संचालन की आवश्यकता होती है।
संपीड़ित बनाम असम्पीडित डेटा
डेटा संग्रहण की समस्या के लिए स्पेस-टाइम व्यापार लागू किया जा सकता है। यदि डेटा असम्पीडित संग्रहीत किया जाता है, तो यह अधिक स्थान लेता है, परंतु डेटा को संपीड़ित करने की तुलना में एक्सेस में कम समय लगता है (चूंकि डेटा को संपीड़ित करने से इसमें लगने वाले स्थान की मात्रा कम हो जाती है, परंतु डेटा संपीड़न को चलाने में समय लगता है)। समस्या के विशेष उदाहरण के आधार पर, कोई भी तरीका व्यावहारिक है। ऐसे दुर्लभ उदाहरण भी हैं जहां संपीड़ित डेटा के साथ सीधे काम करना संभव है, जैसे संपीड़ित बिटमैप इंडेक्स के मामले में, जहां संपीड़न के बिना संपीड़न के साथ काम करना तेज़ होता है।
री-रेंडरिंग बनाम संगृहीत चित्र
किसी वेक्टर ग्राफ़िक्स के केवल [[स्केलेबल वेक्टर ग्राफिक्स]] स्रोत को संग्रहीत करना और हर बार पृष्ठ के लिए अनुरोध किए जाने पर इसे बिटमैप के रूप में प्रस्तुत करना स्पेस के लिए ट्रेडिंग समय होगा; अधिक समय का उपयोग, परंतु कम जगह। जब पृष्ठ बदला जाता है तो छवि को प्रस्तुत करना और प्रदान की गई छवियों को संग्रहीत करना समय के लिए व्यापार स्थान होगा; अधिक जगह का उपयोग, परंतु कम समय। इस तकनीक को आमतौर पर कैश (अभिकलन ) के रूप में जाना जाता है।
छोटा कोड बनाम लूप अनोलिंग
लूप अनोलिंग लागू करते समय उच्च प्रोग्राम गति के लिए बड़े कोड आकार का व्यापार किया जा सकता है। यह तकनीक लूप के प्रत्येक पुनरावृत्ति के लिए कोड को लंबा बनाती है, परंतु प्रत्येक पुनरावृत्ति के अंत में लूप की शुरुआत में वापस कूदने के लिए आवश्यक संगणना समय को बचाती है।
अन्य उदाहरण
स्पेस-टाइम व्यापार का उपयोग करने वाले एल्गोरिदम में शामिल हैं:
- असतत लघुगणक की गणना के लिए बेबी-स्टेप जाइंट-स्टेप एल्गोरिद्म
- क्रिप्टोग्राफी में रेनबो टेबल, जहां विरोधी जानवर-बल के हमले के लिए आवश्यक घातीय समय से बेहतर करने की कोशिश कर रहा है। क्रिप्टोग्राफ़िक हैश फ़ंक्शन के हैश स्थान में रेनबो टेबल आंशिक रूप से पूर्व-गणना किए गए मानों का उपयोग सप्ताहों के बजाय मिनटों में पासवर्ड क्रैक करने के लिए करते हैं। इंद्रधनुष तालिका के आकार को कम करने से हैश स्थान पर पुनरावृति करने में लगने वाला समय बढ़ जाता है।
- बीच-बीच में हमला केवल कुंजी (क्रिप्टोग्राफी) खोजने के लिए स्पेस-टाइम व्यापार का उपयोग करता है एन्क्रिप्शन (और अंतरिक्ष) बनाम अपेक्षित एन्क्रिप्शन (परंतु केवल अंतरिक्ष) भोले हमले की।
- गतिशील प्रोग्रामिंग, जहाँ अधिक मेमोरी का उपयोग करके किसी समस्या की समय जटिलता को काफी कम किया जा सकता है।
यह भी देखें
- Algorithmic efficiency
- Blum's speedup theorem
- Computational complexity
- Computational resource
- Savitch's theorem
संदर्भ
- ↑ 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.
