Która funkcja jest najlepsza pod względem wydajności i czasu użytkowania stosu

Question

Napisałem 3 funkcje, które zliczają ile razy pojawia się element-a na liście. Próbowałem różnych wejść i profilowałem to, ale nadal nie wiem, która funkcja jest najlepsza pod względem wydajności użycia stosu i wydajności czasu. Proszę pomóż mi.

;; 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))))) 

Answer 1

Wersja pętla/powtarzać to właściwa droga. Clojure nie może zoptymalizować wywołań końcowych z powodu ograniczeń JVM.

Answer 2

Pisanie kodu więc kompilator/interperter może optymalizowania go za ogon rekursji, powinny spowodować zwiększenie wydajności i zmniejszenie wykorzystania stosu. Myślę, że twoja normalna funkcja liczenia mogłaby kwalifikować się do rekurencji ogona, tak że powinna być dość szybko. Nie jestem pewien, bo ja tylko pstry w Lisp jako hobby.

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