テール再帰のないクイックソート

Question

私はテール再帰を使用して次のランダム化クイックソートコードを書いています。私は末尾再帰を使用しないという効果を見たいと思っていましたし、実行時間と実行時間がどのように影響を受けているのかを見たいと思っていました。下のランダム化クイックソートコードから末尾再帰を削除するにはどうすればよいですか？

#include<iostream> 
#include<cstdlib> 
using namespace std; 

int partition(int low,int high,int a[]) 
{ 
    int index=(rand()%(high-low))+low; 
    //cout<<endl<<index<<"----"<<endl; 
    int temp1=a[index]; 
    a[index]=a[low]; 
    a[low]=temp1; 
    int left,right,pivot_item=a[low]; 
    left=low; 
    right=high; 

    while(left<right) 
    { 
     while(a[left]<=pivot_item) 
      left++; 
     while(a[right]>pivot_item) 
      right--; 
     if(left<right) 
     { 
      int temp=a[right]; 
      a[right]=a[left]; 
      a[left]=temp; 
     } 
    } 
    a[low]=a[right]; 
    a[right]=pivot_item; 
    return right; 
} 

void quicksort(int low,int high,int a[]) 
{ 
    int pivot; 
    if(low<high) 
    { 
     pivot=partition(low,high,a); 
     quicksort(low,pivot-1,a); 
     quicksort(pivot+1,high,a); 
    } 
} 

int main() 
{ 
    srand(time(NULL)); 
    int n; 
    n=50; 
    int a[n]; 
    int i; 
    for(i=0;i<n;i++) 
     a[i]=(rand()%(1000-1)); 

    quicksort(0,n-1,a); 
    cout<<endl; 

    for(i=0;i<n;i++) 
     cout<<a[i]<<endl; 
    return 0; 
} 

EDIT： 全くquicksort機能における第二の再帰呼び出しを削除する方法はあります。これは末尾再帰を取り除くことを意味し、時間にも大きな影響を与えます。

Answer 1

通常、コンパイラには特定の最適化を有効または無効にするオプションがあります。

g ++および関連するコンパイラの場合、-foptimize-sibling-calls and -fno-optimize-sibling-callsオプションを使用してテールコールの最適化を有効または無効にすることができます。別のコンパイラを使用する場合は、マニュアルを参照してください。

同じアルゴリズムを使用できるため、これらを使用して末尾再帰の効果を比較することをお勧めします。

---

それは非テールrecuriveにするために単純ではないので、クイックソートは、自然に末尾再帰です。 1つの手、それは簡単です：単に再帰呼び出しの後に何かをします。 Voilà、アルゴリズムはもはやテール再帰的ではありません。しかし、再帰後に行うことは重要です。それは副作用を持っていなければなりません、そうでなければ最適化することができます。しかしそれはパフォーマンスに影響し、テールコール最適化の効果だけを測定することはもうありません。

ここにアイデアがあります。

void quicksort1(int low,int high,int a[]) 
{ 
    int pivot; 
    if(low<high) 
    { 
     pivot=partition(low,high,a); 
     quicksort1(low,pivot-1,a); 
     quicksort2(pivot+1,high,a); 
    } 
} 

void quicksort2(int low,int high,int a[]) 
{ 
    int pivot; 
    if(low<high) 
    { 
     pivot=partition(low,high,a); 
     quicksort2(low,pivot-1,a); 
     quicksort1(pivot+1,high,a); 
    } 
} 

それは相互再帰関数に末尾呼び出しの最適化を行うことは可能ですので、私は賢いコンパイラが把握しないという保証するものではありません。自分自身は末尾呼び出しであれば代わりにお互いを呼ぶ二つの同一の機能を実装します何が起こっているのか。しかし、最適化は実装が難しくなるため、コンパイラによってはそれを行おうとしないかもしれません。確認したい場合はアセンブリをチェックしてください。また、これは命令キャッシュに何らかの影響を与える可能性があるため、テールコールの最適化を無効にする以外のパフォーマンスに影響を与える可能性があります。

Answer 2

テール再帰を簡単に削除するには、再帰呼び出しを行った後に関数内で何か他の処理を行う方法があります。以下では、voidではなく値を返すように関数を変更し、再帰呼び出しが終了した後に何かを返すreturn文を追加しました。これはパフォーマンスの影響を最小限に抑える必要があります。

int quicksort(int low,int high,int a[]) 
{ 
    int pivot; 
    if(low<high) 
    { 
     pivot=partition(low,high,a); 
     quicksort(low,pivot-1,a); 
     quicksort(pivot+1,high,a); 
    } 
    return 0; 
}