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

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

Re: Rekursion bricht nicht ab

Show key headers only | View raw

Am 23.04.2016 um 14:57 schrieb Patrick Roemer:
> - Bereits angesprochen: Repräsentation ändern, so dass gleich belegte
> Gläser zusammengefasst werden.

Geht halt nicht unbeschränkt. (a,a,a) () ist zwar ideell dasselbe wie ()
(a,a,a), sieht aber anders aus. Das sind auf dem Screen zwei
verschiedene Stellungen. Wenn ich die einheitlich repräsentiere, brauche
ich nicht nur einen Algorithmus, der die tatsächliche Stellung in die
vereinfachte überführt, sondern auch einen, der sie dann incl. Lösung
zurücküberführt. Selbst Chessbase, bei denen Jahrzehnte an Entwicklung
und viel Geld dahinter stehen, hatten neulich noch einen Bug drin: Eine
Stellung ist durch eigenartiges Spiel mit vertauschten Farben
entstanden, Schwarz am Zug, bei „regulärem“ Verlauf wäre Weiß am Zug.
Chessbase hat die Identität der Stellung erkannt, aber die Lösung nicht
transformiert. Züge wurden angegeben, als sei Weiß am Zug. Irritierend.

> - Vector<Character> durch String ersetzen.

Ich dachte, veränderliche Dinge sind durch konstante Strings schlecht
repräsentiert?

> - Heuristische Sortierung der neu erzeugten Züge, z.B. solche mit
> bereits gleichfarbig belegten Gläsern als Ziel zuerst ausprobieren.

In der Breitensuche sicher sinnvoll. Da wird man aber aufpassen müssen,
dass man nicht soviel Optimierungslogik erzeugt, dass die Optimierung
aufwändiger als die Lösung ist :-)

> - Vector durch ArrayList ersetzen.

Das hatte ich mir schon mal vorgenommen, mich in die Details einzulesen,
wann welche Liste/Vector besser ist.

> Ausserdem würde ich das explizite Gewerkel mit dem Hashcode und das
> Cloning auf den Prüfstand stellen. IMHO leidet die Codeverständlichkeit
> darunter, es bietet Raum für zusätzliche Fehlerquellen, und vom
> Bauchgefühl her würde ich da keinen Gewinn von erwarten - zumindest
> keinen signifikanten. Ich würde anstelle des "bigHashCode" die
> eigentlichen Objekte mit "normalem" #equals() und #hashCode() verwenden,
> und den copy constructor statt des #clone().

Ich habe das mal ausprobiert, dass ich keine HashSet<BigInteger>,
sondern wirklich eine HashSet<LSBoard> verwende. Erster Durchlauf:
Katastrophe. War im Nachhinein auch klar, denn in bigHashCode() bekommen
unterschiedliche, aber äquivalente Stellungen den gleichen Hashcode,
während bislang equals() wirklich nur identische Stellungen als gleich
erkennt, aber keine Permutationen.

Also equals() angepasst. Um das eindeutig zu bekommen, müssen die LSTube
irgendwie eindeutig sortiert werden. Also muss LSTube jetzt Comparable
implementieren. Für LSTube#compareTo(LSTube) ist mir im Moment noch
nichts besseres eingefallen als das Vergleichen von int hashCode(). Mit
dem Ergebnis, dass ich mich jetzt insgesamt 95% der Rechenzeit  in
LSBoard#equals() und LSTube#hashCode() aufhalte. Rechenzeitzunahmen
bislang zwischen 50 und 1500%. Ineffektiv bei der aktuellen
Datenrepräsentation. Ohne grundlegende Änderungen ist der status quo
wohl das beste erreichbare Ergebnis. Und es ist praxistauglich.

Die nächste Idee ist, die Gläser statt eines Vector<Character> durch ein
Bitfeld zu repräsentieren. Mit 31 Farben sollte ich gut hinkommen, das
wären 5 bit, max. 4 Plätze macht 20 bit, das ist gut in ein int
reinzupacken. hashCode() ist dann nur ein Getter für den int. Ich suche
noch effiziente Algorithmen für Stackoperationen auf einem Bitfeld.

Dann denke ich doch nochmal über deine Art nach, Züge zu repräsentieren.
Die beschreibt Reagenzgläser nicht durch ihren Platz, sondern durch
ihren Inhalt. Und du hast völlig recht, dass das bei der Zuggeneration
Zeit spart. Es ist halt „ausgabeunfreundlich“. Im Prinzip sind die
Gläser dann nicht in einer Liste o.ä., sondern in einer Menge. Wenn ich
da mal ne GUI drüberlege, brauche ich noch eine Liste, in der
festgehalten ist, welches Glas auf welchem Platz steht. Das wird
vermutlich in dem Moment lustig, in dem von zwei Gläser gleichen Inhalts
sich mindestens eins verändert ((a,a) (a,a) -> (a) (a,a,a)). Und ich
brauche eine Zuordnung des Zuges (a,a)->(a,a) zu den graphischen
Objekten. Lösbar; die Frage ist halt die nach der Effizienz.

Mit soviel Lerneffekt hatte ich gar nicht gerechnet, als ich angefangen
habe. Und mit Stefan Rams Ansatz, der offensichtlich in nochmal deutlich
kürzerer Zeit eine, aber nicht unbedingt die kürzeste Lösung findet,
habe ich mich noch gar nicht beschäftigt.

Ach ja, die eigentlichen Lerninhalte haben funktioniert: Ich lernte,
dass beim Refactoring eine umfangreiche Suite von Unit-Tests unendlich
hilfreich ist; dass 100% Code-Abdeckung durch Tests kein Fetisch ist;
dass checkstyle mit der gleichen Regeldatei in unterschiedlichen
Umgebungen seltsamerweise unterschiedliche Ergebnisse bringt; und dass
Maven und Jenkins jetzt laufen :-)

Und daher wende ich mich jetzt aktuelleren Aufgaben zu. Der Thread ist
gebookmarked, irgendwann im Wintersemester greife ich das wieder auf.

lg
QNo

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

Thread

Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-08 23:28 +0200
  Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-09 16:13 +0200
    Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-10 15:41 +0200
      Re: Rekursion bricht nicht ab Peter Büttner <not_for_mail_peb@gmx.net> - 2016-04-10 16:45 +0200
        Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-10 18:28 +0200
          Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-13 19:25 +0200
            Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-13 21:56 +0200
              Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-23 16:13 +0200
              Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-23 16:13 +0200
                Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-23 17:31 +0200
                Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-25 00:53 +0200
                Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-25 00:56 +0200
                Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-23 19:22 +0200
            Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-14 00:42 +0200
              Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-14 09:20 +0200
              Re: Rekursion bricht nicht ab Christoph Schneegans <Christoph@Schneegans.de> - 2016-04-14 18:47 +0200
              Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-23 16:13 +0200
                Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-25 12:07 +0200
                Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-25 17:38 +0200
                Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-25 22:36 +0200
                Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-28 08:26 +0200
      Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-10 22:15 +0200
        Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-12 15:46 +0200
          Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-12 18:32 +0200
            Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-13 20:44 +0200
              Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-14 12:07 +0200
                Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-23 13:35 +0200
                Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-23 14:57 +0200
                Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-25 23:05 +0200
                Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-26 01:16 +0200
                Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-23 16:05 +0200
                Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-25 12:48 +0200
  Re: Rekursion bricht nicht ab v_borchert@despammed.com (Volker Borchert) - 2016-04-10 06:07 +0000
  Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-10 15:40 +0200
  Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-11 11:21 +0200
    Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-12 15:57 +0200
      Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-12 18:28 +0200
        Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-12 23:36 +0200
          Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-25 21:42 +0200

csiph-web