は、k番目の最小の数 - クイックソートより速いquickselect

Question

よりも私は（もっと一般的に最小の数をk番目）の中央値選択のためのO(n)複雑性を達成するために、次のquickselectのアルゴリズムを実装している：

static size_t partition(struct point **points_ptr, size_t points_size, size_t pivot_idx) 
{ 
    const double pivot_value = points_ptr[pivot_idx]->distance; 

    /* Move pivot to the end. */ 
    SWAP(points_ptr[pivot_idx], points_ptr[points_size - 1], struct point *); 

    /* Perform the element moving. */ 
    size_t border_idx = 0; 
    for (size_t i = 0; i < points_size - 1; ++i) { 
      if (points_ptr[i]->distance < pivot_value) { 
        SWAP(points_ptr[border_idx], points_ptr[i], struct point *); 
        border_idx++; 
      } 
    } 

    /* Move pivot to act as a border element. */ 
    SWAP(points_ptr[border_idx], points_ptr[points_size - 1], struct point *); 

    return border_idx; 
} 

static struct point * qselect(struct point **points_ptr, size_t points_size, size_t k) 
{ 
    const size_t pivot_idx = partition(points_ptr, points_size, rand() % points_size); 

    if (k == pivot_idx) { //k lies on the same place as a pivot 
      return points_ptr[pivot_idx]; 
    } else if (k < pivot_idx) { //k lies on the left of the pivot 
      //points_ptr remains the same 
      points_size = pivot_idx; 
      //k remains the same 
    } else { //k lies on the right of the pivot 
      points_ptr += pivot_idx + 1; 
      points_size -= pivot_idx + 1; 
      k -= pivot_idx + 1; 
    } 

    return qselect(points_ptr, points_size, k); 
} 

その後、私はglibcののqsort()と比較してみましたO(nlog(n))となり、その優れた性能に驚いた。

double wtime; 
wtime = 0.0; 
for (size_t i = 0; i < 1000; ++i) { 
    qsort(points_ptr, points_size, sizeof (*points_ptr), compar_rand); 
    wtime -= omp_get_wtime(); 
    qsort(points_ptr, points_size, sizeof (*points_ptr), compar_distance); 
    wtime += omp_get_wtime(); 
} 
printf("qsort took %f\n", wtime); 

wtime = 0.0; 
for (size_t i = 0; i < 1000; ++i) { 
    qsort(points_ptr, points_size, sizeof (*points_ptr), compar_rand); 
    wtime -= omp_get_wtime(); 
    qselect(points_ptr, points_size, points_size/2); 
    wtime += omp_get_wtime(); 
} 
printf("qselect took %f\n", wtime); 

10000個の素子のアレイのためのqsort took 0.280432、qselect took 8.516676と同様の結果を有する：ここで、測定コードです。クイックソートがquickselectより速いのはなぜですか？

Answer 1

あなたの提案に感謝します。私のquickselectの実装に関する問題は、私のケースでは、inputs that contain many repeated elementsの最悪ケースの複雑度O(n^2)を示しています。 Glibcのqsort()（これはデフォルトでmergesortを使用しています）はここにO(n^2)を表示しません。

私は基本的な3ウェイ分割および中央値の-3 quickselectのためにうまく動作を実行するために私partition()機能を変更しました：

/** \breif Quicksort's partition procedure.         
*                   
* In linear time, partition a list into three parts: less than, greater than 
* and equals to the pivot, for example input 3 2 7 4 5 1 4 1 will be   
* partitioned into 3 2 1 1 | 5 7 | 4 4 4 where 4 is the pivot.    
* Modified version of the median-of-three strategy is implemented, it ends with 
* a median at the end of an array (this saves us one or two swaps).   
*/                   
static void partition(struct point **points_ptr, size_t points_size, 
         size_t *less_size, size_t *equal_size) 
{                    
    /* Modified median-of-three and pivot selection. */      
    struct point **first_ptr = points_ptr;         
    struct point **middle_ptr = points_ptr + (points_size/2);    
    struct point **last_ptr = points_ptr + (points_size - 1);     
    if ((*first_ptr)->distance > (*last_ptr)->distance) {      
     SWAP(*first_ptr, *last_ptr, struct point *);       
    }                   
    if ((*first_ptr)->distance > (*middle_ptr)->distance) {     
     SWAP(*first_ptr, *middle_ptr, struct point *);      
    }                   
    if ((*last_ptr)->distance > (*middle_ptr)->distance) { //reversed   
     SWAP(*last_ptr, *middle_ptr, struct point *);       
    }                   
    const double pivot_value = (*last_ptr)->distance;      

    /* Element swapping. */             
    size_t greater_idx = 0;             
    size_t equal_idx = points_size - 1;          
    size_t i = 0;                
    while (i < equal_idx) {             
     const double elem_value = points_ptr[i]->distance;     

     if (elem_value < pivot_value) {          
      SWAP(points_ptr[greater_idx], points_ptr[i], struct point *);  
      greater_idx++;             
      i++;                
     } else if (elem_value == pivot_value) {        
      equal_idx--;              
      SWAP(points_ptr[i], points_ptr[equal_idx], struct point *);  
     } else { //elem_value > pivot_value         
      i++;                
     }                  
    }                   

    *less_size = greater_idx;             
    *equal_size = points_size - equal_idx;         
} 

/** A selection algorithm to find the kth smallest element in an unordered list. 
*/                   
static struct point * qselect(struct point **points_ptr, size_t points_size, 
           size_t k) 
{                    
    size_t less_size;               
    size_t equal_size;              

    partition(points_ptr, points_size, &less_size, &equal_size);    

    if (k < less_size) { //k lies in the less-than-pivot partition   
     points_size = less_size;            
    } else if (k < less_size + equal_size) { //k lies in the equals-to-pivot partition 
     return points_ptr[points_size - 1];         
    } else { //k lies in the greater-than-pivot partition      
     points_ptr += less_size;            
     points_size -= less_size + equal_size;        
     k -= less_size + equal_size;           
    }                   

    return qselect(points_ptr, points_size, k);        
} 

結果は確かに（私が使用している線形およびqsort()よりも優れています@IVladとしてフィッシャーイエーツshuffleが示唆されているので、絶対qsort()回は）悪い：

array size qsort  qselect speedup 
1000  0.044678 0.008671 5.152328 
5000  0.248413 0.045899 5.412160 
10000  0.551095 0.096064 5.736730 
20000  1.134857 0.191933 5.912773 
30000  2.169177 0.278726 7.782467 

Answer 2

最初の明らかな答えは、qsortがquicksortを実装していない可能性があります。 標準を読んでからしばらく時間がかかりましたが、qsort（）がクイックソートを実行することが必要なことはありません。

2番目：既存のC標準ライブラリは、多くの場合、（たとえば、特別なアセンブリ命令を使用している場合など）頻繁に最適化されています。現代のCPUの複雑なパフォーマンス特性と組み合わせると、O（n log n）アルゴリズムにつながる可能性があります。クイックソートではありません。アルゴリズムはO（n）アルゴリズムより高速です。

私の推測では、あなたがキャッシュを台無しにしていると思います。これは、valgrind/cachegrindがあなたに伝えることができるものです。