Hypercell ein ] Hypercell aus ] Zeige Navigation ] Verstecke Navigation ]
c++.net  
   

Die mobilen Seiten von c++.net:
https://m.c-plusplus.net

  
C++ Forum :: C++ (alle ISO-Standards) ::  Algorithmus implementieren, jedoch viel zu ineffizient  
Gehen Sie zu Seite 1, 2  Weiter
  Zeige alle Beiträge auf einer Seite
Auf Beitrag antworten
Autor Nachricht
racc44
Unregistrierter




Beitrag racc44 Unregistrierter 00:08:38 07.01.2017   Titel:   Algorithmus implementieren, jedoch viel zu ineffizient            Zitieren

Hallo, ich habe eine Aufgabe bekommen inkl. Implementierunsvorschlag:
Zitat:
Finde alle Züge, die einen anderen Zug überholen und gib deren Zugnummern aus.

Implementierunsvorschlag:

Code:
    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
C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
   #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.
bahnfahrer
Unregistrierter




Beitrag bahnfahrer Unregistrierter 00:24:45 07.01.2017   Titel:              Zitieren

Schade, dass du die *.dat-Dateien nicht zur Verfügung stellst.
Was aber sofort ins Auge springt ist
C++:
Train give(int index) { return trains[index]; }

Warum nicht
C++:
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...
racc44
Unregistrierter




Beitrag racc44 Unregistrierter 00:29:25 07.01.2017   Titel:              Zitieren

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.
Th69
Mitglied

Benutzerprofil
Anmeldungsdatum: 25.03.2008
Beiträge: 4393
Beitrag Th69 Mitglied 11:42:41 07.01.2017   Titel:              Zitieren

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.
C++:
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, ...)?
rac44
Unregistrierter




Beitrag rac44 Unregistrierter 12:32:20 07.01.2017   Titel:              Zitieren

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

C++:
1
2
3
4
5
6
7
8
9
10
    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
Mitglied

Benutzerprofil
Anmeldungsdatum: 04.11.2016
Beiträge: 179
Beitrag temi Mitglied 13:30:10 07.01.2017   Titel:              Zitieren

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.

C++:
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);
        // ...

_________________
C++ Anfänger und Spaßprogrammierer. Bisher mit C# unter Windows programmiert und jetzt unter Linux mit Qt Creator als IDE.


Zuletzt bearbeitet von temi am 13:34:53 07.01.2017, insgesamt 4-mal bearbeitet
rac44
Unregistrierter




Beitrag rac44 Unregistrierter 14:20:00 07.01.2017   Titel:              Zitieren

Ahja gute Idee :D

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

Benutzerprofil
Anmeldungsdatum: 25.03.2008
Beiträge: 4393
Beitrag Th69 Mitglied 14:54:03 07.01.2017   Titel:              Zitieren

Du könntest ein
C++:
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).


Zuletzt bearbeitet von Th69 am 17:07:59 07.01.2017, insgesamt 4-mal bearbeitet
rac44
Unregistrierter




Beitrag rac44 Unregistrierter 15:49:50 07.01.2017   Titel:              Zitieren

Was ist denn?
C++:
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??
racc44
Unregistrierter




Beitrag racc44 Unregistrierter 16:04:38 07.01.2017   Titel:              Zitieren

Wow -O2 und das Ding braucht nicht mal mehr ne halbe Sekunde!!!
Danke :)
C++ Forum :: C++ (alle ISO-Standards) ::  Algorithmus implementieren, jedoch viel zu ineffizient  
Gehen Sie zu Seite 1, 2  Weiter
Auf Beitrag antworten

Zeige alle Beiträge auf einer Seite




Nächstes Thema anzeigen
Vorheriges Thema anzeigen
Sie können Beiträge in dieses Forum schreiben.
Sie können auf Beiträge in diesem Forum antworten.
Sie können Ihre Beiträge in diesem Forum nicht bearbeiten.
Sie können Ihre Beiträge in diesem Forum nicht löschen.
Sie können an Umfragen in diesem Forum nicht mitmachen.

Powered by phpBB © 2001, 2002 phpBB Group :: FI Theme

c++.net ist Teilnehmer des Partnerprogramms von Amazon Europe S.à.r.l. und Partner des Werbeprogramms, das zur Bereitstellung eines Mediums für Websites konzipiert wurde, mittels dessen durch die Platzierung von Werbeanzeigen und Links zu amazon.de Werbekostenerstattung verdient werden kann.

Die Vervielfältigung der auf den Seiten www.c-plusplus.de, www.c-plusplus.info und www.c-plusplus.net enthaltenen Informationen ohne eine schriftliche Genehmigung des Seitenbetreibers ist untersagt (vgl. §4 Urheberrechtsgesetz). Die Nutzung und Änderung der vorgestellten Strukturen und Verfahren in privaten und kommerziellen Softwareanwendungen ist ausdrücklich erlaubt, soweit keine Rechte Dritter verletzt werden. Der Seitenbetreiber übernimmt keine Gewähr für die Funktion einzelner Beiträge oder Programmfragmente, insbesondere übernimmt er keine Haftung für eventuelle aus dem Gebrauch entstehenden Folgeschäden.