अधिकतर सॉर्ट किए गए डेटा के लिए एक अच्छा सॉर्टिंग एल्गोरिदम जो स्मृति में फिट नहीं है?

Question

मामले में आप दिए गए हैं:

• डेटा की निश्चित राशि
डेटा आकार डेटा की
• हिस्सा क्रमबद्ध हो जाता है के आकार आधे के साथ
• स्मृति
• आप हल कर के आकार पता नहीं है डेटा।

आप किस क्रमबद्ध एल्गोरिदम का चयन करेंगे? मैं सम्मिलन और क्विकॉर्ट के बीच बहस कर रहा हूं। मुझे पता है कि सम्मिलन प्रकार के लिए सबसे अच्छा मामला ओ (एन) है, लेकिन सबसे खराब मामला ओ (एन) है। इसके अलावा, इस तथ्य पर विचार करते हुए कि स्मृति सीमित है, मैं डेटा को दो हिस्सों में विभाजित कर दूंगा, और उनमें से प्रत्येक को quicksort करना होगा, फिर सबकुछ एक साथ मिलाएं। ओ (एन) डेटा को विभाजित करने के लिए ओ (एन) समय ले जाएगा, ओ (एन) डेटा को मर्ज करने के लिए, और ओ (एन लॉग एन) ओ (एन लॉग एन) के नेट रनटाइम के लिए, Quicksort का उपयोग कर डेटा को सॉर्ट करने के लिए।

क्या किसी को भी इसे सुधारने के बारे में कोई सुझाव है?

Answer 1

आपका विलय-जैसा दृष्टिकोण बहुत उचित लगता है। अधिक आम तौर पर, इस प्रकार के सॉर्टिंग एल्गोरिदम को external sorting algorithm कहा जाता है। ये एल्गोरिदम अक्सर आपके द्वारा वर्णित कार्य के रूप में काम करते हैं - डेटा के कुछ सबसेट को स्मृति में लोड करें, इसे सॉर्ट करें, फिर उसे डिस्क पर वापस लिखें। अंत में, एक साथ वापस सब कुछ मर्ज करने के लिए एक विलय एल्गोरिदम का उपयोग करें। कितना लोड करना है और किस प्रकार के एल्गोरिदम का उपयोग करना पसंद है, आमतौर पर प्रमुख चिंताएं होती हैं। मैं ज्यादातर सॉर्टिंग एल्गोरिदम पसंद पर ध्यान केंद्रित करूंगा।

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

उसने कहा, चूंकि आप जानते हैं कि डेटा पहले ही आंशिक रूप से क्रमबद्ध है, तो आप अपने सॉर्टिंग चरण के लिए adaptive sorting algorithm देख सकते हैं। आपने इसके लिए सम्मिलन प्रकार का उल्लेख किया है, लेकिन वहां बहुत बेहतर अनुकूली एल्गोरिदम हैं। यदि स्मृति दुर्लभ है (जैसा आपने वर्णन किया है), तो आप smoothsort एल्गोरिदम में देखने का प्रयास करना चाहेंगे, जिसमें सबसे अच्छा केस रनटाइम ओ (एन), सबसे खराब केस रनटाइम ओ (एन लॉग एन) है, और केवल उपयोग करता है ओ (1) स्मृति। यह कुछ अन्य एल्गोरिदम (जैसे पायथन के timsort, natural mergesort, या Cartesian tree sort) के रूप में अनुकूली नहीं है, लेकिन इसमें कम स्मृति उपयोग है। यह एक अच्छा क्विकॉर्ट के रूप में भी तेज़ नहीं है, लेकिन यदि डेटा वास्तव में अधिकतर सॉर्ट किया जाता है तो यह बहुत अच्छा कर सकता है।

आशा है कि इससे मदद मिलती है!

Answer 2

इसके चेहरे पर, मैं & को विभाजित करता हूं और इसे एक दिन कॉल करता हूं। कई एल्गोरिदम समस्याओं को अधिक विचार किया जाता है।

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

मान लें कि many sorting algorithms हैं और कुछ क्रमबद्ध सेट के लिए बेहतर हैं। साथ ही, जब आप जानते हैं कि एक सेट सॉर्ट किया गया है, तो आप इसे n समय में किसी अन्य सेट के साथ विलय कर सकते हैं। इस प्रकार, सॉर्ट किए गए डेटा के हिस्सों की पहचान करने से पहले आपको बहुत समय बचा सकता है जब आप एक सिंगल (एन) पास जोड़ने की तुलना करते हैं और क्विक्सॉर्ट (एन) पर जाने का मौका बहुत कम करते हैं।