Menu
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.
;; 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)))))
510
Application of the Stack A Stack can be used for evaluating expressions consisting of operands and operators. Stacks can be used for Backtracking, i.e., to check parenthesis matching in an expression. It can also be used to convert one form of expression to another form. It can be used for systematic Memory Management.
A stack is a linear data structure, collection of items of the same type. Stack follows the Last In First Out (LIFO) fashion wherein the last element entered is the first one to be popped out. In stacks, the insertion and deletion of elements happen only at one endpoint of it.
In stacks, The last element in a list is tracked with a pointer called top. Visualizing a Stack. Popping an element from a stack will take O(1) time complexity. Popping the last element in a stack will take O(n).
Methods of reducing stack usage In general, you can lower the stack requirements of your program by: writing small functions that only require a small number of variables. minimizing the number of variables that are in use at any given time at each point in a function. avoiding the use of large local structures or ...
The loop/recur version is the right way. Clojure cannot optimize tail calls due to limitations of the JVM.
175
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
