Algorithmus implementieren, jedoch viel zu ineffizient



  • Hallo, ich habe eine Aufgabe bekommen inkl. Implementierunsvorschlag:

    Finde alle Züge, die einen anderen Zug überholen und gib deren Zugnummern aus.

    Implementierunsvorschlag:

    for all trains B
            for all trains A
                find station C, where A departs and B later departs than A (the earliest one)
                    if there is such one
                        for all stations D, where A stops after C and B also stops
                            if B stops at D earlier than A, then B is a overtaker!
    

    Ich hab mir jeweils Klassen gebaut für die Züge, Bahnhöfe und Einträge für den Fahrplan, ich lese von drei verschiedenen Files ein und es wird pro Zeile ein Objekt erstellt und diese wiederum in eigene "TrainList" (bzw. "StationList",...) eingefügt, diese benutzen intern einen Vektor.

    Also meine Implementierung funktioniert, allerdings ist sie sehr, sehr langsam. Kein Wunder, eine 4-fach verschachtelte for-Schleife ist nicht gerade das Gelbe vom Ei.

    Habt ihr vielleicht eine Idee, wie man den vorgegeben Algorithmus wesentlich effizienter implementieren könnte? Ich freue mich über jeden Vorschlag!

    main.cc

    #include <iostream>
        #include <fstream>
        #include "station.h"
        #include "train.h"
        #include "schedule.h"
    
        using namespace std;
    
        int main(int argc, char *argv[]) {
    
          StationList stations = StationList("stations.dat");
          TrainList trains = TrainList("trains.dat");
          Schedule schedule = Schedule("schedule.dat");
    
          for(int b = 0; b < trains.length(); b++){
            for(int a = 0; a < trains.length(); a++){
              for(int c = 0; c < stations.length(); c++){
                int departureA = schedule.lookup(trains.give(a).getId(), stations.give(c).getId(), 1);
                int departureB = schedule.lookup(trains.give(b).getId(), stations.give(c).getId(), 1);
    
                if(departureA == -1 || departureB == -1)
                  continue;
    
                if(departureA < departureB){
                  for(int d = 0; d < trains.length(); d++){
                    int arrivalA = schedule.lookup(trains.give(a).getId(), stations.give(d).getId(), 0);
                    int arrivalB = schedule.lookup(trains.give(b).getId(), stations.give(d).getId(), 0);
    
                    if(arrivalA == -1 || arrivalB == -1)
                      continue;
    
                    if(arrivalA > departureA && arrivalB > departureB && arrivalB < arrivalA){
                      cout << "FOUND" << endl;
                      break;
                    }
                  }
                }
              }
            }
          }   
        }
    

    Die restlichen C++ Dateien (Code) wären hier: https://hastebin.com/ubexokuyan.cpp
    Hauptsächlich geht es jedoch um die Implementierung des Algorithmus in der main.



  • Schade, dass du die *.dat-Dateien nicht zur Verfügung stellst.
    Was aber sofort ins Auge springt ist

    Train give(int index) { return trains[index]; }
    

    Warum nicht

    const Train& give(int index) { return trains[index]; }
    

    ?
    Beim Algo selber wird es vermutlich noch sehr viele gute Optimierungen geben.
    Vielleicht stelltst du ja die drei Dateien noch online...



  • Hallo, danke für deine Antwort, die *.dat Dateien sehen so aus:
    schedule.dat, stations.dat, trains.dat

    Danke, das mit den References hab ich auch schon geändert, aber der Hauptalgorithmus ist irgendwie problematisch.



  • Welche Optimierungsoption hast du denn beim Compiler eingestellt?
    Und wie lange dauert der Algo jetzt dafür (also für die 144 Trains)?

    Was mir auf jeden Fall auffällt, daß du einige Variablen aus der Schleife rausziehen solltest, z.B.

    int idA = trains.give(a).getId();
    int idB = trains.give(b).getId();
    

    Leider kann ich auf deinen Source nicht zugreifen ("Web server is returning an unknown error"), aber die Hauptfunktion ist ja "schedule.lookup" - wie hast du diese implementiert (lineare Suche, konstant, ...)?



  • 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?



  • 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?



  • 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 🙂



  • 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!!



  • 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...



  • 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.



  • 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 😉



  • 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?



  • 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.



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


Anmelden zum Antworten