समष्टि-समय का व्यापार

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

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

इतिहास

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

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

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

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

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

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

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

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

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

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

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

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

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

अन्य उदाहरण

स्पेस-टाइम व्यापार का उपयोग करने वाले एल्गोरिदम में शामिल हैं:

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

यह भी देखें

• Algorithmic efficiency
• Blum's speedup theorem
• Computational complexity
• Computational resource
• Savitch's theorem

बाहरी संबंध

• Philippe Oechslin: Making a Faster Cryptanalytic Time-Memory Trade-Off.
• Once Upon a Time-Memory Tradeoff.