"Brute Force Algorithmus" - geht das noch schneller?

[otze]

Kóyaánasqatsi schrieb:

Brute Force-Algorithmen lässt man heutzutage über die GPU (Grafikkarten"prozessor") laufen.

In dieser Pauschalität ist das, wie immer, falsch.

Topic: mir ist nicht ganz klar, was die Funktion machen soll.

[redrew99]

Ich bin Matrix... schrieb:

aber mich würde mal interessieren, wie man das noch schneller hinbekommt bzw. wie man sowas heutzutage mit C++ löst. Keine Angst, hab nicht vor irgendwen zu hacken, dazu is mein PC viel zu schwach
Danke Schonmal

Die meisten Rechner haben ja mehrere CPUs heutzutage. Deren zusätzliche Benutzung
könnte die Berechnung schneller machen.
Stichwort dafür ist: Threads.

[drakon]

redrew99 schrieb:

Ich bin Matrix... schrieb:

aber mich würde mal interessieren, wie man das noch schneller hinbekommt bzw. wie man sowas heutzutage mit C++ löst. Keine Angst, hab nicht vor irgendwen zu hacken, dazu is mein PC viel zu schwach
Danke Schonmal

Die meisten Rechner haben ja mehrere CPUs heutzutage. Deren zusätzliche Benutzung
könnte die Berechnung schneller machen.
Stichwort dafür ist: Threads.

Ich würde nicht direkt auf Threads aufsetzen, sondern eine Bibliothek nutzen, die dir hilft. So Zeugs lässt sich z.B. Prima mit Intel TBB parallelisieren.

[Kóyaánasqatsi]

otze schrieb:

Kóyaánasqatsi schrieb:

Brute Force-Algorithmen lässt man heutzutage über die GPU (Grafikkarten"prozessor") laufen.

In dieser Pauschalität ist das, wie immer, falsch.

Warum sollte es falsch sein?

[otze]

Kóyaánasqatsi schrieb:

Warum sollte es falsch sein?

Schonmal Programme auf einer Grafikkarte implementiert?

[Ich bin Matrix...]

Danke euch allen erstmal für die Antworten.

-lass das "inline" weg. Dein compiler igoniert dich sowieso.

Ich weiß, war auch eher zum Spaß

-Warum das Ganze rekursiv aufziehen? Bei der iterativen Variante sparst du dir die Funktionsaufrufe und du musst keine Angst haben, irgendwann aus dem Stack zu fallen

Versteh ich nicht ganz, denn das einzige, was in meinem Beispiel rekursiv ist ist die "Erhöhung" des strings. Hättest du einen kurzen Codeschnipsel als Denkanstoß? Muss nicht lauffähig sein, Pseudocode tätes auch. Danke

Topic: mir ist nicht ganz klar, was die Funktion machen soll.

Ist doch eig. selbsterklärend. pw() legt einen neuen string an und füllt ihn mit dem Startzeichen und "Erhöht" ihn dann solange um "1", bis es wieder beim Startstring angekommen ist, dann wird das ganze bis zur maximalen Wortlänge wiederholt.

[Sone]

Ich bin Matrix... schrieb:

Versteh ich nicht ganz, denn das einzige, was in meinem Beispiel rekursiv ist ist die "Erhöhung" des strings.

inline bool inc(std::string& str, int curpos, char begin, char end) 
{ 
    if (str[curpos] == end) 
    { 
        str[curpos] = begin; 
        if (curpos == 0) 
            return false; 

        return inc(str, curpos-1, begin, end);//Hier fängt die Rekursion an
    } 
    else 
        ++str[curpos]; 
    return true; 
}

[ipsec]

Die Rekursionstiefe ist hier maximal curpos, d.h. maximal die Länge des Strings. Ich denke bei den Eingabegrößen, bei denen Brute Force noch einigermaßen anwendbar ist, sollte der Stack gerade noch reichen.

[yihaaa]

Einfach mal so eine idee mit dem Stack, die Parameter werden ja auch drauf abgelegt. Man könnte ja eine struct machen, dann spart man schon mal eine Menge. Noch besser wäre natürlich, wenn man das ganze im Sinne von __fastcall, also die Parameter gerade in die Register laden würde. Dann bleibt nur noch die Returnadresse vom Call auf dem Stack liegen.

MfG

[knivil]

1.) Also hier werden einem Anfaenger Threads und OpenCl empfohlen ... das ist keine Hilfe, sondern nur rumposen.
2.) Sieht die Funktion sehr endrekursiv aus, dein Kompiler sollte die Rekursion wegoptimieren.

Lerne also erstmal weiter C++ bevor du anfaengst rumzufuschen!