Re: Generics und Wildcards

Path	csiph.com!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From	"Christian H. Kuhn" <qno-news@qno.de>
Newsgroups	de.comp.lang.java
Subject	Re: Generics und Wildcards
Date	Thu, 22 Aug 2019 16:55:40 +0200
Lines	46
Message-ID	<gs7ondFi3p2U1@mid.individual.net> (permalink)
References	<gs4mcmFsqvfU1@mid.individual.net> <qjm66t$mu4$1@newsreader4.netcologne.de>
Mime-Version	1.0
Content-Type	text/plain; charset=utf-8
Content-Transfer-Encoding	8bit
X-Trace	individual.net IgpuJEjICBWKLxMNOEzVIQmLJ2LqXUegTR3p4+RphmO+EPNQU=
Cancel-Lock	sha1:BPF+t8/kGy1dvIyaDPkUGZ7ohHE=
User-Agent	Mozilla/5.0 (Windows NT 10.0; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.8.0
In-Reply-To	<qjm66t$mu4$1@newsreader4.netcologne.de>
Xref	csiph.com de.comp.lang.java:13275

Show key headers only | View raw

Am 22.08.2019 um 15:43 schrieb Patrick Roemer:
> Responding to Christian H. Kuhn:
>> Eine PriorityQueue<LSNode<LSElement<?>>>, die nach Distanz sortiert.
> 
> Habe ich noch nie benutzt, daher interessehalber: Musst Du da die
> jeweils gefundenen Nachbarn nicht gezielt entfernen und dann nach Update
> neu einsortieren? Hättest Du dann nicht zwar ein O(n) für die Suche nach
> dem Minimum gespart, aber Dir dafür x andere O(n) für die #remove()
> eingetreten...?

Müsste ich. Theoretisch. Wenn ich das machen würde, würde ich keine
PriorityQueue nehmen, sondern ein TreeSet o.ä., was mir remove in O(log
n) gibt.

Nun habt ihr mir aber hier beigebracht (ohne Link auf den Thread, oder
war es doch auf stackoverflow?), dass das nicht nötig ist. Wenn ich
einen kürzeren Weg zu einer Position gefunden habe, füge ich die einfach
mit der kürzeren Distanz zur Queue hinzu. Der Trick ist, dass die
Position mit der kürzesten Distanz auf jeden Fall als erste aus der
Queue kommt und damit besucht wird. Ich muss also jede aus der Queue
entnommene Position einmal testen, ob sie schon besucht ist. Falls ja,
werfe ich sie weg und hole die nächste.

Wie schnell das ist, hängt natürlich davon ab, wie schnell isVisited()
ist. Zur Zeit werfe ich alle generierten Nodes in eine HashMap<LSNode,
LSNode> und suche über get(). equals() ist so implementiert, dass die
enthaltenen LSElement verglichen werden. Wenn Distanz und damit der
Vorgänger oder aber der Besucht-Status upgedated werden, wird der Node
aus der HashMap überschrieben. Bei den bisherigen Anwendungen schnell genug.

Auf SO hatte sich auch jemand daran gestört, dass ich keine eigene
Besucht-Datenstruktur vorhalte, sondern das über ein Flag im Node löse.
Kann nicht viel schneller sein. Bisher: Node aus der Queue, passenden
Value aus der Gesamt-Hashmap. visited-Flag prüfen, bei falsle
(visited-Flag setzen, Node in Gesamt-Hashmap schreiben). Mit eigener
Struktur: Node aus der Queue, contains() auf die visited-HashMap, bei
false Node in visited-HashMap schreiben. Ich spare also einen Test und
u.U. eine Änderung eines boolean, und die Zugriffszeiten auf eine
HashMap dürften auch irgendwie von n abhängen, die Docs machen da keine
Zusicherung. Für ein HashSet allerdings ist das O(1), und ich habe die
Hoffnung, dass HashMap contains(), get() und put() unterhalb von O(log
n) schafft. Und wenn ich dann noch initialCapacity rauf und loadFactor
runtersetze, sollte für meine Anwendungen der Unterschied minimal werden.

lg
QNo

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

Thread

Generics und Wildcards "Christian H. Kuhn" <qno-news@qno.de> - 2019-08-21 12:57 +0200
  Re: Generics und Wildcards Michael Paap <feunews@mpaap.de> - 2019-08-21 16:18 +0200
    Re: Generics und Wildcards "Christian H. Kuhn" <qno-news@qno.de> - 2019-08-21 17:32 +0200
  Re: Generics und Wildcards "Christian H. Kuhn" <qno-news@qno.de> - 2019-08-21 18:06 +0200
  Re: Generics und Wildcards Patrick Roemer <sangamon@netcologne.de> - 2019-08-21 19:42 +0200
    Re: Generics und Wildcards "Christian H. Kuhn" <qno-news@qno.de> - 2019-08-21 21:17 +0200
      Re: Generics und Wildcards Patrick Roemer <sangamon@netcologne.de> - 2019-08-22 12:04 +0200
        Re: Generics und Wildcards "Christian H. Kuhn" <qno-news@qno.de> - 2019-08-22 13:47 +0200
          Re: Generics und Wildcards Patrick Roemer <sangamon@netcologne.de> - 2019-08-22 14:45 +0200
      Re: Generics und Wildcards Patrick Roemer <sangamon@netcologne.de> - 2019-08-25 19:36 +0200
        Re: Generics und Wildcards "Christian H. Kuhn" <qno-news@qno.de> - 2019-08-28 22:08 +0200
          Re: Generics und Wildcards Patrick Roemer <sangamon@netcologne.de> - 2019-08-29 11:11 +0200
            Re: Generics und Wildcards "Christian H. Kuhn" <qno-news@qno.de> - 2019-08-29 23:56 +0200
  Re: Generics und Wildcards Patrick Roemer <sangamon@netcologne.de> - 2019-08-22 15:43 +0200
    Re: Generics und Wildcards "Christian H. Kuhn" <qno-news@qno.de> - 2019-08-22 16:55 +0200

csiph-web