Chức năng nào là tốt nhất về hiệu quả sử dụng ngăn xếp và thời gian

Question

Tôi đã viết 3 hàm đếm số lần một phần tử xuất hiện trong danh sách. Tôi đã thử nhiều đầu vào khác nhau và lược tả nó nhưng tôi vẫn không biết chức năng nào là tốt nhất về hiệu quả sử dụng và hiệu quả thời gian của ngăn xếp. Hãy giúp tôi ra.

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

Phiên bản loop/tái phát là đúng cách. Clojure không thể tối ưu hóa các cuộc gọi đuôi do các hạn chế của JVM.

Answer 2

Viết mã của bạn để trình biên dịch/interperter có thể optmize nó cho đệ quy đuôi, sẽ dẫn đến tăng hiệu suất và giảm mức sử dụng ngăn xếp. Tôi nghĩ rằng chức năng đếm bình thường của bạn có thể đủ điều kiện cho đệ quy đuôi để một trong những nên được khá nhanh. Không chắc lắm vì tôi chỉ tranh giành Lisp như một sở thích.

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