Path: csiph.com!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail From: "Christian H. Kuhn" Newsgroups: de.comp.lang.java Subject: Re: Dijkstra-Implementierung mit theoretischer Fehlerquelle Date: Sun, 7 Jan 2018 20:57:43 +0100 Lines: 42 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Trace: individual.net AADywyC/6Mj999KTRY7syAEK544lu3P58a0cM8GXvhEFwITvM= Cancel-Lock: sha1:UK/VrQQ+/vnoziiwp1RauOFVFdE= User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:52.0) Gecko/20100101 Thunderbird/52.5.2 In-Reply-To: Xref: csiph.com de.comp.lang.java:13161 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 graph; > Die Menge aller Knoten? Da gibt's mit Set einen passenderen Typ. Set hat kein get(E e). Daher (kam die Idee von Michael oder hab ichs ergoogelt?) Map, 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 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