Welche Funktion ist die beste in Bezug auf Stack Usage Efficiency und Zeit

Ich schrieb 3 Funktionen, die zählen, wie oft ein Element in einer Liste erscheint. Ich habe verschiedene Eingänge ausprobiert und profiliert, aber ich weiß immer noch nicht, welche Funktion hinsichtlich Stapeleffizienz und Zeiteffizienz am besten ist. Bitte hilf mir.Welche Funktion ist die beste in Bezug auf Stack Usage Efficiency und Zeit

;; Using an accumulator 
    (defn count-instances1 [a-list an-element] 
     (letfn [(count-aux [list-aux acc] 
         (cond 
          (empty? list-aux) acc 
          :else (if (= (first list-aux) an-element) 
            (count-aux (rest list-aux) (inc acc)) 
            (count-aux (rest list-aux) acc))))] 
     (count-aux a-list 0))) 

;; Normal counting 
    (defn count-instances2 [a-list an-element] 
    (cond 
     (empty? a-list) 0 
     :else 
      (if (= (first a-list) an-element) 
       (+ 1 (count-instances2 (rest a-list) an-element)) 
       (count-instances2 (rest a-list) an-element)))) 

;; using loop. does this help at all? 
    (defn count-instances3 [a-list an-element] 
     (loop [mylist a-list acount 0] 
      (if (empty? mylist) 
       acount 
       (if (= (first mylist) an-element) 
       (recur (rest mylist)(inc acount)) 
       (recur (rest mylist) acount)))))

Quelle

2009-07-22 unj2

Was waren die Ergebnisse Ihrer Profilierungsbemühungen? –

Verschachtelt 'defn' macht wahrscheinlich nicht, was Sie denken. 'defn' definiert immer eine Toplevel-Funktion. Sie können 'leftn' (oder sogar' (lassen Sie [f (fn ...)]) ') verwenden, wenn Sie eine innere Funktion definieren möchten. –

Danke Brian. Aber ich kann den Letfn nicht zur Arbeit bringen. Könntest du meine Frage mit Letfn bearbeiten? Danke vielmals. – unj2

Die Schleife/recur Version ist der richtige Weg. Clojure kann Tail-Aufrufe aufgrund von Einschränkungen der JVM nicht optimieren.

Quelle

2009-07-22 21:01:06 Svante

Das ist nicht genau. Sie sollten sagen, dass Clojure * wählt, um Tail-Aufrufe nicht zu optimieren, weil das in einer Sprache (Java), die sie noch nicht hat, ziemlich schwer zu erreichen ist. Tatsächlich gibt es einige Implementierungen von Sprachen (z. B. SISC - http://sisc-scheme.org/) oben auf der JVM, die Endanrufe optimieren. –

Das ist wirklich seltsam. Warum sollte es keine Tail Calls optimieren wollen? Es hätte uns eine Menge Ärger erspart. Gibt es Kompromisse? – unj2

'recur' ist nett, weil es explizit ist und Sie es nur aus Tail-Positionen verwenden können (der Compiler beschwert sich anders), die Instanzen abfängt, in denen Sie denken, dass Sie tail-recursing sind, aber Sie nicht sind. Es könnte alles automatisch weggemaced werden, aber es ist nicht so mühsam, den Funktionsnamen im Tail-Call durch das Symbol "recur" zu ersetzen. –

Schreiben Sie Ihren Code so dass der Compiler/interperter es für Endrekursion optimieren können, sollten in einem gewissen Leistungssteigerung führen und Nutzungs Reduktion stapeln. Ich denke, deine normale Zählfunktion könnte sich für eine Schwanzrekursion eignen, so dass man ziemlich schnell sein sollte. Nicht sicher, da ich mich nur in Lisp als Hobby beschäftige.

http://en.wikipedia.org/wiki/Tail_recursion

Quelle

2009-07-22 20:45:27 anio

Clojure kann Tail-Aufrufe aufgrund von Einschränkungen der JVM nicht optimieren. – Svante

Rich Hickey's Kommentar zu diesem war, dass es besser war, eine explizite Abstinenz zu haben, die die ganze Zeit (wiederkehrend) funktioniert, als eine implizite, die fast immer funktioniert (aufgrund der Komplexität der JVM) –

@Svante - Clojure kann und optimiert Tail Calls. Sie müssen nur explizit sein, dass Sie es wollen, indem Sie 'recur' verwenden (was eine Sprachdesign-Wahl von Rich Hickey war). Es ist durchaus möglich, TCO auf der JVM die meiste Zeit zu machen. JVM-Beschränkungen beeinflussen nur die gegenseitige Co-Rekursion (was tatsächlich ein ziemlich seltener Fall ist). – mikera

Welche Funktion ist die beste in Bezug auf Stack Usage Efficiency und Zeit

Antwort

Verwandte Themen