एक मेमोरी-अनुकूली मर्ज एल्गोरिदम?

Question

कई एल्गोरिदम एक अलग सॉर्ट किए गए सरणी में दो अलग सॉर्ट किए गए सरणी को मर्ज करने के लिए merge algorithm का उपयोग करके काम करते हैं। उदाहरण के लिए, इनपुट के रूप में दिया सरणियों

1 3 4 5 8 

और

2 6 7 9 

इन सरणियों के मर्ज सरणी

1 2 3 4 5 6 7 8 9 

परंपरागत रूप से, विलय करने के लिए दो अलग-अलग दृष्टिकोण होने लगते होगा सॉर्ट किए गए सरणी (ध्यान दें कि लिंक्ड सूचियों को विलय करने का मामला काफी अलग है)। सबसे पहले, जगह के बाहर मर्ज एल्गोरिदम हैं जो भंडारण के लिए एक अस्थायी बफर आवंटित करके काम करते हैं, फिर अस्थायी बफर में विलय के परिणाम को संग्रहीत करते हैं। दूसरा, यदि दो सरणी एक ही इनपुट सरणी का हिस्सा बनती हैं, तो in-place merge algorithms हैं जो केवल ओ (1) सहायक स्टोरेज स्पेस का उपयोग करते हैं और दो अनुक्रमित अनुक्रमों को एक क्रमबद्ध अनुक्रम में पुनर्व्यवस्थित करते हैं। ओ (एन) समय में दोनों एल्गोरिदम दोनों चलते हैं, लेकिन आउट-ऑफ-प्लेस विलय एल्गोरिदम में बहुत कम स्थिर कारक होता है क्योंकि इसमें ऐसी कठोर स्मृति आवश्यकताएं नहीं होती हैं।

मेरा सवाल यह है कि क्या एक ज्ञात विलय करने वाला एल्गोरिदम है जो इन दो दृष्टिकोणों के बीच "इंटरपोलेट" कर सकता है। यही है, एल्गोरिदम ओ (1) और ओ (एन) मेमोरी के बीच कहीं भी उपयोग करेगा, लेकिन इसके लिए जितनी अधिक मेमोरी उपलब्ध है, उतनी तेज़ी से चलती है। उदाहरण के लिए, अगर हम एल्गोरिदम द्वारा किए गए सरणी पढ़ने/लिखने की पूर्ण संख्या को मापने के लिए थे, तो इसमें फॉर्म एनजी (एस) + एफ (एस) का रनटाइम हो सकता है, जहां एस के लिए उपलब्ध स्थान की मात्रा है और जी (एस) और एफ (एस) उपलब्ध अंतरिक्ष की मात्रा से व्युत्पन्न कार्य हैं। इस फ़ंक्शन का लाभ यह है कि यह संभवतः मेमोरी बाधाओं को संभवतः सबसे प्रभावी तरीके से दो सरणी में विलय करने का प्रयास कर सकता है - सिस्टम पर उपलब्ध अधिक मेमोरी, जितनी अधिक मेमोरी इसका उपयोग करेगी और (आदर्श) बेहतर प्रदर्शन होगा ।

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

किसी को भी इस तरह के एक एल्गोरिथ्म से परिचित है (या एक का एक विवरण खोजने के लिए देखने के लिए जहां पता है?)

Answer 1

"अपने रन-टाइम जटिलता निर्भर करता है कम से कम प्रलेखन के अनुसार, in-place merge function in SGI STL अनुकूली जाता है और कितनी मेमोरी उपलब्ध है "। स्रोत कोड निश्चित रूप से उपलब्ध है, आप इसे कम से कम जांच सकते हैं।

Answer 2

संपादित करें: एसटीएल में inplace_merge है, जो अस्थायी बफर के आकार के अनुकूल होगा। यदि अस्थायी बफर कम से कम उप-सरणी में से एक के रूप में बड़ा है, तो यह ओ (एन) है। अन्यथा, यह मर्ज को दो उप-विलय और रिकर्स में विभाजित करता है। विभाजन (बाइनरी खोज) में घूमने के लिए अन्य उप सरणी का सही भाग खोजने के लिए ओ (लॉग एन) लेता है।

तो यह आपके द्वारा उपलब्ध कितनी मेमोरी के आधार पर ओ (एन) से ओ (एन लॉग एन) से जाता है।