Optimierungen von Funktionen

Hi,
ich programmiere erst seit kurzem intensiver in C++. Deswegen habe ich auch noch kaum Ahnung, wie man schnellen und effektiven Code schreibt. Ich habe drei Funktionen geschrieben, die leider kriechend lahm sind. Es wäre wirklich schön, wenn sie sich jemand anschauen und mir Optimierungsvorschläge geben könnte:

// Eine Hilfsfunktion, die einen String um r Einheiten nach rechts verschiebt
string shiftstring(const string text, long r) {
    string nstring;
    long c,len = text.length();
    for (long i = 0 ; i < len ; ++i) {
        c = i + r;
        if (i + r > len-1) c = c - len;
        nstring += text[c];
    }

    return nstring;
}

// Verarbeitet einen String nach dem BWT Algo
// Knackpunkte sind das Erstellen der Rotationen sowie das Sortieren des String-Arrays
string comp_bwt(const string text) {

    // Alle Rotationen erstellen
    string rows[text.length()];
    long len = text.length()-1;
    string bwt;
    for (long i=0 ; i<=len ; ++i) {
        rows[i] = shiftstring(text, i);
    }

    // Reihen sortieren
    quicksortstr(0, len, rows);

    // Letzte Spalte ist gesuchter String
    for (long i=0; i<=len ; ++i) {
        bwt += rows[i][len];
    }

    return bwt;
}

Nun folgt mein modifizierter QuickSort Algorithmus für Strings, der wirklich sehr langsam zu sein scheint. Zum einen funktioniert bei mir die Funktion strcmp bei dem String-Array nicht, deswegen musste ich mir dafür ebenfalls eine bestimmt langsame Hilfsfunktion schreiben. Zum anderen habe ich diesen Algo direkt von Int zu String umgeschrieben - vielleicht gibt es auch bessere, und vor allem schnellere Methoden:

void quicksortstr( long l, long r, string *field ) {
    if( l < r ) {
        //Privotelement aussuchen
        string pivot = field[ (long)((l+r) >> 1) ] ;

        long i = l-1 ; 
        long j = r+1 ; 

        while( 1 ) {
            //Solange Element kleiner als Pivot Element
            do { i++; } while( strcmp2(field[i], pivot) < 0 ) ; 
            do { j--; } while( strcmp2(field[j], pivot) > 0 ) ;

            //Vertausche linkes Feld mit rechten, wenn i < j 
            if( i < j ) {    
                string tmp  = field[i] ; 
                field[i] = field[j] ; 
                field[j] = tmp ;   
            } else {
                //Unterteile Feld in zwei 2 Teilfelder
                quicksortstr( l, j, field ) ; 
                quicksortstr( j+1, r, field ) ; 
                break ; 
            }
        }
    }
    return ;
}

Ich weiß, es ist viel Code, aber er lässt sich mit einem erfahrenen Auge bestimmt noch stark komprimieren.

Vielen Dank schonmal im Voraus
Gruß,
Neo

ness

sieh dir mal folgendes an: std::rotate, refernzen, std::swap.

Hi,
1. Also wenn swap wirklich schneller ist als die drei Zeilen werde ich die Stelle austauschen.

2. std::rotate kriege ich leider nicht zum laufen. Könnte es evtl. daran liegen, dass das String in sich ja ein Char-Array ist, und ich somit ein zweidimensionales Array rotieren lassen muss? Hier der Code:

for (long i=0 ; i<=len ; ++i) {
        rows[i] = text;
        std::rotate(rows[i], rows[i,i], rows[i,len]);
    }

Am Ende sollen im String Array "rows" alle möglichen Rotationen von "text" gespeichert sein.

3. Referenzen kenne ich zumindest in der Theorie etwas. Nur inwiefern sollen sie mir bei der Codeoptimierung helfen? Ich wäre dir sehr dankbar, wenn du das etwas spezifizieren könntest.

Inzwischen habe ich eine erstaunlich einfache Möglichkeit gefunden, den String Quicksort Algo zu optimieren: Anstatt strcmp oder meiner strcmp2 Funktion verwende ich einfach einen direkten Vergleich:

field[i] < pivot

Ich dachte eigentlich, Strings kann man nicht auf diese Art vergleichen. Aber anscheinend funktioniert es doch.

Nun ist nur noch das Herausfinden aller Rotationen des Strings ein Problem.
Wäre nett, wenn mir jemand ein Beispiel der std::rotate Funktion anhand des String-Arrays(!) zeigen könnte, falls diese wirklich so schnell ist.

Greetz,
Neo

Lesco

NeoInferno schrieb:

3. Referenzen kenne ich zumindest in der Theorie etwas. Nur inwiefern sollen sie mir bei der Codeoptimierung helfen? Ich wäre dir sehr dankbar, wenn du das etwas spezifizieren könntest.

einer funktion eine referenz zu übergeben ist fast immer schneller als wenn du den wert übergibst

Ach so ist das gemeint, danke.

Übrigens habe ich zum Rotieren einen sehr schnellen Ansatz gefunden, ich muss nur noch herauskriegen, wie ich ihn implementiere:
Einfach den neuen String aus zwei Teilstrings des alten zusammensetzen, und zwar per

text.substr(pos,len)

Wenn jemand eine Idee hat, wie man daraus in etwa soetwas machen kann, her damit

// r ist der Verschiebungswert
nstring = text.substr(len-r, r ) + text.substr(r+1, len-r);

Gruß,
Neo

Walli

NeoInferno schrieb:

1. Also wenn swap wirklich schneller ist als die drei Zeilen werde ich die Stelle austauschen.

Schneller wird es wohl nicht unbedingt sein. Aber schöner ist es allemal .

@Walli:
Beim Sortieren geht es nicht um Ästhetik, sondern um Speed

Ich habe inzwischen die Lösung für eine funktionierende Rotationsfunktion selbst gefunden:

// len = text.length() und r ist die Verschiebung
nstring = text.substr(len-r, r ) + text.substr(0, len-r);

Wer noch mehr Optimierungen findet, bitte posten

Walli

NeoInferno schrieb:

@Walli:
Beim Sortieren geht es nicht um Ästhetik, sondern um Speed

std::swap ist aber auch nicht langsamer als ein manueller Dreieckstausch.

operator void

Sondern unglaublich viel schneller, weil es std::string::swap aufruft.