performance frage

kantaki

Sabrina S. schrieb:

kantaki schrieb:

Das kann garnicht passieren. völlig unmöglich. warum ? ich nehme wegpunkte zb alle 10 m auf warum sollte sich der abstand vergrößern wenn ich berg auf oder ab gehe?
meine formel beinhaltet x y und Z.

Die 10m kamen erst nach meinem Post, vorher hieß es nur "ich fahre Rad, dabei werden Punkte aufgezeichnet". Ich ging von einer Timergesteuerten Aufzeichnung aus (ist mMn. leichter), dabei liegen die Punkte bei schnellerer Fahrt weiter auseinander als Punkte bei langsamerer Fahrt.
Und wenn du weißt, dass du exakt alle 10m einen Messpunkt hast, warum vergleichst du mit allen Punkten?
Und was ist, wenn du 10m vor einer exakten 60°-Kehre bist? Dann ist von dir aus die Kurve und der nächste Messpunkt nach der Kurve exakt 10m weit weg. Die Logik weiß ja nicht, ob der übersprungene Kurvenpunkt jetzt zum Weg gehört - es ist ja ein anderer Punkt ebenfalls 10m weit weg, und der Weg zum Ziel wird dadurch kürzer.

Langer Rede kurzer Sinn: Bevor du deine Wege ausgeben kannst, musst du festlegen, welche Punkte man tatsächlich zu einem Weg verbinden kann. In einer Punktwolke können alle möglichen Punkte einen möglichen Weg bilden. Das wollen wir dir seit >3 Seiten sagen.

das mache ich weil wenn ich auf einer kreuzung stehe muss ich zb zwichen 4-5 wegpunkten entscheiden. dabei kann natürlich der abstand varieren.

in einer Punktwolke können alle möglichen Punkte einen möglichen Weg bilden. Das wollen wir dir seit >3 Seiten sagen.

deswegen habe ich auch gefragt ob es eine alternative zum vector gibt, da ich beim vector jeden einzelnen wert erstmal ausgeben muss, und da ich ziemlich viele vergleiche anstellen muss, dauert es natürlich auch länger.
eine distanz von ca 50km dauert 4-5sec mit meiner berechnung.
es wäre natürlich ein vorteil wenn ich im vorhinein wüsste welche wegpunkte überhaupt in frage kommen, aber daran hänge ich noch

So langsam wird es ja etwas klarer was Du da machst (verstehe nicht wieso Du nicht von Anfang an sagst was Du machst. Wie soll man das mit diesem Bild http://img638.imageshack.us/img638/5426/appwb.jpg erraten. Hellsehen kann hier keiner).
Ich denke Hauptaufgabe ist für Dich aus deinen Punkten Straßen zu bilden. Das ist an vielen Stellen einfach, etwas kniffeliger wird es an Knicken und Kreuzungen. Wenn Du das hast, hast Du Kreuzungen=Knoten und Straßen=Kanten und bewegst dich dann auf bekanntem Gebiet der Graphen. Den Graphen kannst du dann abspeichern und musst nicht jedes mal von vorne deine Straßen suchen.

genau so mache ich das ich lasse die wegpunkte die ich nehmen soll im vorhinein berechnen, speichere die in eine .ini datei und kann diese dann einfach auf eine karte einzeichnen.

brotbernd

kantaki schrieb:

genau so mache ich das ich lasse die wegpunkte die ich nehmen soll im vorhinein berechnen, speichere die in eine .ini datei und kann diese dann einfach auf eine karte einzeichnen.

Nein, Du machst mit Sicherheit nicht das was da steht. Hast Du überhaupt gelesen was da steht? Der Vorschlag war deine Wegpunkte in einen Graphen mit Knoten und Kanten zu überführen, diesen zu speichern und deine blöden Wegpunkte wegzuschmeißen. Dein Programm arbeitet dann mit dem Graphen und nicht mehr mit Punkten. Der Graph wird dann nur aktualisiert, wenn Du neue Punkte aufgenommen hast.

kantaki

brotbernd schrieb:

kantaki schrieb:

genau so mache ich das ich lasse die wegpunkte die ich nehmen soll im vorhinein berechnen, speichere die in eine .ini datei und kann diese dann einfach auf eine karte einzeichnen.

Nein, Du machst mit Sicherheit nicht das was da steht. Hast Du überhaupt gelesen was da steht? Der Vorschlag war deine Wegpunkte in einen Graphen mit Knoten und Kanten zu überführen, diesen zu speichern und deine blöden Wegpunkte wegzuschmeißen. Dein Programm arbeitet dann mit dem Graphen und nicht mehr mit Punkten. Der Graph wird dann nur aktualisiert, wenn Du neue Punkte aufgenommen hast.

okay tut mir leid, hab ich wohl falsch interpretiert.

kannst du mir erklären was ein "Graph mit Knoten und Kanten" ist?

SeppJ

kantaki schrieb:

kannst du mir erklären was ein "Graph mit Knoten und Kanten" ist?

Das versucht dir hier ein jeder im Thread seit 4 Seiten zu erklären! Wie möchtest du noch jemanden motivieren, das noch einmal zu tun, wenn du bisher nur den Eindruck erweckst, dass man gegen eine Wand anschreibt.

Das Stichwort lässt sich aber auch hervorragend googlen.

krümelkacker

Um auf Dein Problem zurück zu kommen:

(1) Bau Dir irgendwie einen Graphen.
(2) Nimm einen altbekannten Wegsuchealgorithmus, wie z.B. den A-Stern.

Aber: Das ist eher ein Programmier-Problem als ein Problem mit der Sprache C++.

Zum Implementieren der Graph-Datenstruktur empfehle ich Dir std::list als Knoten-Container. Das praktische dabei ist, dass Zeiger auf Knoten solange gültig bleiben, bis der Knoten aus der Liste wieder gelöscht wird. Wird die Liste zerstört, werden auch automatisch die gespeicherten Knoten zerstört. Um böse Überraschungen mit den Zeigern zu vermeiden, kannst Du das Kopieren der Datenstruktur unterbinden. Mal ein einfaches Beispiel ohne großartige Kapselung:

Pseudo-Code:

struct vec3d {
  double coeffs[3];
};

struct knoten {
  vec3d position;
  vector<knoten*> direkte_nachbarn;
};

struct graph {
  list<knoten> alle_knoten;

  knoten* knoten_hinzufuegen(vec3d c) {
    knoten temp = {c};
    alle_knoten.push_back(temp);
    return &alle_knoten.back();
  }

private:
  // Kopieren und Zuweisen ausschalten...
  graph(graph const&);            // bleibt absichtlich undefiniert
  graph& operator=(graph const&); // bleibt absichtlich undefiniert
};

oder so ähnlich.

Wenn Du nach 4 Seiten immer noch nicht weißt, was ein Graph ist, frag nochmal in "Rund um die Programmierung" zu dem Thema. Das hat wirklich nix mit C++ zu tun.

Eisflamme

Ich hab jetzt irgendwann aufgehört zu lesen, weil zwei Seiten vergeblich versucht wurde zu erklären, was das Problem an OPs Ansatz ist.

Nur ganz kurz. Falls das hier deine Punktewolke ist (Wege sind eingezeichnet, aber die hast du ja nicht): http://www.leda-tutorial.org/de/offiziell/Pictures/DFS_NUMDemoGraphWin.png

Dann würde dein Algo von 1|14 zu 15|18 ja als kürzesten Weg angeben, dass er über 19|19 geht. Aber wie man sieht, gibt es dort gar keine Verbindung (Fluss dazwischen).

kantaki

okay super vielen danke

ich weiß zwar noch nicht was struct oder list ist, aber das lässt sich ja einfach googlen.
ich lese nur gerade primer und bin noch nicht sehr weit (s.300).
aber ich wollte einfach mal was programmieren, und ich muss sagen obwhol es sehr unneffizient ist, bin ich trotzdem stolz das ich es geschafft habe.

naja ich werde mich jetzt mal in das obrige programm einlesen

vielen dank

Eisflamme

Juchu, endlich Mal jemand, der zum Einstieg ein vernünftiges Buch liest.

kantaki

okay ich habe mich in ein paar algorithmen eingelesen.
leider muss ich feststellen das mein grundwissen doch noch sehr viele lücken aufweist
Ich werde wohl erstmal bei meiner momentanen Version bleiben.

Allerdings lasse ich nun die string koordinaten sofort in ein struct speichern und diesen struct speichere ich in einen vector. Das hat mir einen enormen perfomance vorteil verschafft =).
Danke schonmal dafür.

Ein Problem habe ich leider noch und ich kann den fehler nicht finden.
Wenn die Distanz zu groß ist werden garbage werte ausgegeben(immer der selbe wert)

Würde vielleicht jemand über den Code drüber schauen und mir ein paar tipps geben?

Leider ist der Code 250Zeilen groß und ich möchte ungern das forum vollspamen.
Dafür ist er gut Kommentiert
Also wenn sich jemand bereiterklären würde, wäre ich sehr dankbar.
bzw wenn sich jemand findet, dann würde ich ihn auch hier posten, wenn das in ordnung wäre.

314159265358979

Kommentare sind übrigens üblicherweise ein Zeichen von schlechtem Code.

kantaki

314159265358979 schrieb:

Kommentare sind übrigens üblicherweise ein Zeichen von schlechtem Code.

weil der code kommentare braucht um verständlich zu sein ?

314159265358979

Richtig

Bashar

314159265358979 schrieb:

Kommentare sind übrigens üblicherweise ein Zeichen von schlechtem Code.

Lösung: Kommentare entfernen.

314159265358979

Bashar schrieb:

314159265358979 schrieb:

Kommentare sind übrigens üblicherweise ein Zeichen von schlechtem Code.

Lösung: Kommentare entfernen.

otze

314159265358979 schrieb:

Kommentare sind übrigens üblicherweise ein Zeichen von schlechtem Code.

Das stimmt nicht. Kommentare sind üblicherweise ein zeichen für Code, der mehr macht als simple GUI-Boilerplate Logik. Wenn du einen Algorithmus implementierst, dann gibt es oftmals teile, die zwar im originalpaper hergeleitet wurden, aber die Herleitung hat keine Intuition die stark genug ist, dass sprechende Variablennamen alleine den Code beschreiben können.

314159265358979

In seiner Größenordnung stimmt das normalerweise

volkard

otze schrieb:

314159265358979 schrieb:

Kommentare sind übrigens üblicherweise ein Zeichen von schlechtem Code.

Das stimmt nicht.

Das stimmt aber auch nicht.

otze schrieb:

Kommentare sind üblicherweise ein zeichen für Code, der mehr macht als simple GUI-Boilerplate Logik. Wenn du einen Algorithmus implementierst, dann gibt es oftmals teile, die zwar im originalpaper hergeleitet wurden, aber die Herleitung hat keine Intuition die stark genug ist, dass sprechende Variablennamen alleine den Code beschreiben können.

Das wäre der Idealfall. Ich beneide Dich um die Arbeitskollegen, die das auch so handhaben.

In der Welt passiert aber leider sowas:
http://stackoverflow.com/questions/3198615/wrote-a-quick-and-dirty-brainfuck-interpreter-what-could-i-do-better

Auf den ersten Eindruck erscheint es wie ein bestens kommentiertes Programm; es kann sogar Profis beeindrucken, wie hübsch es doch sei. Und zu sowas führt es, wenn man Anfänger zwingt, viele Kommentare zu schreiben. In Wirklichkeit ist es schlechtestens kommentiert. Die ganzen einfachen Sachen sind kommentiert, sodaß man alles doppelt liest, aber der elegante Trick, wie '[' und ']' zusammenarbeiten, ist kein Bißchen kommentiert^(*). Da stottert man beim Lesen. Und zwar nicht umsonst: Der Code ist falsch.

Ich halte es so, daß ich dermaßen ausgewalzte Kommentare ein Zeichen von Unverständnis und Praxisferne halte, ein fettes Warnblinklicht, das mir sagt, ich hätte mich da nicht einmischen sollen, dann hätte ich den Code jetzt auch nicht lesen müssen.

Vielleicht wäre es gut, die Anfänger nicht mehr zum Kommentieren anzuhalten. Und die Profis sollten vor jede Klasse schreiben (können), warum sie diese Klasse einführen. Das wäre schön. Ach, was würden viele RessourcenManager und curiously recurring templates sterben. Nee, das klappt nie:

class RessourcenManager{
//Diese Klasse managt Ressourcen, ist doch kla, du. 
...//weiter wie gehabt, oder noch schlimmer

^(*) Man erkennt nur am ?:-Operator, daß der Schreiber sich dort viele Gedanken gemacht hat und ein Profi ist.^