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

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

Re: Rekursion bricht nicht ab

Show key headers only | View raw

Responding to Christian H. Kuhn:
> Am 11.04.2016 um 11:21 schrieb Patrick Roemer:
> 
>> [...] eine sinnvolle Obergrenze [...] Kannst Du knicken.
> Inzwischen: ACK. Das ist aber kein Grund, es nicht doch zu optimieren :-)

Ich meinte damit: Eine bijektive Abbildung auf int kannst Du knicken. Da
gibt's auch nicht wirklich was dran zu optimieren. :)

> Wobei du mich noch auf eine andere Idee bringst: Eine Rekursion darf
> tatsächlich auch dann abbrechen, wenn die Stellung bei geringerer
> Rechentiefe in einem anderen Zweig des Baumes aufgetaucht ist, nicht
> aber, wenn sie im anderen Zweig bei tieferer Suche gefunden wird. Man
> könnte statt einem Set eine Map nehmen, bei der zum Hash die
> Rechentiefe mit vermerkt wird.

Ich halte es einfach für den grundfalschen Ansatz, mit Tiefensuche den
kompletten Zugbaum ablaufen zu wollen. Nimm eine Breitensuche, halte die
Objektrepräsentationen bereits gesehener Stellungen in einem HashSet und
liefere die erste gefundene Lösung zurück. Wenn man bei größeren
Szenarien feststellen sollte, dass durch das HashSet der Speicher
platzt, kann man immer noch schauen, ob und wie man das optimieren kann.

Mit dem Ansatz solltest Du für die einfachen Beispiele aus dem
Trailervideo in den Zehntelsekundenbereich kommen, ganz ohne
Optimierungskapriolen.

>> Code sollte zunächst mal korrekt sein, und dann erst performant.
>> Wenn Du Gefahr läufst, eine Lösung nicht zu finden, weil es in
>> einer Sackgasse vorher mal den selben Hashcode gab, läuft was
>> schief.
> 
> Das wir die ursprüngliche Befürchtung, für die ich aber in der Praxis
> bisher keine Anzeichen habe.

Wie auch - Du hast ja bisher nur sehr überschaubare Szenarien. Und
Hashkollisionen zeichnen sich üblicherweise dadurch aus, dass sie eher
selten auftreten.

> Ich habe einen BigInteger bigHashCode()
> gewählt, der die Gläser nach fallender Größe ihres Hashcodes
> verarbeitet und so allen Permutationen von Gläsern den gleichen Code
> verpasst, und solange maximal 16 Farben und Gläser auftauchen und
> nicht mehr als 4 Bewohner in ein Glas passen, müsste diese Funktion
> bijektiv sein (jedenfalls wenn man Stellungen als identisch definiert,
> wenn sie durch Glaspermutation auseinander entstehen). Und damit
> sollte diese Fehlerquelle für eine übersehene Lösung wegfallen.

Zum einen verstehe ich nicht recht, wo bei einem BigInteger dann noch
das Limit für die Bijektivität herkommen soll, zum anderen wäre die
Frage, wieviel Speicher man damit im Vergleich zu einer kompakten
Repräsentation eines Glases überhaupt noch spart.

Viele Grüße,
Patrick

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