büyük tablolar için garip yavaş quicksort

Question

Bir dizi sıralama algoritmasını karşılaştırmak için ev ödevimi yapıyorum ve garip bir fenomene rastladım. Şeyler beklendiği gibi oldu: insertionsort 20 inçlik tablo gibi bir şey için kazanma, aksi halde çabukluğu, heapsort ve mergesort üstün performans. 500.000 inçlik bir tabloya kadar (bellekte saklanır). 5.000.000 inç (hala hafızada saklanır) için, hızlı bağlantı, aniden daha kötü hale gelir, ardından heapsort ve mergesort. Sayılar her zaman eşit olarak dağıtılır, rasgele pencereler sanal bellek kapalıdır. Bunun sebebi ne olabilir?

 void quicksortit(T *tab,int s) { 
        if (s==0 || s==1) return; 
        T tmp; 
        if (s==2) { 
         if (tab[0]>tab[1]) { 
             tmp=tab[0]; 
             tab[0]=tab[1]; 
             tab[1]=tmp; 
             } 
         return; 
         } 
        T pivot=tab[s-1]; 
        T *f1,*f2; 
        f1=f2=tab; 
        for(int i=0;i<s;i++) 
          if (*f2>pivot) 
           f2++; 
          else { 
           tmp=*f1; 
           *f1=*f2; 
           *f2=tmp; 
           f1++; f2++; 
           } 
        quicksortit(tab,(f1-1)-tab); 
        quicksortit(f1,f2-f1); 
    }; 

Answer 1

Dizide çok sayıda yineleme olduğunda algoritma başarısız oluyor. Bunu sadece büyük değerlerde fark ettiniz, çünkü büyük bir yayılma alanı olan
aralığındaki rastgele değerleri beslemektesiniz (rand: (0 - RAND_MAX) ile rand() kullandığınızı varsayalım ve bu problem sadece büyük dizilerde görünüyor.

Aynı sayıda bir diziyi sıralamaya çalıştığınızda (100000 aynı sayıları ayırmayı deneyin, program çökecektir) ilk önce tüm dizi boyunca gereksiz şekilde değiştiren öğelerden geçeceksiniz. Daha sonra ikiye dizi bölme, ancak büyük dizisi yalnızca 1 azaltılmıştır:

    v 
quicksortit(tab,(f1-1)-tab); 

Böylece Algoritma (n^2) O olur ve aynı zamanda istifin, çok büyük miktarda tüketir. Daha iyi bir pivot aramak, bu durumda size yardımcı olmayacaktır, bunun yerine bu kusuru sergilemeyen bir quicksort() sürümü seçin.

değiştirilmiş bir sürümü olan

function quicksort(array) 
    if length(array) > 1 
     pivot := select middle, or a median of first, last and middle 
     left := first index of array 
     right := last index of array 
     while left <= right 
      while array[left] < pivot 
       left := left + 1 
      while array[right] > pivot 
       right := right - 1 
      if left <= right 
       swap array[left] with array[right] 
       left := left + 1 
       right := right - 1 
     quicksort(array from first index to right) 
     quicksort(array from left to last index) 

: Sana verdiğim ne sistem bilmiyorum http://rosettacode.org/wiki/Sorting_algorithms/Quicksort

Answer 2

Diziniz artık L3 önbellekten daha büyük olabilir.

Quicksort bölümleme işlemi, rasgele öğeleri dizinin bir ucundan diğerine taşır. Tipik bir intel L3 önbellek 8MB gibi. 5M 4-byte elemanları ile - diziniz 20MB'dir. ve bir ucundan diğerine yazıyorsunuz.

Önbellek L3'ü ana belleğe kaydeder ve daha yüksek düzeyde önbellek eksiklerinden çok daha yavaş olabilir.

Şimdiye kadar olan tüm sıralama işlemi tamamen CPU'nun içinde çalışıyordu.