एल्गोरिदम: हाइब्रिड MergeSort और InsertionSort निष्पादन समय

Question

शुभ दिन अतः समुदाय,

मैं वर्तमान में एक प्रयोग MergeSort और InsertionSort संयोजन प्रदर्शन कर एक सीएस का छात्र हूं। यह समझा जाता है कि एक निश्चित दहलीज के लिए, एस, InsertionSort MergeSort की तुलना में एक त्वरित निष्पादन समय होगा। इसलिए, दोनों सॉर्टिंग एल्गोरिदम विलय करके, कुल रनटाइम अनुकूलित किया जाएगा।

हालांकि, कई बार प्रयोग चलाने के बाद, 1000 के नमूना आकार और एस के विभिन्न आकारों का उपयोग करके, प्रयोग के परिणाम हर बार एक निश्चित उत्तर नहीं देते हैं।

अब, 3500 का एक नमूना आकार के साथ एक ही एल्गोरिथ्म कोड की कोशिश कर रहा:: यहाँ प्राप्त बेहतर परिणाम की एक तस्वीर (ध्यान दें समय की है कि आधे परिणाम के रूप में निश्चित नहीं है) है

अंत में, 500,000 का एक नमूना आकार के साथ एक ही एल्गोरिथ्म कोड की कोशिश कर रहा (ध्यान दें कि y- अक्ष मिलीसेकेंड में है:

हालांकि तर्कसंगत रूप से, एस < = 10 के रूप में हाइब्रिड मर्जोर्ट तेज होगा, क्योंकि InsertionSort में रिकर्सिव ओवरहेड टाइम नहीं है। हालांकि, मेरे मिनी प्रयोग के परिणाम अन्यथा कहते हैं।

MergeSort: O (n n लॉग इन करें)

InsertionSort:

• बेस्ट मामला: θ (एन)
• सबसे बुरे

  वर्तमान में, इन समय जटिलताओं मुझे सिखाया जाता है केस: θ (एन^2)

अंत में, मुझे एक ऑनलाइन स्रोत मिला है: https://cs.stackexchange.com/questions/68179/combining-merge-sort-and-insertion-sort जो स्थापित करती है:

हाइब्रिड MergeInsertionSort:

• बेस्ट मामला: θ (n + n लॉग इन करें (n/x))
• सबसे खराब मामला: θ (NX + n लॉग इन करें (n/एक्स))

मैं अगर वहाँ सीएस समुदाय है, जो निश्चित सबूत है कि एक हाइब्रिड MergeSort एल्गोरिथ्म एक निश्चित सीमा से, एस नीचे एक सामान्य MergeSort एल्गोरिथ्म की तुलना में बेहतर काम करेंगे, और यदि हां, तो क्यों चलता में परिणाम हैं पूछना चाहूँगा?

धन्यवाद इतना समुदाय, यह एक तुच्छ सवाल हो सकता है, लेकिन यह वास्तव में कई सवाल है कि मैं वर्तमान समय जटिलता और सामान :) के बारे में है स्पष्ट करेगी

नोट: मैं की कोडिंग के लिए जावा का उपयोग कर रहा एल्गोरिदम, और रनटाइम जावा द्वारा डेटा को स्मृति में संग्रहीत करने के तरीके से प्रभावित हो सकता है ..जावा में

कोड:

public static int mergeSort2(int n, int m, int s, int[] arr){ 
     int mid = (n+m)/2, right=0, left=0; 
     if(m-n<=s) 
      return insertSort(arr,n,m); 
     else 
     { 
      right = mergeSort2(n, mid,s, arr); 
      left = mergeSort2(mid+1,m,s, arr); 
      return right+left+merge(n,m,s,arr); 
     }  
    } 

    public static int insertSort(int[] arr, int n, int m){ 
     int temp, comp=0; 
     for(int i=n+1; i<= m; i++){ 
      for(int j=i; j>n; j--){ 
       comp++; 
       comparison2++; 
       if(arr[j]<arr[j-1]){ 
        temp = arr[j]; 
        arr[j] = arr[j-1]; 
        arr[j-1] = temp; 
       } 
       else 
        break; 
      } 
     } 
     return comp; 
    } 

    public static void shiftArr(int start, int m, int[] arr){ 
     for(int i=m; i>start; i--) 
      arr[i] = arr[i-1];  
    } 

public static int merge(int n, int m, int s, int[] arr){ 
     int comp=0; 
     if(m-n<=s) 
      return 0; 
     int mid = (n+m)/2; 
     int temp, i=n, j=mid+1; 
     while(i<=mid && j<=m) 
     { 
      comp++; 
      comparison2++; 


      if(arr[i] >= arr[j]) 
      { 
       if(i==mid++&&j==m && (arr[i]==arr[j])) 
        break; 
       temp = arr[j]; 
       shiftArr(i,j++,arr); 
       arr[i] = temp; 
       if(arr[i+1]==arr[i]){ 
        i++; 
       } 
      } 
      i++; 


     } 
     return comp; 
    } 

Answer 1

उदाहरण कोड एक पारंपरिक मर्ज तरह नहीं है। मर्ज फ़ंक्शन मूल सरणी और अस्थायी वर्किंग सरणी और पीछे के बीच रन विलय करने के बजाय सरणी को स्थानांतरित कर रहा है।

मैंने ऊपर और नीचे विलय प्रकारों का परीक्षण किया है और दोनों 500,000 32 बिट पूर्णांक को क्रमबद्ध करने के लिए 42 एमएस == 0.042 सेकेंड लेते हैं, जो ग्राफ में स्पष्ट परिणाम बनाम हैं जो 42 एमएस के बजाय लगभग 42 सेकंड में 1000 गुना धीमे होते हैं । मैंने 10,000,000 पूर्णांक के साथ भी परीक्षण किया और क्रमबद्ध करने में थोड़ा सा समय लगता है।

अतीत में, सी ++ का उपयोग करते हुए, मैंने एक हाइब्रिड तल अप विलय/सम्मिलन क्रम के साथ एक नीचे अप मर्ज सॉर्ट की तुलना की, और 16 मिलियन (2^24 == 16,777,216) 32 बिट पूर्णांक के लिए, हाइब्रिड सॉर्ट लगभग 8 था एस == के साथ% तेज़ 16. एस == 64 एस == की तुलना में थोड़ा धीमा था 16. विजुअल स्टूडियो std :: stable_sort नीचे अप मर्ज सॉर्ट की एक भिन्नता है (अस्थायी सरणी मूल सरणी का आकार 1/2 है) और सम्मिलन प्रकार, और एस == 32 का उपयोग करता है।

छोटे सरणी के लिए, प्रविष्टि सॉर्ट मर्ज सॉर्ट, कैश इलाके का संयोजन और प्रविष्टि प्रकार के साथ एक छोटी सरणी को सॉर्ट करने के लिए आवश्यक कम निर्देशों की तुलना में तेज़ है। छद्म यादृच्छिक डेटा और एस == 16 से 64 के लिए, प्रविष्टि क्रम मर्ज सॉर्ट के रूप में लगभग दोगुना तेज़ था।

सापेक्ष लाभ सरणी के आकार के रूप में कम हो जाता है। एस == 16 के साथ, नीचे अप विलय सॉर्ट पर प्रभाव को ध्यान में रखते हुए, केवल 4 मर्ज पास अनुकूलित किए जाते हैं। मेरे परीक्षण मामले में 2^24 == 16,777,216 तत्वों के साथ, यह 4/24 = 1/6 ~ = पास की संख्या का 16.7% है, जिसके परिणामस्वरूप लगभग 8% सुधार होता है (इसलिए सम्मिलन क्रम विलय के रूप में लगभग दोगुना तेज़ होता है उन 4 पास के लिए क्रमबद्ध करें)। विलय के लिए कुल समय लगभग 1.52 सेकंड थे, और हाइब्रिड सॉर्ट के लिए लगभग 1.40 सेकेंड, एक प्रक्रिया पर 0.12 सेकंड लाभ जो केवल 1.52 सेकेंड लेता है। एस == 16 के साथ, शीर्ष डाउन विलय सॉर्ट के लिए, रिकर्सन के 4 गहरे स्तर को अनुकूलित किया जाएगा।

अद्यतन - ओ (एन लॉग (एन)) समय जटिलता के साथ मर्ज सॉर्ट/सम्मिलन क्रम में एक हाइब्रिड के लिए उदाहरण जावा कोड उदाहरण। (नोट - रिकर्सन के कारण सहायक भंडारण अभी भी ढेर पर खपत है।) जगह में भाग क्षेत्र में डेटा के साथ विलय किए गए क्षेत्र में डेटा को स्वैप करके मर्ज चरणों के दौरान पूरा किया जाता है। यह एक स्थिर प्रकार नहीं है (मर्ज चरणों के दौरान स्वैपिंग के कारण बराबर तत्वों का क्रम संरक्षित नहीं है)। 500,000 पूर्णांक को छंटनी एक सेकंड के लगभग 1/8 वें स्थान पर है, इसलिए मैंने इसे 16 मिलियन (2^24 == 16777216) पूर्णांक में बढ़ाया, जो 4 सेकंड से थोड़ा अधिक समय लेता है। सम्मिलन प्रकार के बिना, क्रम में लगभग 4.524 सेकंड लगते हैं, और एस == 64 के साथ सम्मिलन क्रम के साथ, क्रम में लगभग 4.150 सेकेंड लगते हैं, लगभग 8.8% लाभ। अनिवार्य रूप से सी में एक ही कोड के साथ, सुधार कम था: 2.88 सेकंड से 2.75 सेकंड तक, लगभग 4.5% लाभ।

package msortih; 
import java.util.Random; 

public class msortih { 

    static final int S = 64; // use insertion sort if size <= S 

    static void swap(int[] a, int i, int j) { 
     int tmp = a[i]; a[i] = a[j]; a[j] = tmp; 
    } 

    // a[w:] = merged a[i:m]+a[j:n] 
    // a[i:] = reordered a[w:] 
    static void wmerge(int[] a, int i, int m, int j, int n, int w) { 
     while (i < m && j < n) 
      swap(a, w++, a[i] < a[j] ? i++ : j++); 
     while (i < m) 
      swap(a, w++, i++); 
     while (j < n) 
      swap(a, w++, j++); 
    } 

    // a[w:] = sorted a[b:e] 
    // a[b:e] = reordered a[w:] 
    static void wsort(int[] a, int b, int e, int w) { 
     int m; 
     if (e - b > 1) { 
      m = b + (e - b)/2; 
      imsort(a, b, m); 
      imsort(a, m, e); 
      wmerge(a, b, m, m, e, w); 
     } 
     else 
      while (b < e) 
       swap(a, b++, w++); 
    } 

    // inplace merge sort a[b:e] 
    static void imsort(int[] a, int b, int e) { 
     int m, n, w, x; 
     int t; 
     // if <= S elements, use insertion sort 
     if (e - b <= S){ 
      for(n = b+1; n < e; n++){ 
       t = a[n]; 
       m = n-1; 
       while(m >= b && a[m] > t){ 
        a[m+1] = a[m]; 
        m--;} 
       a[m+1] = t;} 
      return; 
     } 
     if (e - b > 1) { 
      // split a[b:e] 
      m = b + (e - b)/2; 
      w = b + e - m; 
      // wsort -> a[w:e] = sorted a[b:m] 
      //   a[b:m] = reordered a[w:e] 
      wsort(a, b, m, w); 
      while (w - b > 2) { 
       // split a[b:w], w = new mid point 
       n = w; 
       w = b + (n - b + 1)/2; 
       x = b + n - w; 
       // wsort -> a[b:x] = sorted a[w:n] 
       //   a[w:n] = reordered a[b:x] 
       wsort(a, w, n, b); 
       // wmerge -> a[w:e] = merged a[b:x]+a[n:e] 
       //   a[b:x] = reordered a[w:n] 
       wmerge(a, b, x, n, e, w); 
      } 
      // insert a[b:w] into a[b:e] using left shift 
      for (n = w; n > b; --n) { 
       t = a[n-1]; 
       for (m = n; m < e && a[m] < t; ++m) 
        a[m-1] = a[m]; 
       a[m-1] = t; 
      } 
     } 
    } 

    public static void main(String[] args) { 
     int[] a = new int[16*1024*1024]; 
     Random r = new Random(0); 
     for(int i = 0; i < a.length; i++) 
      a[i] = r.nextInt(); 
     long bgn, end; 
     bgn = System.currentTimeMillis(); 
     imsort(a, 0, a.length); 
     end = System.currentTimeMillis(); 
     for(int i = 1; i < a.length; i++){ 
      if(a[i-1] > a[i]){ 
       System.out.println("failed"); 
       break; 
      } 
     } 
     System.out.println("milliseconds " + (end-bgn)); 
    } 
}