Path: csiph.com!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail From: "Christian H. Kuhn" Newsgroups: de.comp.lang.java Subject: Re: Rekursion bricht nicht ab Date: Wed, 13 Apr 2016 21:56:56 +0200 Lines: 51 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-15 Content-Transfer-Encoding: 8bit X-Trace: individual.net 0GW0rFBJ0xBisnFyN5xhAAbi+LaXf7gNInBDyzxWEYJFYPZ+k= Cancel-Lock: sha1:UM8h0r/qwpyImUd9fyMDjGaYeEY= User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:38.0) Gecko/20100101 Thunderbird/38.7.2 In-Reply-To: Xref: csiph.com de.comp.lang.java:12934 Hallo Wanja, Danke für die Hinweise. Am 13.04.2016 um 19:25 schrieb Wanja Gayk: > a) im Algorithmus suchen (insb. bei Rekursion: Werden z.B. bereits > gewonnene Erkentnisse verworfen und/oder neu berechnet, obwohl man sie > sich merken kann?) Zur Zeit sicher so. Ich suche bis Tiefe n. Wenn ich keine Lösung habe, suche ich bis Tiefe n+1, baue den Baum aber komplett neu auf. Ich müsste alle Stellungen in Tiefe n speichern und im nächsten Durchlauf dann bearbeiten. Spart viel Zeit, kostet viel Speicher. Werde ich in der nächsten Version probieren. > b) in der Datenstruktur (z.B. du löscht immer Werte am Anfang einer > ArrayList, das ist O(n) -> bei einer LinkedList ist removeFirst() nur O > (1), z.B. du iterierst ohnehin immer durch eine Liste und ab und zu > löscht du was an der aktuellen Position, dann ist LinkedList und > Iterator#remove() besser statt ArrayList#remove(n) oder > LinkedList#remove(n), oder z.B. die Suche in einem Ergebnis ist linear, > dabei ist die Liste selten geschriebenm aber oft gelesen und eine binäre > Suche ist schneller, oder vielleicht willst du auch eine HashMap, zb. > ein HashSet, um zu checken, ob etwas schon vorhanden ist?) Hm. Werde ich ausprobieren und messen müssen. Wo ich nur peek, pop und push brauche, verwende ich einen Stack<>, und da der von Vector<> erbt, kann ich beim Hashen auch mal eben durchiterieren. Zum Speichern schon gesehener Stellungen benutze ich je nachdem HashMap oder HashSet. Die ArrayList<>s habe ich aufgrund deines Posts mal mit LinkedList<>s ersetzt, weil ich tatsächlich hauptsächlich durchiteriere und nur gelegentlichst mal auf eine Index-Position zugreife. Allerdings ohne signifikanten Zeitvorteil. Werde ich mir nochmal genauer anschauen. > c) in der Speicherverwaltung - und zwar weniger im Erzeugen von vielen, > kurzlebigen Objekten, sondern darin dem Garbage-Collector nicht genügend > Speicher gegeben zu haben( -verbose:gc ), sodass es unnötig viele full > garbage collections gibt. Auch damit habe ich mal rumgespielt. Speicher bleibt bislang insgesamt unter 300 MB, -Xmx1g hat keine Zeitveränderung gezeigt. > Download hier: https://visualvm.java.net/ Das ist doch mal ein interessantes Werkzeug :-) Warum lernt man sowas nicht im Studium? Vielen Dank! lg QNo