फास्ट एल्गोरिदम कार्यान्वयन बहुत छोटी सूची को क्रमबद्ध करने के लिए

Question

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

मेरा दृष्टिकोण अधिकतम/न्यूनतम कार्यों का उपयोग करना था (4 संख्याओं को क्रमबद्ध करने के लिए 10 कार्य, कोई शाखाएं, आईआईआरसी)।

// s(i,j) == max(i,j), min(i,j) 
i,j = s(i,j) 
k,l = s(k,l) 
i,k = s(i,k) // i on top 
j,l = s(j,l) // l on bottom 
j,k = s(j,k) 

मुझे लगता है कि मेरा प्रश्न एल्गोरिदम के प्रकार के बजाय कार्यान्वयन के लिए अधिक प्रासंगिक है।

इस बिंदु पर यह कुछ हद तक हार्डवेयर निर्भर हो जाता है, तो आइए एसएसई 3 के साथ इंटेल 64-बिट प्रोसेसर मान लें।

धन्यवाद

Answer 1

इस तरह के छोटे सरणी के लिए, आपको शायद sorting networks में देखना चाहिए। जैसा कि आप उस पृष्ठ पर देख सकते हैं, सम्मिलन प्रकार को सॉर्टिंग नेटवर्क के रूप में व्यक्त किया जा सकता है। हालांकि, अगर आप पहले से सरणी के आकार को जानते हैं, तो आप एक इष्टतम नेटवर्क तैयार कर सकते हैं। this site पर एक नज़र डालें जो आपको दिए गए आकार के लिए इष्टतम सॉर्टिंग नेटवर्क खोजने में मदद कर सकता है (हालांकि इष्टतम केवल 16 के आकार के लिए गारंटीकृत है)। तुलनित्रों को भी संचालन में एक साथ समूहीकृत किया जाता है जो समानांतर में किया जा सकता है। तुलनित्र अनिवार्य रूप से आपके एस (एक्स, वाई) फ़ंक्शन के समान होते हैं, हालांकि यदि आप वास्तव में तेज़ी से होना चाहते हैं, तो आपको न्यूनतम और अधिकतम का उपयोग नहीं करना चाहिए क्योंकि आप आवश्यक तुलना की तुलना में दोगुना कर रहे हैं।

यदि आपको आकारों की एक विस्तृत श्रृंखला पर काम करने के लिए इस सॉर्टिंग एल्गोरिदम की आवश्यकता है, तो शायद आपको दूसरों के सुझाव के अनुसार सम्मिलन प्रकार के साथ जाना चाहिए।

Answer 2

इतनी छोटी डेटा सेट के लिए, आप संभव के रूप में एल्गोरिथ्म के रूप में सरल चाहते हैं। अधिक संभावना नहीं है, एक मूल Insertion Sort साथ ही साथ आप चाहें भी करेंगे।

इस प्रणाली के बारे में और जानना होगा कि यह कितना बार चल रहा है, आपको इस तरह की दूसरी बार इत्यादि करने की ज़रूरत है ... लेकिन छोटे नियमों में सामान्य नियम इसे सरल रखना है। Quicksort और पसंद फायदेमंद नहीं हैं।

Answer 3

सम्मिलन प्रकार छोटे सरणी के लिए सबसे अच्छा माना जाता है। देखें Fast stable sort for small arrays (under 32 or 64 elements)

Answer 4

मुझे लगता है कि आपके पास पहले से ही एक समाधान है जो 5 तुलनाओं का उपयोग करता है (माना जाता है कि एस (i, j) एक बार दो संख्याओं की तुलना करता है, और या तो उन्हें स्वैप करता है या नहीं)। यदि आप तुलना-आधारित सॉर्टिंग से चिपके रहते हैं, तो आप इसे 5 से कम तुलना के साथ नहीं कर सकते हैं।

यह साबित हो सकता है क्योंकि 4 हैं! = 4 संख्याओं को आदेश देने के 24 संभावित तरीके। प्रत्येक तुलना केवल आधे में संभावनाओं को काट सकती है, इसलिए 4 तुलनाओं के साथ आप केवल 2^4 = 16 संभावित ऑर्डरिंग के बीच अंतर कर सकते हैं।

Answer 5

छोटी संख्याओं को क्रमबद्ध करने के लिए आप एक साधारण एल्गोरिदम चाहते हैं क्योंकि जटिलता अधिक ओवरहेड जोड़ती है।

उदाहरण के लिए चार वस्तुओं को सॉर्ट करने रैखिक तुलना करने के लिए छँटाई कलन विधि को जानने की, इस प्रकार सभी भूमि के ऊपर elliminating होगा सबसे कारगर तरीका:

function sort(i,j,k,l) { 
    if (i < j) { 
    if (j < k) { 
     if (k < l) return [i,j,k,l]; 
     if (j < l) return [i,j,l,k]; 
     if (i < l) return [i,l,j,k]; 
     return [l,i,j,k]; 
    } else if (i < k) { 
     if (j < l) return [i,k,j,l]; 
     if (k < l) return [i,k,l,j]; 
     if (i < l) return [i,l,k,j]; 
     return [l,i,k,j]; 
    } else { 
     if (j < l) return [k,i,j,l]; 
     if (i < l) return [k,i,l,j]; 
     if (k < l) return [k,l,i,j]; 
     return [l,k,i,j]; 
    } 
    } else { 
    if (i < k) { 
     if (k < l) return [j,i,k,l]; 
     if (i < l) return [j,i,l,k]; 
     if (j < l) return [j,l,i,k]; 
     return [l,j,i,k]; 
    } else if (j < k) { 
     if (i < l) return [j,k,i,l]; 
     if (k < l) return [j,k,l,i]; 
     if (j < l) return [j,l,k,i]; 
     return [l,j,k,i]; 
    } else { 
     if (i < l) return [k,j,i,l]; 
     if (j < l) return [k,j,l,i]; 
     if (k < l) return [k,l,j,i]; 
     return [l,k,j,i]; 
    } 
    } 
} 

हालांकि, कोड आप जोड़ना प्रत्येक अतिरिक्त आइटम के लिए एक बहुत बढ़ता है । पांचवां आइटम जोड़ना कोड को लगभग चार गुना बड़ा बनाता है।आठ वस्तुओं पर यह लगभग 30000 लाइनें होगी, हालांकि यह अभी भी सबसे कुशल है, यह बहुत सी कोड है, और आपको एक प्रोग्राम लिखना होगा जो इसे सही करने के लिए कोड लिखता है।

Answer 6

सॉर्टिंग नेटवर्क को सिमड में आसानी से कार्यान्वित किया जा सकता है, हालांकि यह एन = 4 या एन = 8 के लिए बदसूरत हो जाता है हालांकि यह एक अच्छा विकल्प होगा। आदर्श रूप से आपको समवर्ती रूप से सॉर्ट करने के लिए बहुत से छोटे डेटा सेट की आवश्यकता होती है, यानी यदि आप 8 बिट मानों को सॉर्ट कर रहे हैं तो आप कम से कम 16 डेटा सेट सॉर्ट करना चाहते हैं - इस तरह की चीज सिम वैक्टर में करना बहुत मुश्किल है।

यह भी देखें: Fastest sort of fixed length 6 int array