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

Groups > de.comp.lang.java > #13265 > unrolled thread

Generics und Wildcards

Back to article view | Back to de.comp.lang.java

Contents

  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

#13265 — Generics und Wildcards

Liebe Gemeinde,

ich hab es auf stackoverflow probiert, aber kaum kommt mal ein
wirkliches Problem, kann da auch niemand helfen ...

Implementation eines generischen Dijkstra zur Lösung von beliebigen
Spielen. Randbedingung: Kantengewichte alle 1, Kanten implizit definiert
über die Spielregeln.

Kern sind die Spielpositionen und die in ihnen möglichen Spielzüge. Die
muss der Programmierer des Spiels durch Implementierung dieses
Interfaces bereitstellen:

public interface LSElement<T> {
    List<T> findLegalMoves();
    LSElement<T> executeMove(T move);
}

T ist der Typ des Spielzugs. Bei Münzwürfen Boolean, bei einem Würfel
Integer, bei mehreren Würfeln List<Integer>, bei Kartenspielen eine
Karte, eine Folge von Karten, ... Ich könnte Object nehmen, dann
bräuchte ich keine generische Typisierung. Dafür müsste beim
Implementieren des Interfaces ein Hin- und Hergecaste stattfinden.
Fehleranfällig, erfordert Checks, was den Code aufbläht, und kommt mir
ganz allgemein nicht so effizient vor. Mit Generics alles schön
übersichtlich und bis hierhin unproblematisch.

Damit kann man noch keinen Dijkstra machen. Als wird LSElement<T> in
LSNote<LSElement<?>> verpackt. Vorgänger, Entfernung vom Startknoten und
andere, evtl. implementierungsabhängige Daten werden hinzugefügt. Kern
ist natürlich ein Feld vom Typ LSElement<?>. Details sind für mein
Problem unerheblich, aber man sieht an der unbounded wildcard, wohin das
geht.

LSGraph<E extends LSElement<?>> schließlich stellt Datenstruktur und
Methoden für den Dijkstra-Algorithmus bereit. Eine
PriorityQueue<LSNode<LSElement<?>>>, die nach Distanz sortiert. Ein
HashSet<LSElement<?>>, in dem die während des Algorithmus erzeugten
LSElements<> gespeichert werden. Und natürlich

 public void findShortestPath(final LSNode<E> startNode, final LSNode<E>
destNode) {}

wo der eigentliche Dijkstra abläuft.

Wenn ein Knoten besucht wird, werden zunächst die Nachbarknoten
berechnet, und hier laufe ich in Probleme.

final List<?> moves = actNode.getElement().findLegalMoves();

Ich kann wegen der unbounded wildcard nicht über moves iterieren. Kurzes
Googlen fand die Methodik des wildcard capture über eine private
Hilfsmethode.

fspHelper(moves, actNode);

und außerhalb dann

    private <M> void fspHelper(final List<M> moves, final LSNode<E>
actNode) {
	for (final M move : moves) {
	}
    }

Das klappt, ich kann jetzt über die Spielzüge iterieren. Nun möchte ich
für jeden Zug die Folgeposition berechnen. Und das funktioniert nicht.
So sollte es innerhalb der for-Schleife aussehen:

final LSNode<E> newNode = new
LSNode<>(actNode.getElement().executeMove(move));

Der Compiler widerspricht aber:

The method executeMove(capture#3-of ?) in the type
LSElement<capture#3-of ?> is not applicable for the arguments (M)

Und das verstehe ich nicht. Der Typ T in LSElements<T> ist unbeschränkt
und übersetzt sich zu T extends Object. Und was immer M sein mag, es ist
ein Subtyp von Object und sollte da hineinpassen. Wenn es das nicht tut,
machen Generics irgendetwas, was ich noch nicht verstanden habe. Kann
mir jemand a) eine Erklärung b) eine Lösung geben?

Natürlich käme ich drum herum, wenn ich LSGraph als LSGraph<M,
LSElement<M>> deklarierte. Meiner Ansicht nach wird dadurch aber das
Prinzip der Kapselung verletzt. Niemand außer dem Implementor von
LSElement<T> sollte darüber nachdenken müssen, von welchem Typ ein
Spielzug ist. Oder indem ich LSElement wie oben erwähnt nicht typisiere
und auf Object als Spielzugtyp ausweiche. Das möchte ich aber nach
Möglichkeit erst machen, wenn ich begriffen habe, warum der oben
beschriebene Weg nicht funktioniert.

TIA
QNo

[toc] | [next] | [standalone]

#13266

Am 21.08.2019 um 12:57 schrieb Christian H. Kuhn:

> Der Compiler widerspricht aber:
> 
> The method executeMove(capture#3-of ?) in the type
> LSElement<capture#3-of ?> is not applicable for the arguments (M)
> 
> Und das verstehe ich nicht. Der Typ T in LSElements<T> ist unbeschränkt
> und übersetzt sich zu T extends Object. Und was immer M sein mag, es ist
> ein Subtyp von Object und sollte da hineinpassen. Wenn es das nicht tut,
> machen Generics irgendetwas, was ich noch nicht verstanden habe. Kann
> mir jemand a) eine Erklärung b) eine Lösung geben?

Ich bin grad nicht fit, deswegen habe ich mir das nur ganz grob
durchgelesen. Kann also sein, dass ich völlig an deinem Problem
vorbeirede. Aber diese Art von "Unverständnis" hat meistens den Grund,
dass die Schranke einer Wildcard mit dem "Elementtyp" verwechselt wird.

Ich erkläre es mal am Beispiel einer Liste:

Wenn du einen Ausdruck wie List<?> hast, dann kannst du über diesen
Ausdruck *nichts* in die Liste tun, eben /weil/ die Wildcard
unbeschränkt ist. Denn das ? steht dafür, dass der Compiler /nichts/
über die Schranke weiß. Das ist also etwas /völlig/ anderes als eine
List<Object>.

Entsprechend kannst du in einer List<? extends Tier> kein Tier reintun,
jedenfalls nicht über diesen Ausdruck. Denn der tatsächliche
Typparameter kann ja irgendein Subtyp von Tier sein.

Hingegen kannst du in einer List<? super Tier> jedes beliebige Tier
reintun, denn was immer der tatsächliche Typparameter ist, es ist ein
Supertyp von tier (incl. Tier).

Wenn das völlig an deinem Verständnisproblem vorbeigeht, bitte ich um
Entschuldigung, siehe oben.

Gruß
Michael

[toc] | [prev] | [next] | [standalone]

#13267

Erstmal gute Besserung!

Am 21.08.2019 um 16:18 schrieb Michael Paap:

> Wenn das völlig an deinem Verständnisproblem vorbeigeht, bitte ich um
> Entschuldigung, siehe oben.

Wenn ich wüsste, ob es vorbeigeht, wäre ich schon weiter :-)

Ich schaue nach LSElements<T>. findLegalMoves() ist ein Producer und
könnte daher auch eine List<? extends T> liefern. executeMove(T move)
ist ein Consumer und könnte auch ein <? super T> verarbeiten. Ich will
aber bei beiden GENAU ein T haben. Welches T ich habe, weiß das
Interface nicht, sondern nur der, der es implementiert.

In findShortestPath(LSNode, LSNode) bekomme ich eine Liste von Zügen
durch Aufruf von findLegalMoves. Den Typ der moves kann ich nicht
vorhersagen, daher muss ich eine List<?> benutzen. Mit der kann ich kaum
arbeiten.

Durch die Hilfsmethode bekomme ich den Typ heraus. Da steht in der
Parameterliste eine List<M>, es wird eine List<?> übergeben, durch type
inference wird nachgeschaut, was M ist, und im Inneren der privaten
Hilfsmethode kann ich M verwenden. Bis hierhin funktionier ja alles, im
Zusammenhang mit List wird da nirgendwo gemeckert.

Jetzt bin ich ja immer noch an einer Stelle, an der der Compiler nichts
von einer Implementation von LSElement<T> weiß. Der schaut nur, ob
executeMove(T move) einen passenden Parameter hat. Und ich glaube, ich
beginne zu ahnen, wo es klemmt.

Im Kopf von LSGraph steht LSGraph<LSElement<?>>. Der Typparameter für
den Zug ist also ?. Das Interface LSElement<T> wird also nicht einfach
so oder mit einem festen Typparameter nachgeschaut, sondern mit ?. Damit
hab ich auch ein executeMove(? move), und daher geht da gar nichts mehr.

Ok, ich fange an zu begreifen, worin das Problem besteht. Ich sehe aber
immer noch nur die beiden Lösungen, die mir nicht gefallen: Entweder
nehme ich LSElement ohne generischen Typ und muss den Zugtyp als Object
mit allen Casts und Checks implementieren. Oder ich ändere auf
LSGraph<Move, LSElement<Move>>, dann muss der Benutzer von LSGraph
Interna der benutzten Implementation von LSElement kennen. Gibt es da
denn keine saubere generische Lösung?

lg
QNo

[toc] | [prev] | [next] | [standalone]

#13268

Grmpf.

Am 21.08.2019 um 12:57 schrieb Christian H. Kuhn:
> T ist der Typ des Spielzugs. Bei Münzwürfen Boolean, bei einem Würfel
> Integer, bei mehreren Würfeln List<Integer>, bei Kartenspielen eine
> Karte, eine Folge von Karten, ... Ich könnte Object nehmen, dann
> bräuchte ich keine generische Typisierung. Dafür müsste beim
> Implementieren des Interfaces ein Hin- und Hergecaste stattfinden.
> Fehleranfällig, erfordert Checks, was den Code aufbläht, und kommt mir
> ganz allgemein nicht so effizient vor. Mit Generics alles schön
> übersichtlich und bis hierhin unproblematisch.

Ausprobiert. Geht nicht. An der Stelle, die bisher Probleme machte. Aber
anders.

final LSNode<E> newNode = new
LSNode<>(actNode.getElement().executeMove(move));

Cannot infer type arguments for LSNode<>.

final LSNode<E> newNode = new
LSNode<E>(actNode.getElement().executeMove(move));

The constructor LSNode<E>(LSElement) is undefined

Spätestens an dieser Stelle beginne ich, Generics zu hassen.

public final class LSNode<E extends LSElement> {
    private final transient E element;
    public LSNode(final E element) {
	this.element = element;
    }
}

[toc] | [prev] | [next] | [standalone]

#13269

Responding to Christian H. Kuhn:

> Als wird LSElement<T> in LSNote<LSElement<?>> verpackt.

Ich verstehe schon nicht, warum hier zwingend ein Wildcard ins Spiel
kommen soll...

Versuch mal, das Problem auf ein minimales, zusammenhängendes
Codebeispiel zu reduzieren, das die Implementierung möglichst weglässt
und sich nur auf die API und die Aufrufe konzentriert.

Viele Grüße
Patrick

[toc] | [prev] | [next] | [standalone]

#13270

Am 21.08.2019 um 19:42 schrieb Patrick Roemer:
> Responding to Christian H. Kuhn:
> 
>> Als wird LSElement<T> in LSNote<LSElement<?>> verpackt.
> 
> Ich verstehe schon nicht, warum hier zwingend ein Wildcard ins Spiel
> kommen soll...

Was wäre denn die Alternative?

> Versuch mal, das Problem auf ein minimales, zusammenhängendes
> Codebeispiel zu reduzieren, das die Implementierung möglichst weglässt
> und sich nur auf die API und die Aufrufe konzentriert.
> 

public interface LSElement<T> {
    List<T> findLegalMoves();
    LSElement<T> executeMove(T move);
}


public class LSNode<E extends LSElement<?>> {
    private E element;
    public LSNode<E>(final E element) {
	this.element = element;
    }
    public E getElement() {
        return this.element;
    }
}

public class LSGraph<E extends LSElement<?>> {
    public void findShortestPath(final E startNode, final E destNode){
        List<?> moves = startNode.getElement().findLegalMoves();
	fspHelper(moves, startNode);
    }
    private <M> fspHelper(final List<M> moves, final E startNode) {
        for (final M move : moves) {
            // Hier ist das Problem: executeMove mag nicht mit M.
            LSNode<E> newNode = new
LSNode<E>(startNode.getElement().executeMove(move));
        }
    }
}

Das müsste bis auf den einen Fehler kompilierbar sein, nichts
überflüssiges enthalten, und alles, was noch dazukommt, macht erst
später Probleme ;-)

Man sollte öfter Auto fahren, das macht den Kopf frei. Die Generics
sollen sicherstellen, dass auf einem implementierten LSElement nur Züge
vom richtigen Typ ausgeführt werden können. Das geht auch mit Object,
Cast und Check. Und dass im LSGraph alle LSNodes den gleichen Typ
LSElement beinhalten. Der Client übergibt Start- und Zielnode, das lässt
sich checken, ob die vom gleichen Typ sind. Alle anderen LSElement
werden von einer Methode des jeweiligen Typs geliefert; wenn die den
falschen Typ haben, war halt der Programmierer ein Idiot. Und auch das
ließe sich checken, das geht mir dann aber langsam zu sehr auf die
Performance. Und schließlich muss ich noch mit defensive copies dafür
sorgen, dass mir da kein LSNode oder LSElement nach den Checks unter der
Hand ausgetauscht wird. Dann habe ich alles, was ich benötige, und das
einzige, was fehlt, ist der Lerneffekt ;-)

TIA
QNo

[toc] | [prev] | [next] | [standalone]

#13271

Responding to Christian H. Kuhn:

> public interface LSElement<T> {
>     List<T> findLegalMoves();
>     LSElement<T> executeMove(T move);
> }
> 
> 
> public class LSNode<E extends LSElement<?>> {
>     private E element;
>     public LSNode<E>(final E element) {
> 	this.element = element;
>     }
>     public E getElement() {
>         return this.element;
>     }
> }
> 
> public class LSGraph<E extends LSElement<?>> {
>     public void findShortestPath(final E startNode, final E destNode){
>         List<?> moves = startNode.getElement().findLegalMoves();
> 	fspHelper(moves, startNode);
>     }
>     private <M> fspHelper(final List<M> moves, final E startNode) {
>         for (final M move : moves) {
>             // Hier ist das Problem: executeMove mag nicht mit M.
>             LSNode<E> newNode = new
> LSNode<E>(startNode.getElement().executeMove(move));
>         }
>     }
> }

Ich bin mir immer noch nicht sicher, ob ich Dein Problem verstehe...

Warum willst Du überhaupt den Parameter von LSElement verstecken? Der
gehört zur API. Generics/Wildcards sind IMHO kein Mechanismus zum
information hiding. Wenn Du mit Gewalt versuchst, die Typinformation
"für den Transport" zu obskurieren, wirst Du am Ziel natürlich Probleme
haben, ohne die verlorene Information klarzukommen.

Weiter sehe nicht, warum LSNode öffentlich sichtbar sein sollte - Deiner
Beschreibung nach ist das ein internes Detail der Dijkstra-Implementierung.

Naiv fände ich sowas erst mal halbwegs akzeptabel:

public static class LSGraph<T> {
  public void findShortestPath(
      final LSElement<T> startNode,
      final LSElement<T> destNode
  ) {
    // ...
  }
}

Wenn man partout forcieren will, dass durchgehend ein Subtyp von
LSElement verwendet wird, müsste man wohl schon bei LSElement selber
anfangen, etwa:

public interface LSElement<T, E extends LSElement<T, E>> {
  List<T> findLegalMoves();
  E executeMove(T move);
}

> Das müsste bis auf den einen Fehler kompilierbar sein, [...]

Ist es nicht. :/

> Man sollte öfter Auto fahren, das macht den Kopf frei. Die Generics
> sollen sicherstellen, dass auf einem implementierten LSElement nur Züge
> vom richtigen Typ ausgeführt werden können. Das geht auch mit Object,
> Cast und Check.

Deine Lösung wäre, das Typsystem komplett auszuhebeln/zu umgehen...?!

Viele Grüße
Patrick

[toc] | [prev] | [next] | [standalone]

#13272

Am 22.08.2019 um 12:04 schrieb Patrick Roemer:
> public static class LSGraph<T> {
>   public void findShortestPath(
>       final LSElement<T> startNode,
>       final LSElement<T> destNode
>   ) {
>     // ...
>   }
> }
> 
> public interface LSElement<T, E extends LSElement<T, E>> {
>   List<T> findLegalMoves();
>   E executeMove(T move);
> }
> 

Ausprobiert. Keine Änderung.

LSNode und LSGraph können natürlich nicht einfach ein T mitschleppen.
Das muss schon

LSNode<E extends LSElement<?, E>>

bzw.

LSGraph<E extends LSElement<?, E>>

sein. Und damit habe ich wieder eine Wildcard drin und komme auf die
gleiche Problematik in findShortesPath(startNode, destNode):

final List<?> moves = actNode.getElement().findLegalMoves();

erfordert eine private Hilfsmethode zum wildcard capture. Und hier liefert

    private <M> void fspHelper(LSNode<E> actNode, final List<M> moves) {
	for (final M move : moves) {
	    final LSNode<E> newNode = new
LSNode<>(actNode.getElement().executeMove(move));
         }
    }

wieder den bekannten Fehler

The method executeMove(capture#3-of ?) in the type
LSElement<capture#3-of ?,E> is not applicable for the arguments (M)

> Warum willst Du überhaupt den Parameter von LSElement verstecken?
Ich dachte, das ist offensichtlich. Welche Klasse als Representation
eines Spielzugs benutzt wird, ist implementationsabhängig und am besten
vor den Benutzern zu verstecken. Wenn ich LSElement implementiere und
den Zugtyp an LSGraph etc. übergeben muss, darf ich später, wenn ich die
Klasse des Zugs ändere, nicht nur die Klasse ändern, sondern auch jeden
Code außerhalb. Daher gehört IMHO der Zugtyp eingekapselt.

Gibt es denn nicht sowas wie LSElement.<T>.getClass()?

lg
QNo

[toc] | [prev] | [next] | [standalone]

#13273

Responding to Christian H. Kuhn:
> Am 22.08.2019 um 12:04 schrieb Patrick Roemer:
>> Warum willst Du überhaupt den Parameter von LSElement verstecken?
>
> Ich dachte, das ist offensichtlich. Welche Klasse als Representation
> eines Spielzugs benutzt wird, ist implementationsabhängig und am besten
> vor den Benutzern zu verstecken. Wenn ich LSElement implementiere und
> den Zugtyp an LSGraph etc. übergeben muss, darf ich später, wenn ich die
> Klasse des Zugs ändere, nicht nur die Klasse ändern, sondern auch jeden
> Code außerhalb. Daher gehört IMHO der Zugtyp eingekapselt.

Jeder Code "außerhalb", der mit beliebigen Zugtypen arbeiten soll, kann
(und sollte) einen generischen Typparameter T verwenden.

Der Typparameter ist integraler Bestandteil des Typen. Wenn Du den per
Wildcard darauf reduzierst, dass das irgendein Typ ist, über den man
nichts weiter weiss, bekommst Du natürlich Probleme, wenn Du später
behauptest, dass es sich um einen speziellen anderen Typ handeln soll.

Mal doch vielleicht mal ein Beispiel auf, das illustriert, wo die
"mangelnde Kapselung" ein Problem sein soll.

Viele Grüße
Patrick

[toc] | [prev] | [next] | [standalone]

#13276

Responding to Christian H. Kuhn:
> public void findShortestPath(final E startNode, final E destNode)

Sollte das wirklich void sein? Ich hätte eher vermutet, dass hier eine
Folge von Zügen (ggfs. mit den resultierenden LSElements) zurückgegeben
werden sollte - und damit müsste der Zugtyp doch auch schon wieder
bekannt sein...?

Viele Grüße
Patrick

[toc] | [prev] | [next] | [standalone]

#13292

Am 25.08.2019 um 19:36 schrieb Patrick Roemer:
> Responding to Christian H. Kuhn:
>> public void findShortestPath(final E startNode, final E destNode)
> 
> Sollte das wirklich void sein? Ich hätte eher vermutet, dass hier eine
> Folge von Zügen (ggfs. mit den resultierenden LSElements) zurückgegeben
> werden sollte - und damit müsste der Zugtyp doch auch schon wieder
> bekannt sein...?
> 

Inzwischen ist das

public LSNode ....

Der Zielknoten wird zurückgegeben, von dem aus bekommt man die
Vorgänger. Wird vermutlich noch in eine List<LSNode> oder gar eine
List<LSElement> umgewandelt, der Anwender soll ja von
Implementierungsdetails wie Zeiger auf Vorgänger verschont bleiben.

lg
QNo

[toc] | [prev] | [next] | [standalone]

#13293

Responding to Christian H. Kuhn:
> Am 25.08.2019 um 19:36 schrieb Patrick Roemer:
>> Responding to Christian H. Kuhn:
>>> public void findShortestPath(final E startNode, final E destNode)
>> 
>> Sollte das wirklich void sein? Ich hätte eher vermutet, dass hier eine
>> Folge von Zügen (ggfs. mit den resultierenden LSElements) zurückgegeben
>> werden sollte - und damit müsste der Zugtyp doch auch schon wieder
>> bekannt sein...?
> 
> Inzwischen ist das
> 
> public LSNode ....

Du verzichtest also zugunsten von "Object, Cast und Check" auf Generics
und präsentierst LSNode, das Deiner Beschreibung nach ein reines
Internum des Dijkstra-Algorithmus ist, in der API? Da fällt mir dann
nicht mehr so wirklich was zu ein. :) Gutes Gelingen!

Viele Grüße
Patrick

[toc] | [prev] | [next] | [standalone]

#13294

Am 29.08.2019 um 11:11 schrieb Patrick Roemer:

> Du verzichtest also zugunsten von "Object, Cast und Check" auf Generics
> und präsentierst LSNode, das Deiner Beschreibung nach ein reines
> Internum des Dijkstra-Algorithmus ist, in der API?

Du hast ja recht :-) Das wird alles mal LSElement statt LSNode. Hatte
ich übrigens erwähnt. Zwischendurch ist es halt auch mal wichtig, etwas
auszurechnen, da zählt dann das Ergebnis. Den Code zeige ich dann aber
in der Regel niemandem.

lg
QNo

[toc] | [prev] | [next] | [standalone]

#13274

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...?

Viele Grüße
Patrick

[toc] | [prev] | [next] | [standalone]

#13275

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

[toc] | [prev] | [standalone]

Back to top | Article view | de.comp.lang.java

csiph-web