std::function<> in rekursiver Funktion



  • In einer Vorlesungsübgung ging es darum Quicksort mit zwei verschiedenen Partitionierungsalgorithmen zu implementieren.

    Schlau wie ich bin dachte ich mir, dass ich den verwendeten Algorithmus als std::function<> Objekt übergebe, um ihn schnell austauschen zu können.

    Die Funktion sah dann so aus

    void quicksort(std::vector<int>&A, int p, int r, std::function<int(std::vector<int>&, int,int)>partitionFunc) {
    	if(p<r){
    		int q = partitionFunc(A, p, r);
    		quicksort(A, p, q - 1,partitionFunc );
    		quicksort(A, q + 1, r,partitionFunc );
    	}
    
    }
    

    Und der initiale Aufruf so

    quicksort(vec, 0, vec.size() - 1, std::bind(partition, vec, 0, vec.size()-1));
    

    Ich fürte das auf einem zu sortierenden Vector aus und es knallte auf dem Stack, da dieser voll lief.
    Wenn ich das Ganze "klassisch", mit fest einprogrammiertem Partitionsalgorithmus, ausführe läuft alles sauber durch. Deswegen nehme ich an das meine Abbruchbedingungen der Rekursion passen.
    Somit lässt sich das Problem auf die Verwendung der Funktionsobjekte zurückfürhen.
    Jetzt meine Frage, habe ich dort in der Anwendung etwas falsch gemacht oder ist std::function<> für den Einsatz bei Rekursionen gänzlich Ungeeignet?



  • Spricht in der Form aus meiner Sicht nix dagegen.

    Zumal deine std::function in dem Fall quasi nur eine Hilfsfunktion ist und gar nicht mal die "rekursierende Funktion".



  • Gerade in einer Sortierfunktion, wo es ja auch Geschwindigkeit ankommt, wäre zu überlegen, ob du statt einer std::function nicht ein Template nehmen solltest und statt bind ein Lambda (probiere das mal aus mit angeschalteten Optimierungen!), um den Overhead der std::function zu vermeiden.

    Die Partitionierungsfunktion allgemein sollte doch den Container nicht ändern (+const) und eher size_t statt int zurückgeben. Alternativ könntest du auch mit Iteratoren arbeiten (It partitionFunc(It it1, It it2)).



  • @It0101 sagte in std::function<> in rekursiver Funktion:

    Zumal deine std::function in dem Fall quasi nur eine Hilfsfunktion ist und gar nicht mal die "rekursierende Funktion".

    Dennoch stört sie irgendwie die Rekursion, denn wenn ich mir die Funktinsaufrufe anzeigen lasse wird dort x-mal std::function<> aufgerufen, bis der Aufrufstack voll läuft und das Programm mit einem Stack-Overflow abbricht.

    @wob sagte in std::function<> in rekursiver Funktion:

    Die Partitionierungsfunktion allgemein sollte doch den Container nicht ändern (+const)

    Da die Partitionierungsfunktion vom Prof. als Pseudocode vorgegben ist habe ich diese verwendet, in diesen wird die eigentliche Sortierarbeit gemacht durch das Vertauschen von Elementen, deswegen kein const

    Anbei mal der vollstänige Code zum ausprobieren, evtl. fällt ja dann das Problem auf.

    #include <iostream>
    #include <vector>
    #include <functional>
    
    
    int partition(std::vector<int>&A, int p, int r) {
    	int x = A.at(r);
    	int i = p - 1;
    	for (int j = p; j <= r - 1; j++) {
    		if (A.at(j) <= x) {
    			i++;
    			std::swap(A.at(i), A.at(j));
    		}
    	}
    	std::swap(A.at(i + 1), A.at(r));
    	return i + 1;
    }
    
    int Hoare_Partition(std::vector<int>&A, int p, int r) {
    	int x = A.at(p);
    	int i = p - 1;
    	int j = r + 1;
    	while (true)
    	{
    		do {
    			j--;
    		} while (A.at(j) > x);
    		
    		do {
    			i++;
    		} while (A.at(i) < x);
    
    		if (i < j) {
    			std::swap(A.at(i), A.at(j));
    		}
    		else {
    			return j;
    		}
    	}
    }
    
    void quicksort(std::vector<int>A, int p, int r, std::function<int(std::vector<int>&,int,int)>partitionFunc) {
    	if(p<r){
    		int q = partitionFunc(A, p, r);
    		quicksort(A, p, q - 1, partitionFunc);
    		quicksort(A, q + 1, r, partitionFunc);
    	}
    
    }
    
    
    int main() {
    	std::vector<int>vec{ 13,19,9,5,12,8,7,4,11,2,6,21 };
    
    	quicksort(vec, 0, vec.size() - 1, std::bind(partition, vec,0,vec.size()-1));
    
    	for (int a : vec) {
    		std::cout << a << ",";
    	}
    	return 0;
    }
    


  • @axels sagte in std::function<> in rekursiver Funktion:

    [...] bis der Aufrufstack voll läuft [...]

    void quicksort(std::vector<int>A, // ...
    

    Hör auf die Daten durch die Gegend zu kopieren.



  • @axels sagte in std::function<> in rekursiver Funktion:

    std::bind(partition, vec, 0, vec.size()-1)

    Das sieht merkwürdig aus.

    Generell: verwende Lambda, nicht std::bind.



  • quicksort(vec, 0, vec.size() - 1, partition );

    Damit läuft es.
    Ob das Ergebnis stimmt?

    13,19,9,5,12,8,7,4,11,2,6,21,



  • Mit Lambda statt std::bind funktioniert alles so wie es soll.

    Kann mir jemand erklären warum std::bind solche Probleme verursacht, bzw. hab ich es bloß falsch verwendet?



  • @axels sagte in std::function<> in rekursiver Funktion:

    Kann mir jemand erklären warum std::bind solche Probleme verursacht, bzw. hab ich es bloß falsch verwendet?

    Du verwendest keine Platzhalter. bind ruft partition immer mit den Werten vec, 0, vec.size()-1 auf. Die aktuellen Parameter verschwinden im Nirwana.

    Du solltest bind vergessen. Es wird nicht mehr gebraucht!



  • @wob sagte in std::function<> in rekursiver Funktion:

    Gerade in einer Sortierfunktion, wo es ja auch Geschwindigkeit ankommt, wäre zu überlegen, ob du statt einer std::function nicht ein Template nehmen solltest und statt bind ein Lambda (probiere das mal aus mit angeschalteten Optimierungen!), um den Overhead der std::function zu vermeiden.

    Die Partitionierungsfunktion allgemein sollte doch den Container nicht ändern (+const) und eher size_t statt int zurückgeben. Alternativ könntest du auch mit Iteratoren arbeiten (It partitionFunc(It it1, It it2)).

    Interessanter Punkt. Die Performancefrage hab ich mir auch gestellt. Lässt sich der Overhead von std::function z.B. im Vergleich zu Lambdas irgendwie beziffern?



  • @It0101 Naja, sizeof(function)=32 bei mir. Und durch Type Erasure gibt es eine Indirektion pro Call. Zumindest sofern da der Optimierer nicht sehen kann, dass das hier nicht nötig ist. Ob/ab welcher Größe das messbar ist? Keine Ahnung. Ausprobieren und messen!

    Zum const: ich hatte aus irgendwelchen unerfindlichen Gründen an eine Funktion gedacht, die mir das Pivot-Element heraussucht. Wenn man partitioniert, ist das in der Tat Blödsinn. Wahrscheinlich weil ich dachte, dass die Wahl des Pivots das ist, was hier durchgetestet werden soll.



  • @It0101 sagte in std::function<> in rekursiver Funktion:

    Lässt sich der Overhead von std::function z.B. im Vergleich zu Lambdas irgendwie beziffern?

    Bei std::function hast du zusätzlich zu dem was du darin aufrufst einen indirekten oder virtuellen Funktionsaufruf (je nach Implementierung). Das kostet dich so um die 20~60 Zyklen + die Kosten für die Parameterübergabe.

    Lambdas können dagegen oft inlined werden, die Kosten für den Funktionsaufruf fallen also gänzlich weg. Plus der Compiler kann die aufrufende und die aufgerufene Funktion zusammen optimieren. Weiters müssen Parameter nicht in speziellen Registern bzw. speziellen Positionen am Stack übergeben werden. Die Kosten die bereits in Registern/am Stack vorhandenen Werte umzuschaufeln um sie übergeben zu können entfallen also auch. Insgesamt kann das einiges ausmachen.

    Wenn ein Lambda nicht inlined werden kann ist der Unterschied weniger dramatisch, aber vermutlich immer um >= 10 Zyklen schneller.

    Das sind grobe Richtwerte anhand von http://ithare.com/infographics-operation-costs-in-cpu-clock-cycles/

    Wenn du's genau wissen willst mach das was @wob vorgeschlagen hat: probier es aus 🙂


Anmelden zum Antworten