हम जानते हैं कि त्वरित क्रम सबसे अच्छा सॉर्टिंग एल्गोरिदम है।क्यों Collections.sort Quicksort के बजाय मर्ज सॉर्ट का उपयोग करता है?
संग्रह .sort त्वरित प्रकार के बजाय मर्ज सॉर्ट एल्गोरिदम का उपयोग करता था। लेकिन Arrays.sort त्वरित प्रकार का उपयोग करता है।
संग्रह .sort त्वरित प्रकार के बजाय मर्ज सॉर्ट का कारण क्या है?
अत्यधिक जोश बलोच § से होने की संभावना:
मैं इन तरीकों बारे में था, इसलिए मुझे लगता है कि मैं जवाब देने के लिए योग्य हूँ। यह सच है कि कोई भी सर्वश्रेष्ठ सॉर्टिंग एल्गोरिदम नहीं है। Quicksort जब mergesort की तुलना में दो प्रमुख तत्वों की कमी है:
यह (के रूप में Parsifal विख्यात) स्थिर नहीं है।
यह गारंटी एन लॉग एन प्रदर्शन नहीं है; यह पैथोलॉजिकल इनपुट पर वर्गबद्ध प्रदर्शन के लिए गिरावट कर सकते हैं। के रूप में वहाँ से (मूल्य) समानता अलग रूप में पहचान का बोध भी नहीं है
स्थिरता, आदिम प्रकार के लिए एक गैर मुद्दा है। और वर्गवार व्यवहार की संभावना बेन्टली और मैकइलरॉय के कार्यान्वयन (या बाद में Dual Pivot Quicksort के लिए) में अभ्यास में कोई समस्या नहीं माना गया था, यही कारण है कि इन क्विकॉर्ट प्रकारों का उपयोग आदिम प्रकारों के लिए किया गया था।
मनमानी वस्तुओं को सॉर्ट करते समय स्थिरता एक बड़ा सौदा है। उदाहरण के लिए, मान लीजिए कि आपके पास ईमेल संदेशों का प्रतिनिधित्व करने वाली ऑब्जेक्ट्स हैं, और आप उन्हें पहले तिथि के अनुसार क्रमबद्ध करते हैं, फिर प्रेषक द्वारा। आप उन्हें प्रत्येक प्रेषक के भीतर दिनांक द्वारा क्रमबद्ध करने की अपेक्षा करते हैं, लेकिन यह केवल तभी सच होगा यदि क्रम स्थिर है। यही कारण है कि हम ऑब्जेक्ट संदर्भों को सॉर्ट करने के लिए स्थिर प्रकार (मर्ज सॉर्ट) प्रदान करने के लिए चुने गए। (Techincally बोल, कई अनुक्रमिक स्थिर प्रकार प्रकार के उलटे क्रम में कुंजी पर एक कोषगत आदेश में परिणाम: अंतिम तरह सबसे महत्वपूर्ण उपकुंजी निर्धारित करता है।)
एक अच्छा पक्ष लाभ यह है कि मर्ज क्रमबद्ध है गारंटी एन लॉग एन (समय) प्रदर्शन कोई फर्क नहीं पड़ता कि इनपुट क्या है। निस्संदेह नीचे की ओर है: त्वरित क्रम एक "जगह में" है: इसे केवल लॉग एन बाहरी स्थान (कॉल स्टैक को बनाए रखने के लिए) की आवश्यकता होती है। दूसरी तरफ मर्ज करें, सॉर्ट करें, को ओ (एन) बाहरी स्पेस की आवश्यकता है। टिमसार्ट संस्करण (जावा एसई 6 में पेश किया गया) के लिए इनपुट सरणी लगभग क्रमबद्ध होने पर काफी कम जगह (ओ (के)) की आवश्यकता होती है।
इसके अलावा, following प्रासंगिक है: java.util.Collections.sort द्वारा java.util.Arrays.sort और (परोक्ष रूप से) द्वारा इस्तेमाल किया वस्तु संदर्भ सॉर्ट करने के लिए एल्गोरिथ्म
एक है " संशोधित विलय (जिसमें मर्ज छोड़ा जाता है यदि में उच्चतम तत्व उच्च उपन्यास में सबसे कम तत्व से कम है)।"यह एक उचित तेज़ स्थिर प्रकार है जो ओ (एन लॉग एन) प्रदर्शन की गारंटी देता है और ओ (एन) अतिरिक्त स्थान की आवश्यकता होती है। इसके दिन (यह 1 99 7 में जोशुआ ब्लोच द्वारा लिखा गया था), यह एक अच्छा विकल्प था, लेकिन आज, लेकिन हम ज्यादा बेहतर कर सकते हैं।
2003 के बाद से अजगर की सूची तरह एक एल्गोरिथ्म timsort रूप में जाना जाता इस्तेमाल किया गया है (के बाद टिम पीटर्स, जो इसे लिखा था)। यह एक स्थिर, अनुकूली, पुनरावृत्ति mergesort दूर की आवश्यकता है कि एन 0 लॉग से कम (एन) तुलना आंशिक रूप से सॉर्ट किए गए सरणी पर चल रही है, जबकि प्रदर्शन यादृच्छिक सरणी पर चलने पर पारंपरिक विलय के समान तुलनीय है। सभी उचित विलय पोर्ट्सोर्ट है स्थिर और ओ (एन लॉग एन) समय (सबसे खराब मामला) में चलता है। सबसे बुरे मामले में, timsort को अस्थायी भंडारण एन/2 ऑब्जेक्ट संदर्भों के लिए स्थान की आवश्यकता होती है; सबसे अच्छे मामले में, इसे केवल स्थान की छोटी निरंतर मात्रा की आवश्यकता होती है। वर्तमान कार्यान्वयन के साथ इसकी तुलना करें, जिसे हमेशा n ऑब्जेक्ट संदर्भों के लिए अतिरिक्त स्थान की आवश्यकता होती है, और केवल क्रमबद्ध सूचियों पर n लॉग n को धड़कता है।
टिमसोर्ट का विस्तार यहां वर्णन किया गया है: http://svn.python.org/projects/python/trunk/Objects/listsort.txt।
टिम पीटर्स का मूल कार्यान्वयन सी। जोशुआ ब्लोच में सी से जावा में लिखा गया है और अंत में परीक्षण किया गया है, बेंचमार्क किया गया है, और परिणामस्वरूप बड़े पैमाने पर कोड को ट्यून किया गया है। परिणामस्वरूप कोड java.util.Arrays.sort के लिए एक ड्रॉप-इन प्रतिस्थापन है। अत्यधिक आदेशित डेटा पर, यह कोड वर्तमान कार्यान्वयन के रूप में तेज़ी से 25 गुना तक चला सकता है ( हॉटस्पॉट सर्वर वीएम पर)। यादृच्छिक डेटा पर, पुराने और नए कार्यान्वयन की गति तुलनीय हैं। बहुत छोटी सूचियों के लिए, नया कार्यान्वयन काफी तेज़ है कि पुराना डेटा पर पुराना भी है (क्योंकि यह अनावश्यक डेटा प्रतिलिपि से बचाता है)।
इसके अलावा, Is Java 7 using Tim Sort for the Method Arrays.Sort? देखें।
कोई भी "सर्वश्रेष्ठ" विकल्प नहीं है। कई अन्य चीजों के साथ, यह ट्रेडऑफ के बारे में है।
जब तक आप उत्तर देने के लिए जेडीके लेखक नहीं प्राप्त कर सकते हैं, तो आपको अनुमान लगाना होगा। असली सवाल नहीं है। – EJP
@EJP अच्छा बिंदु, लेकिन निश्चित रूप से "रचनात्मक नहीं" सही बंद कारण है। यह मुझे स्पष्ट है कि सवाल क्या है। –
क्योंकि जावा लोगों ने ऐसा करने का फैसला किया था। उनसे पूछों। मुझे लगता है कि आप यहां एक वैध जवाब नहीं प्राप्त कर सकते हैं। और त्वरित प्रकार ** ** नहीं ** सबसे अच्छा है। ** सामान्य उपयोग ** के लिए यह केवल सर्वोत्तम है। –