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

एक स्पेस-टाइम अदला - बदली, जिसे टाइम-मेमोरी ट्रेड-ऑफ़ या कलन विधि स्पेस-टाइम कॉन्टिनम के रूप में भी जाना जाता है, कंप्यूटर विज्ञान में एक ऐसा मामला है जहां एक एल्गोरिथम या कंप्यूटर प्रोग्राम ट्रेड-ऑफ़ घटे हुए समय के साथ अंतरिक्ष उपयोग में वृद्धि करता है। यहाँ, स्पेस किसी दिए गए कार्य (डायनेमिक रैंडम-एक्सेस मेमोरी, हार्ड डिस्क ड्राइव, आदि) को करने में लगने वाले कंप्यूटर भंडारण को संदर्भित करता है, और टाइम किसी दिए गए कार्य को करने में लगने वाले समय को संदर्भित करता है (समय) जटिलता समय या प्रतिक्रिया समय (प्रौद्योगिकी))।

किसी दिए गए स्पेस-टाइम ट्रेडऑफ़ की उपयोगिता संबंधित निश्चित लागत और परिवर्तनीय लागतों (उदाहरण के लिए, 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.