performance frage

kantaki

Hallo,

mein programm liest aus einer txt datei jede zeile und speichert es in einem vector<string>.

das mache ich mit getline.

die txt datei hat 567 zeilen.

jede zeile im vector muss mit jeder zeile im vector verglichen werden.
das sind insgesammt also 321489 vergleiche.
Und jeder string wird nochmal aufgesplitet um die werte in double zu speichern.

aufsplitten tue ich die werde mit istringstream.
und ich konvertiere string zu double mit stringstream.

nach jedem durchgang wird ein ergenis per fstream in einen .ini datei geschrieben.

mein computer braucht für diese berechnungen 5sec, was mir sehr lange vorkommt.
Was meint ihr dazu ?

pumuckl

Klingt ziemlich umständlich. Was steht in den Zeilen genau drin, und warum musst du jede Zeile mit jeder anderen vergleichen? Was versuchst du damit zu erreichen?

kantaki

ich habe coordinaten in der txt datei zb

2478.87, 1685.28, 100.98
2311.78, 1090.25, 103.67
2603.79, 863.24, 177.17
2884.61, 1002.98, 179.92
2902.17, 380.93, 110.89

diese werden in dem vector gespeichert, dann aufgesplittet in zb

xwert = 2478.87
ywert = 1685.28
zwert = 100.98

ich möchte ein navigationssystem erstellen. dann wird nach einer koordinate gesucht die den kürzesten weg zum zielpunkt und den kürzesten weg von der momentanen position besitzt.

cooky451

Wenn es auf Geschwindigkeit ankommt, würde ich zum Einlesen ifstream.read() + strtod() empfehlen, siehe auch:
http://www.c-plusplus.net/forum/286372

Edit:
Wobei es bei den paar Zeilen vermutlich an den Vergleichen hängt. Da müsstest du etwas genauer deinen Algorithmus beschreiben. (Oder irgendeinen Artikel verlinken, falls der bekannt ist.)

kantaki

http://img638.imageshack.us/img638/5426/appwb.jpg

die schwarzen punkte sind die Koordinaten auf denen ich mich bewegen will
start und ziel sind die anfangs und end Koordinaten.

gehen wir vom start aus.

mein programm schaut nun welcher wegpunkt die kürzeste distanz von
start zu wegpunkt + wegpunkt bis ende hat. Dann schaut es welche wegpunkte der nächstliegende ist.
meine formel ist sqrt(dx^2+dy2+dz^2) welche die distanz berechnet.
das mache ich mit

// Distance from Start
            lengthBeginX = abs(startX-fwpx);
            lengthBeginY = abs(startY-fwpy);
            lengthBeginZ = abs(startZ-fwpz);

            lengthStart= sqrt((pow(lengthBeginX,2))+(pow(lengthBeginY,2))+(pow(lengthBeginZ,2)));
            // Distance to End

            lengthEndX = abs(endX-fwpx);
            lengthEndY = abs(endY-fwpy);
            lengthEndZ = abs(endZ-fwpz);

            lengthEnd= sqrt((pow(lengthEndX,2))+(pow(lengthEndY,2))+(pow(lengthEndZ,2)));

            distanceSumTemp=lengthStart+lengthEnd;
            shortestWayTemp=lengthStart;

            if(distanceSumTemp<distanceSum && lengthStart!=0 )
            {

                if(shortestWayTemp<shortestWay)
                {
                    wpSave=index;
                    distanceSum = distanceSumTemp;
                    shortestWay=shortestWayTemp;
                }

            }

Du könntest schon mal ein paar Vergleiche eliminieren, bei den 321489 (entspricht 567*567) vergleichst du Zeilen doppelt, also z.B 1. und 2. Zeile und dann später nochmal 2. mit 1. Zeile, wenn du das weglässt sind es nur noch ungefähr 161000 Vergleiche

Gruss

kantaki

was ich noch vergessen habe

ich lösche den benutzten wegpunkt aus dem vector mit

svec.erase (svec.begin()+wpSave);

CatDog11 schrieb:

Du könntest schon mal ein paar Vergleiche eliminieren, bei den 321489 (entspricht 567*567) vergleichst du Zeilen doppelt, also z.B 1. und 2. Zeile und dann später nochmal 2. mit 1. Zeile, wenn du das weglässt sind es nur noch ungefähr 161000 Vergleiche

Gruss

stimmt daran habe ich noch garnicht gedacht.
danke

*grübel*

pumuckl

Verwandle zuerst die Zeilen in double-Triplets, danach vergleichst du. Geht viel schneller als string-Vergleiche. Und natürlich kannst du dann anhand der einzelnen Koordinaten schon Vorauswahlen treffen, welche der Punkte überhaupt in Frage kommen. Dadurch sparst du dir dann eine Menge Vergleiche.

kantaki

pumuckl schrieb:

Verwandle zuerst die Zeilen in double-Triplets, danach vergleichst du. Geht viel schneller als string-Vergleiche. Und natürlich kannst du dann anhand der einzelnen Koordinaten schon Vorauswahlen treffen, welche der Punkte überhaupt in Frage kommen. Dadurch sparst du dir dann eine Menge Vergleiche.

ja sowas ähnliches hatte ich am anfang auch
zb wenn ich die differenz von start und ende nehme, das nur wegpunkte ausgesucht werden die in dieser range liegen.
das problem ist das ich auch umwege gehen muss, die straßen sind ja nicht alle gerade =).
naja ich muss wohl noch ein wenig grübeln.

brotbernd

Ich hab jetzt die Regel nicht wirklich verstanden (die kürzeste Distanz ist doch einfach Start mit Endpunkt verbunden ..?), aber scheinbar spielt der nächstgelegende Wegpunkt immer eine Rolle. Um sowas zu beschleunigen kannst du deinen Raum in kleinere Unterräume unterteilen, so dass Du viele Wegpunkte von vornerein ausschließen kannst. Im einfachsten Fall, legst du einfach ein gleichmäßiges Gitter über deinen Raum und sortierst deine Wegpunkte da ein. Wenn das mnoch nicht reicht gibt es eine ganze Reihe bekannter Strukturen (http://en.wikipedia.org/wiki/Space_partitioning#Types_of_space_partitioning_data_structures)

cooky451

Ohne ernsthaft Ahnung davon zu haben, würde ich sagen, die Aufgabe ist nicht sinnvoll, solange man keine definierten Verbindungen zwischen den Koordinaten hat. Denn so gilt:

brotbernd schrieb:

die kürzeste Distanz ist doch einfach Start mit Endpunkt verbunden ..?

kantaki

okay beispiel

ich stehe vor einem berg. natürlich ohne tunnel....
und mein ziel liegt hinter dem berg.

der kürzeste weg ist natürlich start-end aber dann würde mich mein navi direkt durch den berg leiten

so leitet mich mein navi um den berg herum, anhand meiner aufgenommenen kooridnaten.

Ist aber immer noch Käse. Berg ist schön, aber Bäume kennt der immer noch nicht. Was, wenn zwischen deinen Koordinaten plötzlich ein Baum wächst? Musst du dann deine Koordinaten anpassen?
Was du eigentlich willst, wäre deine Punkte in Listen zu speichern, jede Liste markiert einen Weg. Da nicht jeder Punkt mit einem Nachbarpunkt wirklich eine Teilstrecke eines Weges markiert, musst du wohl schon beim SPeichern der Daten deine Wege berücksichtigen. Eine (bessere) Alternative wäre, wenn für jeden Punkt die direkt erreichbaren Punkte (weg-Knick, Kreuzung, ...) abgespeichert würden.

kantaki

ich möchte das als app fürs handy benutzen, da ich gerne fahrrad fahre habe ich die koordianten natürlich nur auf befahrbaren wegen aufgenommen. und falls ein baum kommt muss ich nicht unbedingt dagegen fahren

brotbernd

Du hast da wohl trotzdem einen Denkfehler. Du bewegst Dich auf Wegen, nicht von Punkt zu Punkt. Die Frage lautet "Über welche Wege ist die Strecke A nach B am kürzesten". Wenn Du einfach sagst, dass zwischen jedem Punkt ein Weg liegt der einfach die Luftlinie lang ist, dann ist der kürzeste Weg einfach der Weg von A direkt nach B, das hatten wir schon.
Der Witz am Navi ist ja, dass Du nicht nicht einfach überall bewegen kannst. Du musst also erstmal auf deiner Karte (http://img638.imageshack.us/img638/5426/appwb.jpg) noch Wege einzeichnen und deren Länge bestimmen.

krümelkacker

Was Du da hast, ist ein Haufen von "Knoten" (mit Koordinaten). Wegsuchealgorithmen wollen mehr als das. Neben einem Haufen von Knoten, wollen sie auch wissen, welche Verbindungen es zwischen den Knoten gibt ("Kanten"). Das zusammen dennt man das dann "Graph".

Bei den Graphen für Routenplaner sind "Knoten" Kreuzungen (oder zumindest Punkte auf der Karte) und "Kanten" die Straßen, die die Punkte direkt verbinden.

Die Koordinaten der Knoten kann zusätzlich nutzen, um den Mindestabstand zwischen aktueller Position und Ziel abzuschätzen (Luftlinie). Sowas nennt man dann "informierte Suche". Bekannter Algorithmus dafür: A*.

Wenn ich das jetzt richtig verstanden habe, müsstest du doch zu jeder Koordinate Infos speichern, welche anderen Koordinaten ohne Probleme direkt zu erreichen sind, und dann wird das Ganze zu einem Problem ähnlich des "Handelsreisenden"(Traveling Salesman Problem)

Gruss

pumuckl

CatDog11 schrieb:

Wenn ich das jetzt richtig verstanden habe, müsstest du doch zu jeder Koordinate Infos speichern, welche anderen Koordinaten ohne Probleme direkt zu erreichen sind, und dann wird das Ganze zu einem Problem ähnlich des "Handelsreisenden"(Traveling Salesman Problem)

Hast du offenbar nicht richtig verstanden. Er will nur von A nach B kommen, nicht N Punkte erreichen.

kantaki

okay ich hatte sowieso einen logik fehler in meinem code =(.

jetzt filtere ich die 10 nächsten wegpunkte in einen anderen vector und lass die kürzeste distanz zum endpunkt errechnen.

funktionieren tut es relativ gut nur es braucht leider noch länger =(.

hat jemand vielleicht optimierungsvorschläge?

for (vector<string>::size_type index = 0; index!=svec.size(); ++index)
        {

            int max = 0; 

            if(tenwps.size()< 10)
            {
                tenwps.push_back(svec[index]);
            }

            if(tenwps.size()==10)
            {

                for(vector<string>::size_type st = 0; st!=tenwps.size(); ++st)
                {
                    //some code

                    if(lengthStart>max)
                    {
                        max=lengthStart;
                        stsave=st;
                    }

                }
                //////////ERASE LONGEST WP/////////
                tenwps.erase(tenwps.begin()+stsave);

cooky451

kantaki schrieb:

hat jemand vielleicht optimierungsvorschläge?

Du musst dich immer noch auf Straßen fortbewegen! (Jede Kreuzung ist dann ein Punkt.)

kantaki

cooky451 schrieb:

kantaki schrieb:

hat jemand vielleicht optimierungsvorschläge?

Du musst dich immer noch auf Straßen fortbewegen! (Jede Kreuzung ist dann ein Punkt.)

nein, jede koordinate liegt auf einem weg.
das einzige problem ist das es nicht den kürzesten weg nimmt, sondern immer nur den zielwegpunkt mit der luftdistanz zum ziel berechnet.
Naja zumindest kommt man zum Ziel.
aber die berechnung dauert schon sehr sehr lange

gibt es vielleicht eine alternative zum vector?