Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > de.comp.lang.java > #13161

Re: Dijkstra-Implementierung mit theoretischer Fehlerquelle

Show all headers | View raw

Am 05.01.2018 um 12:57 schrieb Patrick Roemer:
> Responding to Christian H. Kuhn:
> 
> Ich habe dieses mehrteilige Epos nur überflogen, kann also gut sein,
> dass ich was übersehen und/oder falsch verstanden habe...

Scheint alles zu passen.

>> TreeMap<Knoten, Knoten> graph;
> Die Menge aller Knoten? Da gibt's mit Set einen passenderen Typ.
Set<E> hat kein get(E e). Daher (kam die Idee von Michael oder hab ichs
ergoogelt?) Map<E, E>, einfügen von e mit put(e,e), und schon kann ich
ein E mit get(e) bekommen. Ok, ist von der Semantik her schräg, weils
einmal Key und einmal Value ist. Ich bin offen für besseres.

>> PriorityQueue<Knoten> warteSchlange;
> Mit einer PriorityQueue hast Du aber doch kein gezieltes #remove()...?
> Mit unveränderlichen Knoten wahrscheinlich nicht dramatisch - man
> bekommt halt Duplikate, aber da eh nur der Eintrag mit der kürzesten
> Distanz interessiert, stören die nicht, abgesehen davon, dass sie
> Speicher fressen. Aber es klang so, als ob Deine Knoten mutable seien,
> und dass Du ein O(n)-Traversal zwecks Removal vermeiden wolltest. Wie
> passt das denn zusammen?

Die Duplikate stören halt wirklich nicht. Objekte SIND mutable. Das
Sortierkriterium kann sich aber nur verringern. Ich füge dann das neue
Objekt (es ist ja nur der Zeiger darauf, das ist nicht viel Speicher)
ein. Es wird auf jeden Fall VOR dem alten Eintrag eingefügt (kann auch
sein, dass der alte Eintrag durch das Einfügen nach vorne gespült wird
und beide jetzt direkt hintereinander stehen) und als besucht
gekennzeichnet. Beide Einträge zeigen aufs richtige Objekt, haben die
aktuell richtige Distanz. Sobald der erste drankommt, wird das Objekt
als besucht gekennzeichnet. Das wird beim zweiten Eintrag erkannt, der
wird dann ohne weitere Bearbeitung verworfen. Dirty, aber quick genug.

Einzige Lösung, die bei Änderung mutabler Objekte umsortiert, ist mW die
SortedList von JavaFX. Hab jedenfalls nichts anderes gefunden. Getestet.
Laufzeit erhöht sich um Faktor 10. Verworfen. Auch hier bin ich offen
für besseres.

lg
QNo

Back to de.comp.lang.java | Previous | Next — Previous in thread | Find similar

Thread

Dijkstra-Implementierung mit theoretischer Fehlerquelle "Christian H. Kuhn" <qno-news@qno.de> - 2018-01-04 18:44 +0100
  Re: Dijkstra-Implementierung mit theoretischer Fehlerquelle "Christian H. Kuhn" <qno-news@qno.de> - 2018-01-05 00:23 +0100
    Re: Dijkstra-Implementierung mit theoretischer Fehlerquelle "Christian H. Kuhn" <qno-news@qno.de> - 2018-01-05 12:02 +0100
      Re: Dijkstra-Implementierung mit theoretischer Fehlerquelle Patrick Roemer <sangamon@netcologne.de> - 2018-01-05 12:57 +0100
        Re: Dijkstra-Implementierung mit theoretischer Fehlerquelle "Christian H. Kuhn" <qno-news@qno.de> - 2018-01-07 20:57 +0100

csiph-web