Quicksort ohne Schwanz Rekursion

Question

Ich habe den folgenden randomisierten Quicksort-Code mit Tail-Rekursion geschrieben. Ich wollte den Effekt sehen, keine Tail-Rekursion zu verwenden und wollte sehen, wie die Ausführungszeit und die Laufzeit beeinflusst werden. Wie können wir die Schwanzrekursion aus dem folgenden randomisierten Quicksort-Code entfernen?

#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: Gibt es eine Möglichkeit, den zweiten rekursive Aufruf in der quicksort Funktion sogar komplett zu löschen. Dies würde das Entfernen der Schwanzrekursion bedeuten und würde auch die Zeit signifikant beeinflussen.

Answer 1

Compiler haben in der Regel eine Option zum Aktivieren und Deaktivieren bestimmter Optimierungen.

Im Fall von g ++ und verwandten Compilern können Sie die Tail Call-Optimierung mit den Optionen -foptimize-sibling-calls and -fno-optimize-sibling-calls aktivieren und deaktivieren. Wenn Sie einen anderen Compiler verwenden, lesen Sie das Handbuch.

Ich würde empfehlen, diese zu verwenden, um den Effekt der Schwanzrekursion zu vergleichen, weil es Ihnen erlaubt, denselben Algorithmus zu verwenden.

---

Quicksort ist natürlich tail rekursiv, es ist also nicht einfach, nicht-tail-recurve zu machen. Auf der einen Seite ist es einfach: Mach einfach etwas nach dem Rekursionsaufruf. Voilà, der Algorithmus ist nun nicht mehr tail rekursiv. Aber was Sie nach der Rekursion tun, ist wichtig. Es muss einen Nebeneffekt haben, sonst kann es weg optimiert werden. Aber dann würde es die Leistung beeinträchtigen und Sie messen nicht mehr nur den Effekt der Tail-Call-Optimierung.

Hier ist eine Idee. Implementieren Sie zwei identische Funktionen, die sie statt, wenn ich in dem Schwanz Anruf nennen:

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); 
    } 
} 

Es ist immer noch möglich Endaufruf Optimierung auf beiden Seiten rekursiven Funktionen zu tun, so dass ich nicht garantieren, dass ein Smart-Compiler nicht Figur was los ist. Die Optimierung wird jedoch schwieriger zu implementieren sein, sodass einige Compiler dies möglicherweise nicht versuchen. Überprüfen Sie die Baugruppe, wenn Sie sicher sein wollen. Dies kann sich auch auf den Anweisungscache auswirken, was sich auf die Leistung auswirken kann, und nicht nur die Optimierung des Tail-Aufrufs deaktiviert.

Answer 2

Eine einfache Möglichkeit, die Tail-Rekursion zu entfernen, besteht darin, nach dem rekursiven Aufruf etwas anderes in der Funktion auszuführen. Unten habe ich die Funktion geändert, um einen Wert anstelle von void zurückzugeben, und eine return-Anweisung hinzugefügt, um etwas zurückzugeben, nachdem der rekursive Aufruf beendet wurde. Dies sollte minimale Auswirkungen auf die Leistung haben.

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; 
}