Algorithmus implementieren, jedoch viel zu ineffizient

Hi, danke für deine Antwort, also die lookup sieht so aus:

int Schedule::lookup(int trainId, int stationId, int param) {
      Entry item(trainId, stationId, param);
      vector<Entry>::iterator it = find(allEntries.begin(), allEntries.end(), item);
      if (it != allEntries.end()){
        Entry e = *it;
        return (param == 0) ? e.getArrival() : e.getDeparture();
      }
      else
        return -1;
    }

Bis das Programm fertig ist, dauert es ca 4-5 Minuten. Beim Compiler hab ich gar nichts eingestellt, nehme g++

Der hastebin Server sollte wieder funktionieren.

Wie genau meinst du das mit dem Rausziehen?

temi

rac44 schrieb:

Wie genau meinst du das mit dem Rausziehen?

Wenn du z.B. innerhalb der Schleife "c" bist ändert sich ja "a" nicht mehr, du solltest also den Wert für a bereits vor der Schleife einer Variablen zuweisen, damit du dir die ständigen Aufrufe ersparst, die immer zum selben Ergebnis führen.

for(int a = 0; a < trains.length(); a++){

    int idA = trains.give(a).getId(); // nur noch ein Aufruf!

    for(int c = 0; c < stations.length(); c++){
        int departureA = schedule.lookup( idA, stations.give(c).getId(), 1);
        // ...

Ahja gute Idee

Ich denke auch std::find ist nicht gerade der effizienteste Suchalgorithmus, jemand eine Idee wie ich das optimieren könnte?

Th69

Du könntest ein

std::set<Entry>

benutzen (anstatt dem vector<>). Zugriff darauf ist dann O(log(N)) anstatt O(N).

Und stell beim Compiler mal "-O2" (s.a. gcc: Options That Control Optimization) als zusätzlichen Parameter ein (und natürlich einen Release-Build) und miß dann mal die Zeit.

PS: Ich sehe gerade, daß du die "allEntries" ja schon sortiert hast, dann könntest du auch die binäre Suche verwenden (es gab gerade erst einen Beitrag dazu: binary_search mit unterschiedlichem Vergleich als Sortierung).

Was ist denn?

std::std<Entry>

Meinst du vielleicht set? Da ist mein Problem, dass ich keinen eindeutigen Schlüssel habe (sortiert nach TrainIds).

Vielleicht würde es gehen mit zwei Schlüsseln (TrainId und StationId).
Hab grad binary_search implementiert und es ist schon wesentlich schneller, bin bei ca. 5-7 Sekunden, ich denke das ist schon ganz okay.

Glaubst du wird es noch (bemerkbar) schneller, wenn ichs mit nem set machen würde, geht das überhaupt mit mehreren Keys??

Wow -O2 und das Ding braucht nicht mal mehr ne halbe Sekunde!!!
Danke

temi

rac44 schrieb:

Glaubst du wird es noch (bemerkbar) schneller, wenn ichs mit nem set machen würde, geht das überhaupt mit mehreren Keys??

Keine Ahnung. Wie wäre es mit map<key, value>?

Ich denke ich bin zufrieden so.
Vielen Dank für deine Hilfe!!

Th69

Ich wollte auch erst std::map<> schreiben, habe dann aber im Source-Code gesehen, daß die Klasse Entry den == und < Operator schon implementiert hat und habe daher std::set vorgeschlagen (ist quasi äquivalent zu einer sortierten Liste und binärer Suche).

Glückwunsch zu deiner Optimierung

Edit: Habe den Fehler bzgl. std::std => std::set oben korrigiert...

Skym0sh0

racc44 schrieb:

Wow -O2 und das Ding braucht nicht mal mehr ne halbe Sekunde!!!
Danke

Im Extremfall könntest du auch mit Parallelität draufhauen, aber dann werden Antworten zu dem Thema ganz schnell non-trivial.

Finnegan

racc44 schrieb:

Wow -O2 und das Ding braucht nicht mal mehr ne halbe Sekunde!!!
Danke

Ach echt? Das hat bei dir schon gereicht?
Und ich dachte mir gestern Abend noch dass mir das zu mühsam ist und ich zu wenig über die verwendeten Datenstrukturen weiss, um den Algo in eine andere Komplexitätsklasse zu bekommen.
Manchmal denkt man zu kompliziert - bin wohl noch zu sehr von diversen Algorithmenbau-Veranstaltungen im Studium geschädigt

temi

Kurze Frage von mir:

Der enorme Zeitgewinn ist doch jetzt nur aufgrund von Optimierungen seitens des Compilers zustande gekommen, oder?

Das bedeutet doch letztendlich, dass am Algorithmus eigentlich gar nichts optimiert wurde und es hier möglicherweise noch viel Potential durch geeignetere Datenstrukturen, Suchalgorithmen, usw. geben könnte?

Belli

rac44 schrieb:

Hab grad binary_search implementiert und es ist schon wesentlich schneller, bin bei ca. 5-7 Sekunden, ich denke das ist schon ganz okay.

Th69

racc44 hat ja meine Vorschlag mit der binären Suche (anstatt linearem 'find') übernommen (und dann eben noch zusätzlich die Compileroptimierung aktiviert).