在堆栈使用效率和时间方面哪个函数最好

I wrote 3 functions that count the number of times an-element appears in a-list. I tried various inputs and profiled it but I still dont know which function is the best in terms of stack usage efficiency and time efficiency. Please Help me out.

我写了3个函数来计算a-element出现在a-list中的次数。我尝试了各种输入并对其进行了分析,但我仍然不知道哪种功能在堆栈使用效率和时间效率方面最佳。请帮帮我。

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

2 个解决方案

#1

The loop/recur version is the right way. Clojure cannot optimize tail calls due to limitations of the JVM.

loop / recur版本是正确的方式。由于JVM的限制,Clojure无法优化尾调用。

#2

Writing your code so the compiler/interperter can optmize it for tail recursion, should result in some performance increase and stack usage reduction. I think your normal counting function could qualifies for tail recursion so that one should be pretty fast. Not sure since I only dabble in Lisp as a hobby.

编写代码以便编译器/交互操作员可以优化它以进行尾递归,这会导致性能提高和堆栈使用量减少。我认为你的正常计数函数可以有资格进行尾递归,因此一个应该非常快。不确定,因为我只涉及Lisp作为一种爱好。

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