Re: Rekursion bricht nicht ab

From	Patrick Roemer <sangamon@netcologne.de>
Newsgroups	de.comp.lang.java
Subject	Re: Rekursion bricht nicht ab
Date	2016-04-23 14:57 +0200
Organization	news.netcologne.de
Message-ID	<nffrf8$qao$1@newsreader4.netcologne.de> (permalink)
References	(4 earlier) <dn4chpF3vqkU1@mid.individual.net> <nej7v8$29p$1@newsreader4.netcologne.de> <dn7iceFt0j4U1@mid.individual.net> <nenq58$rm$1@newsreader4.netcologne.de> <do150dFc4c5U1@mid.individual.net>

Show all headers | View raw

Responding to Christian H. Kuhn:
> Am 14.04.2016 um 12:07 schrieb Patrick Roemer:
> 
>> Bau halt mal auf echte Breitensuche
>> um - *ohne* Rekursion, mit einer while-Schleife über eine FIFO-Queue.
> 
> Ich habe auch dafür die Zeit gefunden. LinkedList als Queue, enthaltene
> Objekte sind Paare von Stellung und Zugliste, die zu der Stellung
> geführt hat. Initial wird die Ausgangsstellung und eine leere Zugliste
> in die Queue getan. While bricht ab, wenn die Queue leer ist.

Genau. :)

> Massiver Rückgang der Rechenzeit. Beispiele:
[...]
> Stellung 1 Level 4:
> (a, b, c, d) (b, c, e, f) (f, g, e, h) (h, c, g, e) (b, h, i, g) (a, d,
> d, i) (f, a, i, j) (i, j, b, g) (j, e, a, j) (h, f, c, d), zwei leere
> Gläser. 1. 2270765 ms, 2. 105984 ms, 3. 4261 ms.

Das sieht doch gut aus. Da dürfte immer noch Luft drin sein, aber nicht
mehr in der Größenordnung, die man durch die Algorithmenwahl erreicht.
*Jetzt* wäre der Punkt, wo man mal hprof/visualvm anwerfen könnte und
anhand der so gefundenen Hotspots low-level-Optimierungen ausprobieren
könnte.

Spontan würde mir einfallen:
- Bereits angesprochen: Repräsentation ändern, so dass gleich belegte
Gläser zusammengefasst werden.
- Vector<Character> durch String ersetzen.
- Heuristische Sortierung der neu erzeugten Züge, z.B. solche mit
bereits gleichfarbig belegten Gläsern als Ziel zuerst ausprobieren.
- Vector durch ArrayList ersetzen.

Keine Ahnung, ob und wieviel das jeweils bringt, da muss man dann
wirklich im Vergleich messen. Zumindest bei den ersten beiden wäre ich
aber zuversichtlich.

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().

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