Anzeige-Problem (Herunterskalierung)

[lundefugl]

Hallo Christian,

Der significantPositionCache cacht für einen Zoomlevel, welche Positionen der Douglas-Peucker-Algorithmus als signifikant erreichnet habt. Der Cache wird gelöscht, wenn eine Position bewegt wird oder sich ändert oder die gesamte Positionsliste sich ändert.

Ein Löschen des Caches "bezahle" ich auf meinem System mit 25 Sekunden Wartezeit für Deine Dateien mit 600000 Positionen. Wie lange dauern die Schritte unten bei Dir und auf wieviele Positionen reduziert der von Dir optimierte Algorithmus pro Schritt?

Aufgrund der Mail noch eine Erklärung zu meinem Ansatz.
Das Problem beim Originalalgorithmus ist bei mir, dass aufgrund der Originalkurve optimiert wird. Zoomt man hinein, so bleiben an einigen Stellen zu wenige Punkte im Anzeigebereich übrig.
Mein Ansatz ist nun, dass zuerst die Abschnitte der Kurve bestimmt werden, die wirklich im Anzeigebereich sind. Danach werden die Abschnitte einzeln optimiert. Hier macht der Cache dann probleme, da der Douglas-Peucker-Algorithmus mit verschiedenen Kurven aufgerufen wird.
Erst am Ende werden die Segmente dann zu einer Kurve kombiniert.

Der worst case für meinen Algorithmus ist die Gesamtansicht der Kurve, da hier genausoviel übrig bleibt und man sich den Segmentbestimmungsschritt hätte sparen könnte. Umso weiter man hineinzoomt, desto weniger bleibt bei mir übrig und es geht schneller.

Die Zeiten bei mir sind für die Gesamtkurve ca. 3 Sekunden. Vielleicht kann man ja beide Varianten im Code halten, die man über eine Option umschaltbar macht ? Evtl. sollte man auf meine Variante auch erst ab einem bestimmten Zoomlevel gehen.

Code:

INFO: base position list size: 596039
09.09.2012 17:49:32 slash.navigation.converter.gui.mapview.BaseMapView logJavaScript
INFO: script 'return getNorthEastBounds();'
with result '72.193605,61.710604'
09.09.2012 17:49:32 slash.navigation.converter.gui.mapview.BaseMapView logJavaScript
INFO: script 'return getSouthWestBounds();'
with result '44.680463,-26.180021'
09.09.2012 17:49:33 slash.navigation.converter.gui.mapview.BaseMapView filterVisiblePositionsExt
INFO: Reduced 596039 positions to 1 segments / 596039 positions in 252 milliseconds
09.09.2012 17:49:33 slash.navigation.converter.gui.mapview.BaseMapView filterEveryNthPosition
INFO: Filtered every 11,920780th position to reduce 596039 positions to 50000 in 5 milliseconds
09.09.2012 17:49:34 slash.navigation.converter.gui.mapview.BaseMapView calculateSignificantPositionsForZoom
INFO: zoom 5 < 16: threshold 5000.0, significant positions 305, calculated in 1652 milliseconds
09.09.2012 17:49:34 slash.navigation.converter.gui.mapview.BaseMapView filterSignificantPositions
INFO: Filtered significant positions to reduce 50000 positions to 305 in 1656 milliseconds
09.09.2012 17:49:34 slash.navigation.converter.gui.mapview.BaseMapView logJavaScript

Gruß
Thomas

[routeconverter]

Mein Ansatz ist nun, dass zuerst die Abschnitte der Kurve bestimmt werden, die wirklich im Anzeigebereich sind. Danach werden die Abschnitte einzeln optimiert.

Die Idee finde ich gut.

Wäre es nicht sinnvoller, die Abschnitte, die im Anzeigebereich liegen, weniger stark zu optimieren, als die, die außerhalb liegen? Also meinen Code, der ganz brutal/global nur jede N. Position übernimmt zu ersetzen durch

• Douglas Peucker für alle Positionen im Anzeigebereich
  
• für alle Positionen außerhalb des Anzeigebereiches: nur jede N. Position dann Douglas Peucker?
  

Der worst case für meinen Algorithmus ist die Gesamtansicht der Kurve, da hier genausoviel übrig bleibt und man sich den Segmentbestimmungsschritt hätte sparen könnte. Umso weiter man hineinzoomt, desto weniger bleibt bei mir übrig und es geht schneller.

Wie gesagt: Diese Idee finde ich gut.

Die Zeiten bei mir sind für die Gesamtkurve ca. 3 Sekunden.

Douglas Peucker läuft auf Deinem Prozessor in 1,6 Sekunden, der kann das also 15x schneller als meiner. Ich habe hier einen Intel i5 M460 mit 2,53 GHz, Dual-Core mit HT, Windows-Leistungsindex 6,6 - was läuft bei Dir?

Vielleicht kann man ja beide Varianten im Code halten, die man über eine Option umschaltbar macht ? Evtl. sollte man auf meine Variante auch erst ab einem bestimmten Zoomlevel gehen.

Ich bin ja ein Fan von: es funktioniert einfach.

Ich habe jetzt begonnen, Codeteile aus Deinem zweiten Pullrequest, die ich verstanden habe, zu übernehmen. Nach welchem Schema bestimmst Du die Segmente? Die Idee kann ich aus dem Code nicht herauslesen.

[routeconverter]

Wenn Du magst, würde ich gerne mal telefonieren oder skypen - das könnte den Austausch der Ideen deutlich einfacher machen. Schreib mir dann einfach eine Idee für Kontaktdetails.

[routeconverter]

Ich habe gerade etwas anderes Interessantes herausgefunden: die Aktualisierung des Höhenprofils braucht unheimlich viel Zeit, da stets für alle Positionen alle Einträge aktualisiert werden. Erstmal werden lauter Tooltip-Texte gerendert, dann das Profil selbst gemalt. Bei Veränderungen an Dateien mit 600000 Positionen braucht das locker 20 Sekunden... :-(

[lundefugl]

Hallo Christian,

mein Gesamt-Leistungsindex von 5.9 ist nicht so aussagekräftig, da die Systemfestplatte nicht die Schnellste ist.
Für den Anwendungsfall sollten folgende Faktoren relevant sein:
Prozessor: 7.7
RAM (16 GB): 7.8
Grafik: 7.9

Was mir noch eingefallen ist: Hast Du mal probiert deiner Java-VM noch etwas mehr Speicher zu geben, als du es schon gemacht hast ?
In der Firma kenn ich solche Effekte, dass die Java-VM plötzlich extrem langsam wird, wenn sie im oberen Speicherlimit arbeitet. Dann muss der Garbage Collector einfach zu oft anlaufen und das bremst enorm.

Falls du das bei dir nicht machen kannst, dann teile mir doch deinen Speicherwert mit und ich probier es hier aus. Evtl. wird dann auch meine Zeit deutlich schlechter.

Nochmal zum Ansatz von mir. Die Bestimmung der Abschnitte erfolgt in "filterVisiblePositionsExt" eigentlich identisch zur "filterVisiblePositions". Unterschied ist nur, dass sobald eine zweite Positionen ausserhalb des Anzeigebereiches entdeckt wird ein neuer Abschnitt begonnen wird und dieser erst die letzte Position ausserhalb des Anzeigebereiches bekommt, wenn ein Punkt im Anzeigebereich liegt.
Alles was davor ausserhalb des Anzeigebereiches liegt wird komplett weggeworfen. Dadurch bleiben nur die Abschnitte übrig, die wirklich im Anzeigebereich liegen.

Ansonsten können wir gern auch mal telefonieren. Skypen geht bei mir mangels Skype-Account und Hardware (man bräuchte wohl ein Micro ;-) nicht.


Gruß
Thomas

[lundefugl]

Hallo Christian,

Ich habe gerade etwas anderes Interessantes herausgefunden: die Aktualisierung des Höhenprofils braucht unheimlich viel Zeit, ...

ohne mir den Code angeschaut zu haben, mal eine verrückte Idee dazu. Sofern das nicht ständig im Swing-Thread gemacht werden muss, könnte man das und die Aktualisierungen ggf. in einen Single-Thread-Executor auslagern, der das im Hintergrund macht. Den könnte man dann auch notfalls mit etwas geringer Prio laufen lassen. Ich vermute mal, dass die Schnelligkeit bei der Aktualisierung der Grafik für die meisten Anwender eine eher untergeordnete Prio hat.

Ich hab übrigens mal ausprobiert in GpxPosition das origin-Feld null zu lassen. Ich hab zwar hier keinen Profiler, aber laut TaskManager hat das nur ca. 100 MB nach dem Laden eingespart. Im Vergleich zum Gesamtspeicherverbrauch von 2 GB wäre das wohl wirklich eher zu vernachlässigen.

Gruß
Thomas

P.S.: Falls Du noch bedarf an einem Telefongespräch hast, sag einfach wann es dir passen würde (Telefonnummer gäb's dann per Mail).
Ich sitze übrigens in er Schweiz und könnte dich ansonsten auch anrufen, falls du nicht ins Ausland telefonieren willst (ich sprech auch kein Schweizerdeutsch - versprochen ).

[lundefugl]

Hallo Christian,

hab gerade gesehen, dass du "filterEveryNthPosition" versucht hast anzupassen.
Ich bin allerdings der Meinung, dass das immer noch nicht ganz korrekt ist. Damit kommen immer die Positionen 0 und 1 in die Ergebnisliste.

Wenn du deine Lösung mit dem manuellen Insert der 0-ten Position favorisierst, so müsste in meinen Augen die Schleife mit "increment" beginnen statt mit "1".

Code:

double increment = positions.size() / (double) (maximumPositionCount - 1 /* first position */ - 1 /* last position */);
        for (double i = increment; i < positions.size() - 1; i += increment) {
...

Gruß
Thomas

[routeconverter]

Wenn du deine Lösung mit dem manuellen Insert der 0-ten Position favorisierst, so müsste in meinen Augen die Schleife mit "increment" beginnen statt mit "1".

Danke für den Hinweis.

Ich hadere immer noch mit Deinem großen Pull-Request, schaue mir gerade Deine Änderungen Zeile für Zeile an und übernehme Code in kleinen Happen: 9606284f4c26da9c94630a587307edeb6ba76aa5, d46b794dc5301b899c0ed36a01ebeb0c605d218c

Parallel habe ich einen Profiler angeworfen und begonnen, Codestellen zu optimieren, die bei Deinen 600000-Positionen-Dateien immer wieder im Stacktrace auftauchen. Beispielsweise optimiert 275eee6c61581e4ecf4629270daf028ef639722f das Selektieren von vielen Positionen.

Dabei ist mir aufgefallen, daß das ProfileView zumindest bei meinem Rechner das Arbeiten unmöglich macht. Bevor das nicht flutscht, machen weitere Optimierungen keinen Sinn, da man sie nicht merkt oder messen kann (ich bin ein Fan von Premature optimization is the root of all evil).

[routeconverter]

Dabei ist mir aufgefallen, daß das ProfileView zumindest bei meinem Rechner das Arbeiten unmöglich macht. Bevor das nicht flutscht, machen weitere Optimierungen keinen Sinn, da man sie nicht merkt oder messen kann

Damit komme ich nicht voran: das ProfileView "verstopft" die AWT-Eventqueue und macht das Arbeiten mit 700000 Positionen auf meinem Rechner unmöglich. Wenn ich längere Wartepausen in filterVisiblePositions() einbaue, merke ich das nicht.

Ist das bei Dir kein Problem?

[lundefugl]

Hallo Christian,

Damit komme ich nicht voran: das ProfileView "verstopft" die AWT-Eventqueue und macht das Arbeiten mit 700000 Positionen auf meinem Rechner unmöglich. Wenn ich längere Wartepausen in filterVisiblePositions() einbaue, merke ich das nicht.

Ist das bei Dir kein Problem?

im Moment bin ich nicht zu Hause, sondern produziere neue Daten ;-).
Dadurch kann ich im Moment keinen Blick in den Code werfen oder was ausprobieren. Daher erst mal die blöde Frage: Was meinst Du mit "ProfileView" ? Ist das eine Klasse, Funktion oder Profiler ?

Wenn's ein Profiler ist, so hab' ich damit noch nie gearbeitet. Zu Hause hab ich bis jetzt keinen benötigt und in der Firma setzen wir YourKit ein. Wenn ich wieder zurück bin, kann ich aber gern mal bei mir einen Profiler laufen lassen. Evtl. gibts ja Optimierungsmöglichkeiten. Auf meiner Maschine war die Performance bis jetzt immer ausreichend, so dass ich da nie in deinem Code nach Optimierungspotential geschaut habe.

Gruß
Thomas