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

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

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

इतिहास

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

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

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

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

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

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

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

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

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

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

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

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

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

अन्य उदाहरण

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

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

यह भी देखें

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

बाहरी संबंध

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