Java.util.ArrayList.sort() सॉर्टिंग एल्गोरिदम

Question

मैं g12code पर java.util.ArrayList के sort() विधि के स्रोत कोड को देख रहा था। वे छोटे सरणी (आकार < 7) पर सम्मिलन प्रकार का उपयोग करते हैं और बड़े सरणी पर सॉर्ट मर्ज करते हैं। मैं बस सोच रहा था कि क्या इससे बहुत अंतर आता है कि वे केवल < आकार के सरणी के लिए सम्मिलन प्रकार का उपयोग करते हैं। चलने वाले समय में अंतर आधुनिक मशीनों पर शायद ही ध्यान देने योग्य होगा।

मैं Cormen में यह पढ़ा है:

हालांकि मर्ज प्रकार हे में चलता है (एन * logn) (एन * एन) बुरी से बुरी हालत समय और प्रविष्टि प्रकार हे में चलता बुरी से बुरी हालत समय, निरंतर सम्मिलन क्रम में कारक कई मशीनों पर छोटी समस्या के आकार के लिए अभ्यास में तेजी से बना सकते हैं। इस प्रकार, subproblems पर्याप्त रूप से छोटे होने पर विलय प्रकार के भीतर सम्मिलन प्रकार का उपयोग कर रिकर्सन की पत्तियों को मजबूत करने के लिए समझ में आता है।

मैं कुछ घटक है जो मैं की आवश्यकता के लिए एल्गोरिथ्म छँटाई के लिए बनाया गया है |, तो मैं, समय चलाने में अधिक से अधिक आकार अंतर से पहले (शायद आकार < 100 तक) के लिए प्रविष्टि-तरह के उपयोग पर विचार के रूप में तरह विलय की तुलना , स्पष्ट हो जाता है।

मेरा प्रश्न है आकार < 7 पर पहुंचने के पीछे विश्लेषण क्या है?

Answer 1

चलने वाले समय में अंतर आधुनिक मशीनों पर शायद ही ध्यान देने योग्य होगा।

छोटे सरणी को सॉर्ट करने में कितना समय लगता है जब आप महसूस करते हैं कि समग्र सॉर्टिंग एल्गोरिदम रिकर्सिव है, और छोटे सरणी प्रकार प्रभावी ढंग से उस रिकर्सन का मूल मामला है।

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

पीएस यह इंगित करने योग्य है कि Java7 डिफ़ॉल्ट रूप से Timsort का उपयोग करता है।

Answer 2

http://en.wikipedia.org/wiki/Timsort

"Timsort एक संकर छँटाई एल्गोरिथ्म, मर्ज प्रकार और सम्मिलन तरह, वास्तविक दुनिया डेटा के कई प्रकार पर अच्छा प्रदर्शन करने के लिए डिज़ाइन से प्राप्त होता है ... एल्गोरिथ्म पाता डेटा कि पहले से ही कर रहे हैं के सबसेट आदेश दिया गया है, और डेटा को अधिक कुशलतापूर्वक सॉर्ट करने के लिए सबसेट का उपयोग करता है। यह किसी पहचान किए गए सबसेट को विलय करके किया जाता है, जिसे रन कहा जाता है, मौजूदा रनों के साथ कुछ मानदंड पूरा होने तक। "

नंबर 7 के बारे में:।

"... इसके अलावा, यह देखा गया है कि सरपट फायदेमंद है केवल जब प्रारंभिक तत्व अन्य रन के पहले सात तत्वों में से एक नहीं है यह भी में MIN_GALLOP स्थापित किया जा रहा परिणाम 7. गैलोपिंग मोड की कमी से बचने के लिए, विलय करने वाले फ़ंक्शन मिनी-गैलप के मान को समायोजित करते हैं। यदि तत्व वर्तमान में विचाराधीन सरणी से है (यानी, सरणी जो लगातार कुछ समय के लिए तत्वों को वापस कर रही है) मिनी-गैलप का मूल्य एक से कम हो जाता है। अन्यथा, मान एक से बढ़ता है, इस प्रकार प्रवेश को गैलोपिंग मोड में वापस हतोत्साहित करता है। जब यह किया जाता है, यादृच्छिक डेटा के मामले में, मिनी-गैलप का मान इतना बड़ा हो जाता है, कि गैलोपिंग मोड में प्रवेश कभी नहीं होता है।

उस मामले में जहां मर्ज-हाय का उपयोग किया जाता है (यानी, विलय को दाएं से बाएं किया जाता है), डेटा के दाहिने छोर से गैलोपिंग की आवश्यकता होती है, यह अंतिम तत्व है। शुरुआत से गैलपिंग भी आवश्यक परिणाम देता है, लेकिन आवश्यकतानुसार अधिक तुलना करता है। इस प्रकार, गैलोपिंग के लिए एल्गोरिदम में वेरिएबल का उपयोग शामिल होता है जो इंडेक्स देता है जिस पर गैलोपिंग शुरू होनी चाहिए। इस प्रकार एल्गोरिदम किसी भी इंडेक्स पर गैलोपिंग मोड दर्ज कर सकता है और जैसा ऊपर बताया गया है, वैसे ही जारी है, जैसा कि यह 1, 3, 7, ...., (2k - 1) द्वारा ऑफसेट होने वाली अगली अनुक्रमणिका पर जांच करेगा .. और तो वर्तमान सूचकांक से। विलय-हाय के मामले में, सूचकांक के लिए ऑफसेट -1, -3, -7, .... "

Answer 3

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

Tim Peters’s description of the algorithm

आप शीर्षक "कम्प्यूटिंग minrun" अनुभाग पढ़ें

एक सार देने के लिए करना चाहिए, minrun सरणी का कटऑफ आकार है जिसके नीचे एल्गोरिदम सम्मिलन प्रकार का उपयोग करना शुरू कर देना चाहिए। इसलिए, हम हमेशा सरणी को क्रमबद्ध करेंगे आकार "minrun" जिस पर हमें पूरे सरणी को सॉर्ट करने के लिए मर्ज ऑपरेशन चलाने की आवश्यकता होगी।

java.util.ArrayList.sort() में, "minrun" को 7 होने के लिए चुना जाता है, लेकिन जहां तक ​​उपरोक्त दस्तावेज़ की मेरी समझ जाती है, यह मिथक को दर्शाती है और दिखाती है कि यह 2 की शक्तियों के करीब होना चाहिए और 256 से कम और 8 से अधिक। दस्तावेज़ से उद्धरण:

256 पर बाइनरी सम्मिलन क्रम में डेटा-मूवमेंट लागत स्पष्ट रूप से चोट पहुंचती है, और 8 पर फ़ंक्शन कॉल की संख्या में वृद्धि स्पष्ट रूप से चोट पहुंचती है। चुनना कुछ 2 की शक्ति यहां महत्वपूर्ण है, ताकि विलय पूरी तरह संतुलित हो जाएं (अगला अनुभाग देखें)।

जो बिंदु मैं बना रहा हूं वह यह है कि "मिनरन" 64 से कम की 2 (या 2 की शक्ति के नीचे) की कोई शक्ति हो सकती है, बिना टिमसॉर्ट के प्रदर्शन में बाधा डाले।