Path: csiph.com!news.mixmin.net!newsreader4.netcologne.de!news.netcologne.de!.POSTED!not-for-mail
From: Patrick Roemer <sangamon@netcologne.de>
Newsgroups: de.comp.lang.java
Subject: Re: Rekursion bricht nicht ab
Date: Thu, 14 Apr 2016 12:07:36 +0200
Organization: news.netcologne.de
Lines: 78
Distribution: world
Message-ID: <nenq58$rm$1@newsreader4.netcologne.de>
References: <dmqm4qFkm0hU1@mid.individual.net> <neb2mi$m27$1@newsreader4.netcologne.de> <dmv3g8Fngq5U2@mid.individual.net> <neec9f$sgh$1@newsreader4.netcologne.de> <dn4chpF3vqkU1@mid.individual.net> <nej7v8$29p$1@newsreader4.netcologne.de> <dn7iceFt0j4U1@mid.individual.net>
NNTP-Posting-Host: xdsl-87-79-166-218.netcologne.de
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
X-Trace: newsreader4.netcologne.de 1460628456 886 87.79.166.218 (14 Apr 2016 10:07:36 GMT)
X-Complaints-To: abuse@netcologne.de
NNTP-Posting-Date: Thu, 14 Apr 2016 10:07:36 +0000 (UTC)
User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.1.24) Gecko/20100411 Thunderbird/2.0.0.24 Mnenhy/0.7.6.0
In-Reply-To: <dn7iceFt0j4U1@mid.individual.net>
Xref: csiph.com de.comp.lang.java:12937

Responding to Christian H. Kuhn:
> Am 12.04.2016 um 18:32 schrieb Patrick Roemer:
>> Responding to Christian H. Kuhn:
>>> Am 10.04.2016 um 22:15 schrieb Patrick Roemer:
>>>
>>>> Also statt
>>>
>>>> [[a,b], [a,b], [b,a], [], []] => move b to empty [[b], [a,b],
>>>> [b,a], [a], []]
>>>
>>>> sowas wie
>>>
>>>> {[a,b] -> 2, [b,a] -> 1, [] -> 2} => move b to empty {[a] -> 1, [b]
>>>> -> 1, [a,b] -> 1, [b,a] -> 1, [] -> 1}
> 
>> Da finde ich meinen Ansatz schöner. Du kannst eine "redundante" Stellung
>> nach einem Zug gleich wegwerfen, ich muss den Zug gar nicht erst
>> ausprobieren. :)
> 
> Hab ich dann auch mal ausprobiert, aber anders.

Das "anders" ist wahrscheinlich das Problem. ;) s.u.

> public final Vector<LSMove> getMoveList() {
>         Vector<LSMove> moveList = new Vector<LSMove>();
>         HashSet<Integer> startTubes = new HashSet<Integer>();
>         for (int i = 0; i < boardSize; i++) {
>             if (startTubes.contains(tubes.get(i).hashCode())) {
>                 continue;
>             }
>             startTubes.add(tubes.get(i).hashCode());
>             HashSet<Integer> targetTubes = new HashSet<Integer>();
>             for (int j = 0; j < boardSize; j++) {
>                 if (targetTubes.contains(tubes.get(j).hashCode())) {
>                     continue;
>                 }
>                 targetTubes.add(tubes.get(j).hashCode());
>                 LSMove move = new LSMove(i, j);
>                 try {
>                     isLegalMove(move);
>                     moveList.add(move);
>                 } catch (LSBoardBadSizeParameterException |
> LSBoardEmptyStartTubeException | LSBoardNoMoveAtAllException
>                         | LSBoardFullTargetTubeException |
> LSBoardDifferentColoursException e) {
>                     // illegale Züge werden einfach nicht geaddet, keine
> weitere Aktion nötig.
>                 }
>             }
>         }
>         return moveList;
>     }

Dass die Exceptions hier sowohl semantisch als auch von der Performance
her eher fehl am Platz sind, hast Du ja anderweitig schon festgestellt. :)

if(isLegalMove(move)) {
  moveList.add(move);
}

(Bzw. erst gar keine illegalen Züge generieren.)

Das hashCode-Gewerkel finde ich weiterhin äußerst fishy...

> Es gibt wirklich Stellungen, bei denen das Aussondern mehr Zeit kostet
> als der größere Baum.

Gemeint war auch nicht, in jedem Einzelschritt umzukopieren, sondern
durchgehend auf einem Modell a la Map<List<Character>, Integer> zu arbeiten.

Anyway, solange der Algorithmus an sich suboptimal ist, sind Experimente
auf dieser Ebene eher unangebracht. Bau halt mal auf echte Breitensuche
um - *ohne* Rekursion, mit einer while-Schleife über eine FIFO-Queue.
Danach kann man immer noch weiter optimieren.

Viele Grüße,
Patrick